People who analyze algorithms have double happiness. First of all they experience the sheer beauty of elegant mathematical patterns that surround elegant computational procedures. Then they receive a practical payoff when their theories make it possible to get other jobs done more quickly and more economically.
Mathematical models have been a crucial inspiration for all scientific activity, even though they are only approximate idealizations of real-world phenomena. Inside a computer, such models are more relevant than ever before, because computer programs create artificial worlds in which mathematical models often apply precisely. I think that's why I got hooked on analysis of algorithms when I was a graduate student, and why the subject has been my main life's work ever since.

D. E. Knuth

Analyse von Algorithmen (SS 2004)

Peter Rossmanith

Bereich

4+2 SWS Vorlesung im Bereich Theoretische Informatik
und im Vertiefungsgebiet Effiziente Algorithmen

Zeit und Ort

Montags 8-10 Uhr c.t. und Mittwochs 8-10 Uhr c.t. im Raum AH V (Ahornstraße)

Voraussetzungen

Stoff des Informatikgrundstudiums und der zugehörigen Mathematikvorlesungen.

Übung

Skript

Begleitend zur Vorlesung wird es ein vollständiges Skript geben, welches kapitelweise ausgegeben wird. (Eine vorläufige Fassung der ersten vier Kapitel und eines Teils des fünften ist hier: Kapitel 1-5.)

Hier ist die farbige Folie mit dem Flußdiagramm für Quicksort.

Inhalt

Die Vorlesung vermittelt die notwendigen Techniken, welche zur Analyse von Algorithmen benötigt werden, und wendet sie an zahlreichen Beispielen praktisch an.

Literatur

An Introduction to the Analysis of Algorithms von Robert Sedgewick und Phillippe Flajolet ist das für die Vorlesung wichtigste Buch und enthält die Grundlagen der Analyse von Algorithmen.

Weiterführende Literatur

	The Art of Computer Programming. Hier ist besonders das erste Kapitel interessant und der dritte Band. Diese Bücher sind in der Fachbereichsbibliothek in ausreichender Menge vorhanden.
	Analysis of Algorithms - Mathematical Methods, Computational Tools. Dieses Buch entspricht in etwa An Introduction to the Analysis of Algorithms, ist aber vielleicht ein wenig mehr mathematisch orientiert. Ebenfalls sehr gut.
	Concrete Mathematics. Tolles Buch, welches alle notwendigen mathematischen Methoden enthält. Es ist im Prinzip eine ausführlichere Version des ersten Kapitels von The Art of Computer Programming. Sehr viele Aufgaben mit Lösungen.
	Mathematics for the Analysis of Algorithms. Dieses Buch enthält fortgeschrittenere mathematische Techniken, welche an vielen Beispielen erläutert werden. Sehr schwierig!