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 (WS 2002/03)

Peter Rossmanith

Bereich

3 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Vertiefungsvorlesung im Bereich Algorithmen

Zeit und Ort

Mittwochs 9-10 Uhr c.t. und Freitags 10-12 Uhr c.t. im Raum 3.9.14 (Garching).

Vorraussetzungen

Stoff des Informatikgrundstudiums und der zugehörigen Mathematikvorlesungen. Insbesondere Spaß an den beiden Vorlesungen Diskrete Strukturen I und II.

Skript

Begleitend zur Vorlesung gibt es ein vollständiges Skript.

Kapitel 1 (Vorläufige Fassung!)
Kapitel 2 (Vorläufige Fassung!)
Kapitel 3 (Vorläufige Fassung!)
Kapitel 4 (Vorläufige Fassung!)

Inhalt

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

Literatur

Buch

An Introduction to the Analysis of Algorithms von Robert Sedgewick und Phillippe Flajolet ist das Buch, welchem die Vorlesung folgt.

Weiterführende Literatur

Buch The Art of Computer Programming. Hier ist besonders das erste Kapitel interessant und der dritte Band. Diese Bücher sind in der Lehrbuchsammlung in ausreichender Menge vorhanden und können während des ganzen Semesters ausgeliehen werden.
Buch 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.
Buch 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.
Buch Mathematics for the Analysis of Algorithms. Dieses Buch enthält fortgeschrittenere mathematische Techniken, welche an vielen Beispielen erläutert werden. Sehr schwierig!

Weitere Informationen zu Analyse von Algorithmen


Peter Rossmanith, 1997-10-14