FS 2023 — Dr. H.-J. Böckenhauer, Prof. Dr. D. Komm
Algorithmik für schwere Probleme
Inhalt der Vorlesung
Diese Lerneinheit beschäftigt sich mit algorithmischen Ansätzen zur Lösung schwerer Probleme, insbesondere mit parametrisierten Algorithmen und exakten Exponentialzeitalgorithmen.
Termine
Die Vorlesung wird nicht aufgezeichnet.
| Vorlesung | Dienstag | 9‑11 | CAB G 59 | Beginn: 21. Februar 2023 |
| Übungen | Dienstag | 11‑12 | CAB G 59 | Beginn: 28. Februar 2023 |
Vorlesungsinhalt
Die Kapitelangaben beziehen sich auf die zur Verfügung gestellten Skriptentwürfe.
- 21.02.2023. Allgemeine Einführung, pseudopolynomieller Algorithmus für das Rucksackproblem. (Abschnitt 4.1, 4.2)
- 28.02.2023. Starke NP-Schwere, Einführung in parametrisierte Algorithmen, Kernbildung, einfache Kernbildung für Vertex-Cover. (Abschnitt 4.4, 6.1, 6.2.1)
- 07.03.2023. Zusammenhang zwischen Kernbildung und fpt-Algorithmen, Kernbildung für Edge-Clique-Cover, Crown-Decompositions: Definition und Anwendung für Vertex-Cover (Beginn). (Abschnitt 6.2.2, 6.2.3)
- 14.03.2023. Crown-Decompositions: Anwendung für Vertex-Cover (Rest), Tiefenbeschränkte Suchbäume (Vertex-Cover und Cluster-Editing). (Abschnitt 6.3)
- 21.03.2023. Iterative Kompression am Beispiel von Vertex-Cover, Steinerbaum-Problem. (Abschnitt 6.4.1, 6.5)
- 28.03.2023. Baumweite (Einführung und Baumweite spezieller Graphklassen). (Abschnitt 6.6.1)
- 04.04.2023. FPT-Algorithmus für Vertex-Cover bezüglich Baumweite. (Abschnitt 6.6.2)
- 18.04.2023. Grenzen der Parametrisierbarkeit, exakte Exponentialzeitalgorithmen (Einführung und 3SAT). (Abschnitt 6.7 bis und mit Conjecture 6.1)
- 25.04.2023. Exakter Algorithmus für Max-IS. (Abschnitt 5.1, 5.2)
- 02.05.2023. Dynamisches Programmieren für TSP. Algorithmen für Graph Coloring. (Abschnitt 5.3.1, 5.3.2, 5.5.1)
- 09.05.2023. Measure-und-Conquer-Methode und Anwendung für Max-IS, Schönings Algorithmus. (Abschnitt 5.5.2, 9.8)
- 16.05.2023. Derandomisierung von Schönings Algorithmus (Überblick). (Abschnitt 9.9.3, bis und mit Lemma 9.6)
- 23.05.2023. Derandomisierung von Schönings Algorithmus. (Abschnitt 9.9.3)
- 30.05.2023. Approximationsalgorithmen. (Abschnitt 7.2, 7.3.4, 7.5.3, 7.6.1)
Prüfungsstoff
Der Prüfungsstoff umfasst alles, was in der Vorlesung behandelt wurde, sowie den Stoff der Übungsblätter und Lösungen.
Skripte
Unter Algorithmics for Hard Problems stehen Entwürfe von Skripten zu folgenden Vorlesungsteilen zur Verfügung:
- Parametrisierte Algorithmen
- Exakte Exponentialzeitalgorithmen
- Gemeinsame Analyse verschiedener Probleme
- Approximationsschemata für das Rucksackproblem
Das Passwort für den Zugriff wird den Teilnehmenden per E-Mail mitgeteilt.
Übungen
Die Übungen werden von Moritz Stocker () betreut. Die Abgaben der Lösungen können per E-Mail an ihn gesendet werden, er steht auch für Fragen zum Inhalt und zur Organisation der Übungen zur Verfügung.
| Datum | Übung | Lösung |
|---|---|---|
| 21.02.2023 | Übungsblatt 1 | Lösung 1 |
| 28.02.2023 | Übungsblatt 2 | Lösung 2 |
| 07.03.2023 | Übungsblatt 3 | Lösung 3 |
| 14.03.2023 | Übungsblatt 4 | Lösung 4 |
| 21.03.2023 | Übungsblatt 5 | Lösung 5 |
| 28.03.2023 | Übungsblatt 6 | Lösung 6 |
| 04.04.2023 | Übungsblatt 7 | Lösung 7 |
| 18.04.2023 | Übungsblatt 8 | Lösung 8 |
| 25.04.2023 | Übungsblatt 9 | Lösung 9 |
| 02.05.2023 | Übungsblatt 10 | Lösung 10 |
| 09.05.2023 | Übungsblatt 11 | Lösung 11 |
| 16.05.2023 | Übungsblatt 12 | Lösung 12 |
| 23.05.2023 | Übungsblatt 13 | Lösung 13 |
Literatur
- J. Hromkovič: Algorithmics for Hard Problems, 2004, Springer-Verlag, ISBN 3-540-44134-4.
- F. Fomin und D. Kratsch: Exact Exponential Algorithms, 2010, Springer-Verlag, ISBN 978-3-642-16532-0.
- R. Niedermeier: Invitation to Fixed-Parameter Algorithms, 2006, Oxford University Press, ISBN 978-0-19-856607-6.
- M. Cygan et al.: Parameterized Algorithms, 2015, Springer-Verlag, ISBN 978-3-319-21275-3.
Kontakt: Dr. Moritz Stocker, ; letzte Änderung: ; Haftungsausschluss.