Effiziente Algorithmen und Komplexitätstheorie

Diese Vorlesung hat im Wintersemester den Schwerpunkt Komplexitätstheorie und im Sommersemester den Schwerpunkt Effiziente Algorithmen. Ein Besuch beider Vorlesungen ist sinnvoll und für eine Spezialisierung in diesen Bereichen sehr nützlich.

Vorlesungsinhalt

Effiziente Algorithmen werden in vielen Bereichen der Informatik und in anderen Wissenschaften benötigt. So besteht z. B. der wichtigste Beitrag der Informatik zur Genomforschung in der Bereitstellung guter Algorithmen. Der Entwurf effizienter Algorithmen ist eine Disziplin, bei der Kenntnisse in dem Gebiet, aus dem das betrachtete Problem stammt, Intuition, Fingerspitzengefühl und Entwurfsmethoden für effiziente Algorithmen zusammenspielen. Letztere werden an praktisch relevanten Beispielen in der Vorlesung gelehrt. Hinzu kommen Methoden zur Analyse der untersuchten Algorithmen. In der Vorlesung werden die wichtigsten Algorithmentypen behandelt:

Algorithmen, die Probleme für jede Eingabe korrekt und mit geringer Worst-Case-Rechenzeit lösen (grundlegende Graphenprobleme, Mustererkennung, Beispiele aus der Bioinformatik, Maximierung von Flüssen in Netzwerken)
Algorithmen, die Optimierungsprobleme fast exakt oder einigermaßen exakt lösen, aber eine geringe Worst-Case-Rechenzeit haben (Optimale Touren, Rucksackproblem)
Randomisierte Algorithmen, die eine geringe Worst-Case-Rechenzeit haben, aber mit kleiner Wahrscheinlichkeit ein falsches Ergebnis liefern (Primzahltest)
Heuristische Algorithmen, die das Problem lösen und hoffentlich in vielen Fällen eine geringe Rechenzeit haben (Optimale Touren, Rucksackproblem)

Dabei kommen allgemeine Entwurfsmethoden wie dynamische Programmierung oder Branch-and-Bound ebenso zur Sprache wie verallgemeinerbare Tricks zum Entwurf effizienter Algorithmen. Der Schwerpunkt der Vorlesung besteht darin, die Hörerinnen und Hörer in die Lage zu versetzen, in vergleichbaren Situationen selbst effiziente Algorithmen entwerfen und analysieren zu können. Nebenbei werden die besten bekannten Algorithmen für zentrale Probleme vorgestellt.