Parameterisierte Algorithmen

(Vorlesung mit Übungen)

Wohl jeder angehende Informatiker hat schon von der P/NP-Problematik gehört. Vereinfa- chend gesprochen folgt aus der Annahme, dass sich Probleme, die mit nichtdeterministi- schen Maschinen in Polynomzeit lösbar sind, eben nicht mit deterministischen Maschinen in Polynomzeit lösen lassen: Zur exakten Lösung NP-harter Probleme wir superpolynomielle Zeit benötigt. Allerdings tauchen NP-harte Probleme in großer Zahl in unterschiedlichsten Anwendungen auf. Hier hilft es dem Praktiker nichts zu hören, dass sein Problem NP-hart ist und daher “praktisch” nicht mit Rechnerhilfe lösbar ist. Im Gegenteil lehrt die Erfah- rung, dass durch ingenieursmäßige Herangehensweise an solche Probleme oft sehr schnell exakte Lösungen für NP-harte Probleminstanzen gefunden werden können. Lässt sich dieser scheinbare Widerspruch auflösen? Diese Fragestellung ist einer der möglichen Zugänge zur parameterisierten Algorithmik. Konkret würde hier nun versucht, typische Teile der Eingabe zu beschreiben, die in den vorkommenden Instanzen “klein” sind und daher eine exponenti- elle Verknüpfung mit der Laufzeit des Algorithmus “vertragen”. Formaler ausgedrückt, versuchen wir eine zweidimensionale Sicht auf Probleminstanzen zu entwickeln: neben der Gesamtgröße n der Eingabe fließt ein Teil der Eingabe als so genannter Parameter k ein. Wir werden an zahlreichen Beispielen Techniken einüben, um möglichst gute parameterisierte Algorithmen aufzufinden: neben Suchbäumen sind hier sogenannte pa- rameterisierte Kerne, Umparameterisierungen und Graphparameter zu nennen. Die Analyse der entsprechenden Algorithmen stellt auch ein besonderes Teilgebiet dar. Daneben werden wir auch die “harten” Seiten dieser Theorie kennenlernen.

 

Teilnahmevoraussetzungen

Kenntnisse, die einem Bachelor-Abschluss in Informatik entsprechen.

Die parallel angebotene Veranstaltung "Komplexitätstheorie B" ist eine gute Ergänzung zu dieser mehr algorithmisch orientierten Vorlesung.