| Parametrisierte Komplexität | |||
| Studiengänge Mathematik 6. Semester (PO 2023) Mathematik Bachelor 6. Semester Wirtschaftsmathematik 6. Semester (PO 2023) Wirtschaftsmathematik Bachelor 6. Semester Angewandte Mathematik Master | |||
| |||
| Lehrinhalt: Die Parametrisierte Komplexität hat sich in den letzten 30 Jahren zu einem der Mainstream-Themen in der Theoretischen Informatik und Algorithmischen Graphentheorie entwickelt. Statt wie in der klassischen Komplexitätstheorie die Laufzeit von Algorithmen allein in Abhängigkeit von der Eingabegröße zu beschreiben, liefert die Parametrisierte Komplexität eine feinere Analyse, indem sie zusätzliche Parameter der Eingabe bei der Laufzeit berücksichtigt. Damit ermöglicht sie Algorithmen für NP-vollständige Probleme, die für eine große Menge von Instanzen effizient arbeiten. In dieser Vorlesung werden wir die grundlegenden Techniken dieses Forschungsfeldes vorstellen. Neben algorithmischen Ergebnissen beschäftigen wir uns auch mit Schwere-Resultaten und unteren Schranken für Laufzeiten. | |||
|