Algorithmen für schwierige Probleme

Inhalt

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. In der Vorlesung werden wir einige algorithmische Methoden erklären, die eine Alternative zu den heuristischen Verfahren darstellen, wie approximative Algorithmen oder Algorithmen mit moderater exponentieller Komplexität. Ein weiterer Ausweg, der es erlaubt, mit NP-harten Problemen umzugehen, sind parametrisierte Algorithmen. 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: 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 parametrisierter und approximativer Algorithmen vorgestellt. Andererseits werden wir uns mit der Komplexitätstheorie beschäftigen, die sich mit solchen Algorithmen befasst.

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.

Literatur

R. Downey, M. Fellows: Parameterized Complexity, Springer-Verlag, 1999.
F. Fomin and D. Kratsch: Exact Exponential Algorithms, Springer, 2010
R. Motwani, P. Raghavan: Randomized Algorithms. Cambridge University Press, 1995.
R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006
U. Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
C.H. Papadimitriou: Computational Complexity. Addison-Wesley, 1994.

Skript/Folien

Teile der Vorlesung gibt es hier als Folien, die Tafelanschriebe als handschriftliches Skript.

Folien vom 19.10.2011 (Übersicht, Motivation)

Folien vom 20.10.2011 (Komplexität, Grundlagen Parametrisierte Algorithmen)

Folien vom 26.10.2011 (Wiederholungstest zu FPT. Datenreduktion) und Zusatztest (P, NP)

Folien vom 27.10.2011 (Wiederholung zur Datenreduktion von MAXSAT)

Folien vom 2.11.2011 (Wiederholungstest zu FPT und Problemkernen, Kronenregel, Übersicht Datenreduktion)

Folien vom 3.11.2011 (Wiederholungstest FPT/Problemkern, Suchbaumalgorithmus für CENTER STRING)

Folien vom 9.11.2011 (Wiederholungstest und Übungen zu Suchbäumen)

Folien vom 10.11.2011 (Rekursionen, Branching number, Verflechtung von Datenreduktion und Problemkernen, Übersicht Suchbäume) und ausgefülltes Blatt zur Verbesserung des Suchbaums für VERTEX COVER

Folien vom 16.11.2011 (ILP) und zusätzliches Beispiel (MTO, ILP, Suchbaum, Konfliktgraph)

Folien vom 17.11.2011 (Übung zu Suchbäumen)

Folien vom 23.11.2011 (Dynamisches Programmieren, Farbkodierung, LONGEST PATH)

Folien vom 24.11.2011 (Farbkodierung, LONGEST PATH, Baumzerlegung, Baumweite, Robber-Cop mit Übungen)

Folien vom 30.11.2011 (Wiederholungstest zu Baumzerlegungen, Algorithmus für VERTEX COVER mit Baumzerlegung)

Folien vom 1.12.2011 (Wiederholungstest zu Baumweite und Vertex-Cover-Zahl, Übersicht über alle bisherigen Methoden, Einstieg parametrisierte Komplexitätstheorie)

Folien vom 7.12.2011 (Parametrisierte Reduktion, Klassen W[1] und W[2], Übersicht, Zusammenfassung, Ausblick)