Vorlesung
"Algorithmentheorie"
Wintersemester 2005/06
Prof. Dr. Susanne Albers

Vorlesung

Montag, 14-16 Uhr, HS 00-026, Gebäude 101, und Donnerstag, 14-16 Uhr, HS 00-036, Gebäude 101.
Die Vorlesung am Donnerstag 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: Geometrisches Divide-and-Conquer, Fast Fourier-Transformation
• Randomisierung: randomisiertes Quicksort, randomisierter Primzahltest, RSA, universelles und perfektes Hashing
• Amortisierte Analyse: Binomial Queues, Fibonacci Heaps, Union-Find-Strukturen
• Greedy-Verfahren: kürzeste Wege, minimale Spannbä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 "Algorithmen und Datenstrukturen" von Th. Ottmann und P. Widmayer erforderlich.

Übungen

Die Übungen werden von Markus Schmidt und Sylva Scholz betreut und finden alle zwei Wochen zu folgenden Terminen statt:

• Mo 11-13 Uhr: SR 00-006, Geb. 051
• Mo 16-18 Uhr: HS 00-026, Geb. 101
• Mo 16-18 Uhr: SR 03-026, Geb. 051
• Mo 16-18 Uhr: SR 02-017, Geb. 052
• Mi 9-11 Uhr: SR 00-006, Geb. 051
• Fr 11-13 Uhr: SR 00-006, Geb. 051

Einteilung der Übungsgruppen

Die Übungsblätter werden über CampusOnline (s.u.) zur Verfügung gestellt. Das erste Übungsblatt kann auch hier heruntergeladen werden.

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. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Second Edition MIT Press, 2001.
• Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen.  4. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2002

Vorlesungs- und Übungsmaterial

Aufzeichnungen und Folien sind auf unserem Webserver verfügbar.

Kreditpunkte

In dieser Veranstaltung können 6 Kreditpunkte erworben werden.

Prüfungen

Die Klausur findet Mittwoch, den 15.03.2006, 14:00 - 16:00 Uhr statt.

Die Wiederholungsklausur findet Freitag, den 29.09.2006, 10:00 - 12:00 Uhr statt.