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 2008)

Peter Rossmanith

Bereich

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

Zeit und Ort

Montags 10:15-11:45 Uhr im Raum 5054, Freitags 8:15-9:45 Uhr im Hörsaal AH VI (Informatikgebäude)
Übung Montags 14:00-15:30 Uhr im Seminarraum I1 (4017)

Voraussetzungen

Stoff des Informatikgrundstudiums und der zugehörigen Mathematikvorlesungen.

Skript

Begleitend zur Vorlesung gibt es ein Skript. Hier ist eine vorläufige Fassung aus dem Wintersemester 2005/2006, welches zur diesjährigen Vorlesung noch aktualisiert werden wird.

Inhalt

Die Vorlesung vermittelt die notwendigen Techniken, welche zur Analyse von Algorithmen benötigt werden, und wendet sie an zahlreichen Beispielen praktisch an. Dabei wird sowohl Wert darauf gelegt, die Algorithmen sehr genau zu analysieren - im Extremfall die genaue Anzahl von Maschineninstruktionen, die im Durchschnitt durchlaufen werden -, als auch grobe Abschätzungen mit minimalem Aufwand durchführen zu können.

Literatur

Buch

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

Buch 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.
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