---

Vorlesung
"Algorithmentheorie"
Wintersemester 2003/04
Prof. Dr. Susanne Albers
Prof. Dr. Thomas Ottmann

---

Inhalt der Veranstaltung

In dieser Vorlesung werden Algorithmen und Datenstrukturen behandelt, die in der  Vorlesung Informatik II im Grundstudium überhaupt nicht oder nicht mit der erforderlichen Tiefe behandelt wurden. Dazu gehören u. a.:

• Divide and Conquer: Geom. Divide and Conquer, Fast Fourier Transformation
• Randomisierung: rand. Quicksort, rand. Primzahltest, RSA, universales und perfektes Hashing
• Amortisierte Analyse: Binomial Queues, Fibnoacci Heaps, Union Find Strukturen
• Greedy Verfahren: kürzeste Wege, Minimal Spannende Bäume, Bin Packing, Scheduling
• Graphenalgorithmen
• Dynamische Programmierung: Kettenprodukt von Matrizen, Editierdistanz, Longest Common Subsequence
• Zeichenkettenverarbeitung: Knuth-Morris-Pratt, Boyer-Moore, Suffix Trees, Huffman Code, LZW

Zum Verständnis der Vorlesung sind Kenntnisse auf dem Gebiet Algorithmen und Datenstrukturen im Umfang der Kapitel 1 bis 6 des Buches Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen erforderlich.

Literatur

Die folgenden Literaturangaben dienen als Grundlage für die Vorlesung. Weiterführende Literatur wird im Laufe des Semesters zu den einzelnen Themen bekannt gegeben.

• T. Corman, C. Leisserson, R. Rivest: Introduction to Algorithms. MIT Press, 1990.
• Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. xvii+696 Seiten, 3. Auflage, Spektrum Verlag, Heidelberg, 1996

Vorlesungsaufzeichnungen und Folien

Aufzeichnungen und Folien sind auf unserem Webserver verfügbar.