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 2005/06)

Die Benotung der Leistungen in Übung und final exam ist abgeschlossen. Die Ergebnisse können hier eingesehen, die Scheine ab sofort im Sekretariat (E2-6112) abgeholt werden. Übungsteilnehmer, die die Abschlußklausur nicht mitgeschrieben haben, sind nicht aufgelistet. Bei Rückfragen wenden Sie sich bitte an Daniel.

Peter Rossmanith

Bereich

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

Zeit und Ort

Montags 8:15-9:45 Uhr und Freitags 8:15-9:45 Uhr im Raum 5052 (Informatikgebäude)

Am Tag der Informatik fallen alle Lehrveranstaltungen aus.

Voraussetzungen

Stoff des Informatikgrundstudiums und der zugehörigen Mathematikvorlesungen.

Übung

Skript

Begleitend zur Vorlesung gibt es ein Skript. Hier ist eine 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. 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

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