Vorlesung: Parametrisierte Algorithmen
Vorlesung: Parametrisierte Algorithmen
Turnus: 2-jährig
Ort, Uhrzeit:
Prüfungsgebiete:
Voraussetzung: Vordiplom
Beschreibung:
Viele praxisrelevante Probleme erweisen sich als NP-schwer, das heißt, für sie sind keine effizienten Algorithmen bekannt. In der Praxis wird zu ihrer Lösung daher meist auf heuristische Verfahren zurückgegriffen, die zwar oftmals ausreichend gute Laufzeiten bzw. Lösungen liefern, aber leider meist schwer durchschaubar sind und keine garantierten Aussagen über ihre Leistungsgüte erlauben.
Ein möglicher Ausweg kann in der Betrachtung von parametrisierter Komplexität bestehen: Bei vielen NP-schweren Problemen hängt das exponentielle Wachsen der Laufzeit nur von einem kleinen Teil der Eingabe, einem sogenannten Parameter, ab. Dies führt zum Konzept der parametrisierten Algorithmen, welche eine sinnvolle Alternative zu heuristischen Methoden darstellen können: falls die Werte der Parameter in konkreten Anwendungen des jeweiligen Problems klein sind, kann das exponentielle Wachstum gegebenenfalls in Kauf genommen werden und das Problem mit einem Fixed-Parameter-Algorithmus effizient gelöst werden.
In der Vorlesung werden einige interessante Methoden und Techniken zur Entwicklung effizienter parametrisierter Algorithmen vorgestellt. Andererseits werden wir uns mit der sog. parametrisierten Komplexitätstheorie beschäftigen, um die (wahrscheinlichen) Grenzen parametrisierter Algorithmen aufzeigen zu können.
Die Vorlesung besteht zum Teil aus integrierten Übungen, die freiwillig bearbeitet werden können und in der Vorlesung besprochen werden.
Voraussetzungen: Stoff der Grundstudiumsvorlesungen, insbesondere Algorithmen und etwas Komplexität. Es sind keine anderen Vorlesungen des Hauptstudiums Voraussetzung.
Literatur:
Rodney G. Downey, Michael R. Fellows: Parameterized Complexity, Springer-Verlag, 1999.
Jörg Flum, Martin Grohe: Parameterized Complexity Theory, Springer, 2006.
Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford Lecture Series in Mathematics and Its Applications, Oxford University Press, 2006.
Leistungsnachweise
wird noch bekanntgegeben