Aktuelle Themen der Theoretischen Informatik 1+2

“Feinkörnige Komplexität und Parameterisierte Algorithmen”

Diese Vorlesung behandelt aktuelle Forschungsthemen aus der theoretischen Informatik und richtet sich an Student:innen, die Algorithmen und theoretische Informatik gut finden. Es werden etwa hälftig algorithmische und komplexitätstheoretische Fragen und Ergebnisse abgedeckt. Vorrausgesetzt werden Grundbegriffe aus Algorithmen und Datenstrukturen sowie Grundwissen in diskreter Mathematik. Komplexitätstheorie und algorithmische Vertiefungsvorlesungen sind von Vorteil, werden aber nicht formal vorausgesetzt.

Vorlesungsmaterial

In Teil 1 folgen wir dem Buch “Parameterized Algorithms” [pdf]. Hier ist der (vorläufige) Plan:

In Teil 2 folgen wir in wesentlichen Teilen der Vorlesung von Bringmann/Künnemann (henceforth refered to as BK).

Weitere Details:

Inhalt

In dieser Vorlesung geht es um schnelle Algorithmen für “schwere” Berechnungsprobleme und immer auch um die Frage, ob noch schnellere Algorithmen möglich sind. Der Ausgangspunkt ist die Beobachtung, dass NP-Vollständigkeit und die Klassifikation von Problemen in Polynomialzeit und NP-schwer oft zu grobkörnig ist, um genaue Aussagen über die bestmöglich Laufzeit zu erzielen.

Wenn ein Algorithmus in Zeit (O(n^3)) läuft, ist dennoch von höchstem Interesse, ob es nicht einen cleveren und noch unbekannten Algorithmus geben könnte, der nur Zeit (O(n^{2.99})) oder (O(n)) braucht. Und nur weil ein Problem NP-schwer ist und damit keinen Polynomialzeitalgorithmus hat, heißt das noch lange nicht, dass man das Problem nicht gelöst haben möchte. Daher ist die Frage interessant, wie schnell man das Problem denn nun lösen kann: Vielleicht in Zeit (O(n^n)), (O(2^n)) oder gar (O(1.3^k n)) wo (k) ein weiterer Parameter der Eingabe ist?

Dieser Kurs vermittelt spannende algorithmische Techniken, um die Komplexität von NP-schweren und Polynomialzeitproblemen genauer zu analysieren. Die Übungen bilden einen wichtigen Teil der Veranstaltung: Darin werden Sie algorithmische Techniken selbständig anwenden und auch Komplexitätsannahmen benutzen, um zu zeigen, dass bestimmte Probleme keine schnelleren Algorithmen zulassen.

Lernziele

Nach der Veranstaltung kann der:die Student:in

Weitere Literatur: