Proseminar: Algorithmen für NP-schwere Probleme
im Sommersemester 2022
Thema
Wir beschäftigen uns mit der Technik der parametrisierten Algorithmen (fixed parameter tractability) bei denen NP-vollständige Probleme effizient gelöst werden sollen. Die Effizienz bezieht sich hier auf eine polynomielle Laufzeit hinsichtlich der Größe der Instanz wenn ein zusätzlicher Parameter der Instanz als konstant angenommen werden darf. Wir betrachten vor allem Graphenprobleme. Hier könnte der zusätzliche Parameter beispielsweise der Maximalgrad sein.
Aktuelles
- Die Homepage wurde eingerichtet.
- Die Themen wurden zugeteilt.
- Hier gibt es nun einen Link zu unserem Ipe-Tutorial.
Voraussetzungen
- Dieses Proseminar basiert auf und vertieft algorithmische Kenntnisse aus der Vorlesung „Theoretische Grundlagen der Informatik“.
- Die Kenntnis von Graphen, grundlegenden Algorithmentechniken und Komplexitätsklassen wird vorausgesetzt.
Quellen und Betreuung
- Jeder Teilnehmer erhält ein Auszug aus einem Buch zur eigenhändigen Bearbeitung.
- Das Proseminar basiert auf dem Buch Parametrized Algorithms von Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk und Saurabh, erhältlich als E-Ressource in der KIT-Bibliothek: https://services.bibliothek.kit.edu/primo/start.php?recordid=KITSRC455177058
- Die Themen werden am ersten Termin, dem 25.4. vorgestellt und verteilt.
- Jeder Teilnehmer wird von einem Mitarbeiter betreut. Dieser Mitarbeiter steht für Fragen und Hinweise nach voriger Absprache zur Verfügung.
- Das Proseminar wird von Adrian Feilhauer, Laura Merker, Torsten Ueckerdt und Christopher Weyand geleitet.
Allgemeines
- Zeit: Montags von 11:30 Uhr bis 13:00 Uhr.
- Sprache: Die Proseminarsprache ist Deutsch.
Anmeldung
- Alle Plätze sind belegt.
Ablauf
- Jeder Seminarteilnehmer hält einen fünfminütigen Kurzvortrag und einen 35-minütigen Vortrag im Proseminar und steht danach für Fragen der Teilnehmer zur Verfügung.
- Eine regelmäßige Teilnahme am Seminar wird vorausgesetzt.
- Spätestens zwei Wochen vor dem Vortragstermin ist das Vortragskonzept mit dem jeweiligen Betreuer zu besprechen.
- Ein vorläufiger Foliensatz ist eine Woche vor dem Vortrag beim jeweiligen Betreuer abzugeben.
- Die Ausarbeitungen sind spätestens am 11.7. für Feedback an den jeweiligen Betreuer abzugeben. Die finale Abgabe erfolgt am 29. Juli (eine Woche später als ursprünglich angekündigt).
- Die Seminarnote ergibt sich aus der Note für den Vortrag und die Ausarbeitung, sowie der Beteiligung am Seminar.
Zeitplan
| # | Termin | Betreuung | Thema | Vortragende |
|---|---|---|---|---|
| 1 | 25.04. | – | Einführung und Themenvergabe | Torsten |
| 2 | 02.05. | – | "How to Vortrag" | Torsten |
| 3 | 09.05. | – | Kurzvorträge | alle |
| 4 | 23.05. | Dr. Tim Zeitz | 1. Introduction and Definitions | Henriette |
| Buch Kapitel 1, Seite 3-14 | ||||
| 23.05. | Dr. Matthias Wolf | 2. Kernelization | Markus | |
| Buch Kapitel 2.1 und 2.2, Seite 17-26 | ||||
| 5 | 30.05. | Laura Merker | 3. Other Kernelization Techniques | Darius |
| Buch Kapitel 2.3, 2.4 und 2.6, Seite 26-33 und 38-39 | ||||
| 30.05. | Christopher Weyand | 4. Bounded Search Trees | Maxim | |
| Buch Kapitel 3 außer 3.4, Seite 51-60 und 67-69 | ||||
| 6 | 13.06. | Max Göttlicher | 5. Parametrized Algorithms from LP-Relaxations | Illia |
| Buch Kapitel 2.5 und 3.4, Seite 33-38 und 60-67 | ||||
| 13.06. | Maximilian Katzmann | 6. Iterative Compression | Eileen | |
| Buch Kapitel 4 bis inklusive 4.3.1, Seite 77-88 | ||||
| 7 | 20.06. | Dr. Sascha Gritzbach | 7. Randomized Methods | Kedi |
| Buch Kapitel 5 bis inklusive 5.3, Seite 99-108 | ||||
| 20.06. | Adrian Feilhauer | 8. Chromatic Coding and Derandomization | Mark | |
| Buch Kapitel 5.5 und 5.6, Seite 113-122 außer Seite 120 | ||||
| 8 | 27.06. | Torsten Ueckerdt | 9. Introduction to Treewidth | Lars |
| Buch Kapitel 7 bis inklusive 7.2, Seite 151-162 | ||||
| 27.06. | Paul Jungeblut | 10. Treewidth and Dynamic Programming | Lena | |
| Buch Kapitel 7.3, außer 7.3.3, Seite 162-171 | ||||
| 9 | 04.07. | Jonas Sauer | 11. Treewidth and Monadic Second-Order Logic | Jonas |
| Buch Kapitel 7.4, Seite 177-184 | ||||
| 04.07. | Marcus Wilhelm | 12. Computing Treewidth | Dominik | |
| Buch Kapitel 7.6, Seite 190-199 |
Änderungen vorbehalten.
Vorlagen
- Bitte verwenden Sie diese LaTeX-Vorlage für die Ausarbeitung.