Ausgewählte Algorithmen und Datenstrukturen

Typ:

Vorlesung

Veranstalter:

PD Dr. Sven Schuierer

Zeit und Ort:

Mi 9-11, Hörsaal A

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

• Datenstrukturen: Skip-Listen, randomisierte Suchbäume, Splay Trees, Fibonacci-Heaps, Tries.
• Polynome und die schnelle Fouriertransformation.
• Algorithmen zur Zeichenkettenverarbeitung (Knuth Morris Pratt, Boyer Moore u. a.).
• Verschlüsselung und Kodierung von Texten.
• On-line Algorithmen.

Ferner werden die zum Entwurf einer breiten Palette von Algorithmen benötigten Entwurfsprinzipien herausgearbeitet und an Beispielen erläutert. Das sind das Divide-and-Conquer-Prinzip, das Greedy-Prinzip, dynamisches Programmieren, amortisierte Analyse u. a.

Zum Verständnis der Vorlesung sind Kenntnisse auf dem Gebiet Algorithmen und Datenstrukturen im Umfang des Buches

Norbert Blum: Theoretische Informatik, Oldenbourg (1998)

erforderlich.

Literatur zur Veranstaltung

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