Proseminar: Schwere Probleme und die Kunst der Reduktion
im Sommersemester 2025
Thema
Die Berechnungskomplexität eines Problems ist eines der zentralen Konzepte in der Algorithmik. Neben dem Entwurf von effizienten Algorithmen sind auch theoretisch beweisbare untere Schranken für die Komplexität eines Problems von essentieller Bedeutung. Dies erlaubt unter anderem die Einteilung von Problemen in Komplexitätsklassen wie P, NP oder beispielsweise PSPACE. Untere Schranken, also die Schwere eines Problems, werden mit Reduktionen bewiesen. Eine Reduktion transformiert allgemeine Instanzen eines bekannt schweren Problems in äquivalente spezielle Instanzen des betrachteten Problems. Neben den klassischen polynomiellen Reduktionen und der dazugehörigen NP-Schwere, gibt es eine Vielzahl von weiteren Komplexitätsklassen und entsprechenden Reduktionen. Eine Reduktion für ein neues Problem zu finden erfordert sowohl die Kenntnis von geeigneten schweren Problemen, als auch eine gewisse Erfahrung in der Entwicklung von Reduktionen. In diesem Proseminar werden beide Bereiche durch eine Vielzahl von Beispielen gezielt gestärkt.
Aktuelles
- Die Homepage wurde eingerichtet.
- Ein ILIAS-Kurs wurde angelegt.
Voraussetzungen
- Kenntnisse aus den Vorlesungen „Algorithmen 1“ und „Theoretische Grundlagen der Informatik“ sind erforderlich.
- Die Kenntnis von Graphen, grundlegenden Algorithmentechniken und Komplexitätsklassen wird vorausgesetzt.
Quellen und Betreuung
- Jede:r Teilnehmer:in erhält eine wissenschaftliche Quelle zur eigenhändigen Bearbeitung.
- Die Themen werden am ersten Termin, dem 28.4. vorgestellt und verteilt.
- Jede:r Teilnehmer:in wird von einer/m Mitarbeiter:in betreut. Die Mitarbeiter:innen stehen für Fragen und Hinweise nach voriger Absprache zur Verfügung.
Allgemeines
- Organisation: Torsten Ueckerdt und Thomas Bläsius
- Zeit: Montags von 9:45 Uhr bis 11:15 Uhr.
- Sprache: Die Proseminarsprache ist Deutsch.
Anmeldung
- Alle Plätze sind belegt.
Ablauf
- Jede:r Seminarteilnehmer:in hält einen 35-minütigen Vortrag im Proseminar und steht danach für Fragen der Teilnehmer:innen zur Verfügung.
- Eine regelmäßige Teilnahme am Seminar wird vorausgesetzt.
- Spätestens zwei Wochen vor dem Vortragstermin ist das Vortragskonzept mit der/m jeweiligen Betreuer:in zu besprechen.
- Ein vorläufiger Foliensatz ist eine Woche vor dem Vortrag bei dem/der jeweiligen Betreuer:in abzugeben.
- Die Ausarbeitungen sind vorab (genauer Termin wird noch festgelegt) für Feedback an die/den jeweilige:n Betreuer:in abzugeben. Der Termin für die finale Abgabe wird noch bekanntgegeben.
- 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 | 21.04. | – | – | – |
| 2 | 28.04. | – | Einführung und Themenvergabe | Torsten Ueckerdt und Thomas Bläsius |
| 3 | 05.05. | – | Vortrags-Tutorial, Ipe-Einführung | Thomas Bläsius [Torsten, Marcus] |
| 4 | 12.05. | – | – | – |
| 5 | 19.05. | – | Kurzvorträge | alle |
| 6 | 26.05. | – | – | – |
| 7 | 02.06. | Adrian Feilhauer | (1) Mutual Planar Duality | tba |
| Laura Merker | (2) The Price of Upwardness | tba | ||
| 8 | 09.06. | – | – | – |
| 9 | 16.06. | Samuel Schneider | (3) Tiling with Three Polygons | tba |
| Jean-Pierre von der Heydt | (4) FRACTRAN | tba | ||
| 10 | 23.06. | Thomas Bläsius | (5) T-Level Planarity | tba |
| Michael Zündorf | (6) Partial Order Dimension | tba | ||
| 11 | 30.06. | Kolja Kühn | (7) GO is Polynomial-Space Hard | tba |
| Torsten Ueckerdt | (8) Intersection Graphs of Segments and ER | tba | ||
| 12 | 07.07. | Wendy Yi | (9) Binary Space Partitions in the Plane | tba |
| Miriam Goetze | (10) Non-Crossing Connectors | tba | ||
| 13 | 14.07. | Max Göttlicher | (11) Normalisierung von Schaltkreisen | tba |
| Marcus Wilhelm | (12) Graph Diameter and SETH | tba | ||
| 14 | 21.07. | – | – | – |
| 15 | 28.07. | – | – | – |
Änderungen vorbehalten.
Vorlagen
Eine LaTeX-Vorlage für die Ausarbeitung wird hier demnächst nachgereicht.