Klausur (mündliche Prüfung bei geringer Teilnehmeranzahl)

Dieses Modul gibt eine Einführung in die Theorie der parametrisierten Algorithmen und der parametrisierten Komplexitätstheorie. Der Schwerpunkt liegt dabei auf unterschiedlichen Methoden und Techniken zur Entwicklung von parametrisierten Algorithmen. In diesem Modul wird in Lösungsansätze für NP-vollständige Probleme, Parametrisierte Algorithmen und Problemkerne eingeführt. Verschiedene Methoden und Techniken, wie z. B. Datenreduktion und Problemkerne, Tiefenbeschränkte Suchbäume, Dynamisches Programmieren, Baumzerlegungen, Iterative Kompression, Farbkodierung und Lineare Programmierung, werden vorgestellt. Aus dem Bereich der Parametrisierten Komplexitätstheorie werden Parametrisierte Reduktion, die Klasse FPT und Härte-Klassen behandelt.

Die Studierenden besitzen Basiswissen über parametrisierte Algorithmen und parametrisierte Komplexität und können die Schwierigkeit NP-vollständiger Probleme und Algorithmen zur exakten Lösung von diesen einschätzen und bestimmen. Sie kennen unterschiedliche Methoden und Techniken zum Entwurf von parametrisierten Algorithmen. Sie können verschiedene Probleme mit dem vorgestellten Repertoire an Methoden lösen sowie selbständig parametrisierte Algorithmen kreativ entwickeln. Die Studierenden können zwischen verschiedenen Strategien zum Entwurf parametrisierter Algorithmen unterscheiden und diese an das Problem angepasst anwenden. Die Studierenden sind in der Lage, einen parametrisierten Algorithmus kritisch zu bewerten. Sie erkennen Vor- und Nachteile dieses Ansatzes und können ihn in den Kontext anderer Methoden zur Lösung NP-vollständiger Probleme wie Heuristiken, Approximationsalgorithmen, Randomisierte Algorithmen einordnen.

Rolf Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press.
Rodney G. Downey, Michael R. Fellows: Parameterized Complexity, Springer-Verlag, 1999.
Jörg Flum, Martin Grohe: Parameterized Complexity Theory, Springer-Verlag, 2006.