Parametrisierte Algorithmen (WS 2004/05)

Peter Rossmanith

Sprechstunde: Mittwochs 11-12 Uhr

Bereich

4+2 SWS Vorlesung im Bereich Theoretische Informatik

Zeit und Ort

Vorlesung Dienstags 8:15-9:45 Uhr im Hörsaal 5052
sowie Freitags 8:15-9:45 Uhr im Hörsaal 5052
Übung Montags 16:30-18:00 Uhr im Hörsaal 5052.

Aufgemerkt: The mid term exam will take place on December 7th at 8 PM c.t.; the final exam is scheduled to end the lecture series on February 1st.

Übungsblätter

• Blatt 1 (Zusatz: jeder planare Graph hat einen Knoten mit Grad kleiner 6.)
• Blatt 2
• Blatt 3
• Blatt 4
• Blatt 5
• Blatt 6
• Blatt 7
• Blatt 8
• Blatt 9
• Blatt 10
• Blatt 11
• Blatt 12
• Blatt 13
• Midterm Klausur
• Endklausur

Voraussetzungen

Vordiplom.

Literatur

Es gibt bislang nur ein Buch zu diesem Thema:
R. G. Downey and M. R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
Dieses Buch liegt im Semesterapparat in der Informatikbibliothek aus.

Die alten Vorlesungsfolien sind hier und hier sind die Folien im neuen Format (Neu: Jetzt ohne Farbschnickschnack, damit der Drucker nicht gequält wird).

Inhalt

Viele Probleme, die in der Praxis auftauchen, sind NP-hart und werden daher von Theoretikern in der klassischen Sichtweise als praktisch nicht exakt lösbar eingestuft. Natürlich müssen die Probleme praktisch doch gelöst werden, wobei Approximationsalgorithmen oder Heuristiken verwendet werden können. Bei vielen praktischen Problemen werden dabei erstaunlich gute Ergebnisse in kurzer Zeit erzielt. Es scheint als seien praktisch auftretende Probleminstanzen nicht so hart, und die NP-Vollständigkeit manifestiere sich in künstlichen, praxisfernen Instanzen.

Parametrisierte Algorithmen versuchen gezielt die Einfachheit praktisch vorkommender Probleminstanzen auszunutzen. Um diese ''Einfachheit'' erfassen zu können, wird ein Parameter verwendet, der oft k genannt wird. Die Probleminstanz wird als einfach angesehen, wenn der Parameter klein ist. Ein Beispiel ist das Auflösen von Konflikten in Konfliktgraphen. Dieser Graph gibt an, welche Messergebnisse zueinander in Widerspruch stehen. Man möchte nun möglichst wenige Messergebnisse ignorieren, so dass keine Konflikte verbleiben. Dieses Problem ist NP-vollständig. Wenn wir die Anzahl der Konflikte mit k bezeichnen, können wir aber einen einfachen Algorithmus finden, dessen Laufzeit eine Funktion von k multipliziert mit einem Polynom der Grösse des Graphen ist. In der Praxis ist aber k sehr klein, da nur wenige Messfehler vorkommen. Der resultierende Algorithmus gibt ein garantiert optimales Ergebnis.

In dieser Vorlesung werden solche parametrisierten Algorithmen und allgemeine Techniken, solche Algorithmen zu entwerfen, vorgestellt. Der Schwerpunkt liegt dabei auf jenen Techniken, die praktisch verwertbare Algorithmen hervorbringen. Daneben gibt es auch Verfahren, um nur zu zeigen, daß ein Problem einen parametrisierten Algorithmus besitzt, ohne zunächst auf die Effizienz zu achten. Schließlich gibt es noch Methoden, die nachweisen, daß ein Problem wahrscheinlich auch parametrisiert nicht schnell gelöst werden kann.