Algorithmen für schwierige Probleme

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.

 

Es gibt ein Vorlesungsskript.