---

Vorlesung
"Algorithmentheorie"
Wintersemester 2004/05
Prof. Dr. Susanne Albers

---

Vorlesung

Montag, 09-11, und Mittwoch, 09-11, HS 00-026, Gebäude 101.
Die Vorlesung am Mittwoch findet alle 14 Tage statt.

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.

Übungen

• Mo 11-13, SR 00-010/14, Geb. 101
• Di 11-13, SR 00-006, Geb. 051
• Mi 14-16, SR 00-034, Geb. 051
• Mi 16-18, SR 00-034, Geb. 051
• Do 14-16, SR 00-034, Geb. 051
• Do 16-18, SR 00-010/14, Geb. 101 <--- gestrichen

Je nach Teilnehmerzahl werden 5 oder 6 Übungstermine angeboten.

Einteilung der Übungsgruppen

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.

Kreditpunkte

In dieser Veranstaltung können 6 Kreditpunkte erworben werden.

Prüfungen
Die Klausur findet am 17.03.05 in den Räumen 026, 036, 010/14 und 009/13 im Gebäude 101 von 10:00 bis 12:00 Uhr statt.

Die Klausureinsicht findet am 04.04.05, 10:00 Uhr bis 12:00 Uhr, und am 05.04.05, 13:00 Uhr bis 15:00 Uhr, im Gebäude 079 Raum 019 statt.

Die Wiederholungsklausur findet voraussichtlich am 15.09.2005 im HS 026, Gebäude 101 von 10:00 Uhr bis 12:00 Uhr statt.

Die Klausureinsicht zur Wiederholungsklausur findet am 22.09.2005 von 14:00 Uhr bis 15:00 Uhr im Gebäude 079 Raum 019 statt.