Ankündigung der Vorlesung

Fortgeschrittene Datenstrukturen und Algorithmen

PD Dr. Sven O. Krumke
Diese Vorlesung findet im WS 2002/03 statt.
Die Ankündigung der Vorlesung ist als Postscriptdatei [34 KByte] und als PDF-Datei [36 KByte] verfügbar.

Inhalt

In der Kombinatorischen Optimierung treten beim Design von Algorithmen viele "elementare Probleme" auf. Mit Hilfe von geeigneten Datenstrukturen für diese "elementaren Probleme" läßt sich der gesamte Algorithmus oft (theoretisch und auch in der Praxis) deutlich beschleunigen.

Die Vorlesung bietet anhand von ausgewählten Themen einen Einblick in moderne Datenstrukturen und Algorithmen sowie ihre Analyse. Dabei werden die einzelnen Datenstrukturen nicht isoliert behandelt, sondern stets im Zusammenhang mit konkreten Fragestellungen aus der Kombinatorischen Optimierung vorgestellt. Unter anderem werden wir folgende Themen in der Vorlesung behandeln:

Amortisierte Analyse

Informell gesprochen wird bei der amortisierten Analyse wird die Laufzeit eines Algorithmus für eine Folge von Operationen nicht separat für jede einzelne Operation, sondern für die gesamte Folge analysiert. Mit Hilfe der amortisierten Analyse und Potentialfunktionen sind oft verbesserte und aussagekräftigere Laufzeitabschätzungen für Algorithmen möglich. Die amortisierte Analyse wird eines der grundlegenden Hilfsmittel für die Analyse der "`fortgeschrittenen Datenstrukturen und Algorithmen"' sein.

Fibonacci-Heaps und Binomial-Heaps

Fibonacci-Heaps senken etwa bei kürzeste-Wege-Algorithmen (Dijkstra) und Algorithmen für Minimale Aufspannende Bäume (Prim) die Laufzeit drastisch. Mit Hilfe von Fibonacci-Heaps lassen sich die Algorithmen von Dijkstra und Prim so implementieren, daß sie in O(m+n log(n)) Zeit Zeit auf Graphen mit n Ecken und m Kanten laufen. Wir werden zeigen, wie man dies noch weiter steigern kann, indem wir einen Minimalbaum-Algorithmus mit Laufzeit O(n+m b(m,n)) vorstellen, wobei b(m,n)=min { i : log^(i) n < m/n} ist.

Union-Find Strukturen

Union-Find Strukturen kommen dann in Spiel, wenn man effizient Partitionen einer Menge verwalten möchte, beispielsweise die Zusammenhangskomponenten eines Graphen im Algorithmus von Kruskal. Die Anwendung von geeigneten (gar nicht so komplizierten) Strukturen ermöglicht es, Kruskals Algorithmus in Zeit O(m log m + m a(m,n)) laufen zu lassen. Hier bezeichnet a(m,n) die inverse Ackermann Funktion, welche für alle Zahlen, die kleiner als die Anzahl der Atome im Universum sind, nach oben durch fünf beschränkt ist.

Splay-Trees

Zur Konstruktion von optimalen statischen Suchbäumen (etwa zur Datenkompression) benutzt man den Algorithmus von Huffman. Wenn die zu organisierenden Daten jedoch erst im Verlauf des Algorithmus (online) verfügbar werden, ist die statische Methode nicht anwendbar. Splay-Trees ermöglichen es mit einfachen Ideen (aber einer nichttrivialen Analyse), bis auf einen konstanten Strafterm die selben Schranken wie in statischen Fall auch für den dynamischen Fall zu bekommen. Anwendungen findet man vor allem in der Datenkompression.

Dynamic Trees

Dynamische Bäume (Dynamic Trees) sind ein Kniff, um etwa aus schnellen Maximalfluß-Algorithmen noch das Letzte an Laufzeit herauszuholen.

Randomisierte Algorithmen

Randomisierte Algorithmen entschärfen viele Worst-Case-Szenarien. Oft kann man einen randomisierten Algorithmus finden, der viel einfacher und zudem (im Erwartungswert) schneller ist als der bestmögliche deterministische Algorithmus.

Termine

Donnerstags von 10-12 Uhr im MA641.

Formalitäten

Anrechenbarkeit: 2 Semesterwochenstunden
Schein: Teilnahmebescheinigungen werden vergeben

Zielgruppe und Voraussetzungen

Die Veranstaltung richtet sich an Studenten der Mathematik und Informatik im Grund- und Hauptstudium. Grundkenntnisse in der kombinatorischen Optimierung sind hilfreich, aber nicht erforderlich.

Skript

Ab sofort kann man mein vorläufiges Skript zur Vorlesung hier herunterladen.

Das Skript ist als Postscriptdatei [1.5 MByte], als gzip'te Postscriptdatei [359 KByte] und als PDF Datei [660 KByte] erhältlich.

Über Kommentare und Hinweise auf (Tipp-) Fehler würde ich mich freuen.

Dr. Sven Krumke
Last modified: Wed Apr 23 08:31:02 CEST 2003