Parametrisierte Algorithmen (WS 2007/08)

Peter Rossmanith

Sprechstunde: Mittwochs 11-12 Uhr

Bereich

4+2 SWS Vorlesung im Bereich Theoretische Informatik

Zeit und Ort

Montags 8:30-10:00, Raum 5052
Freitags 12:00-13:30, Raum 5052

Übungsblätter

Die Übung findet jeweils montags von 14:00 bis 15:30 Uhr im Seminarraum I1 (Gebäude E1, Raum 4017) statt.

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.

Voraussetzungen

Vordiplom.

Literatur

Das Standardbuch zu diesem Themengebiet ist die Monographie von Downey und Fellows (s.u.). Dieses Buch liegt im Semesterapparat in der Informatikbibliothek aus. Die Folien sind hier.