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 und Thomas Bläsius |
| 3 | 05.05. | – | Ipe-Tutorial | tba |
| 4 | 12.05. | – | – | – |
| 5 | 19.05. | – | – | – |
| 6 | 26.05. | – | – | – |
| 7 | 02.06. | – | Vortrag Thema 1 | tba |
| – | Vortrag Thema 2 | tba | ||
| 8 | 09.06. | – | – | – |
| 9 | 16.06. | – | Vortrag Thema 3 | tba |
| – | Vortrag Thema 4 | tba | ||
| 10 | 23.06. | – | Vortrag Thema 5 | tba |
| – | Vortrag Thema 6 | tba | ||
| 11 | 30.06. | – | Vortrag Thema 7 | tba |
| – | Vortrag Thema 8 | tba | ||
| 12 | 07.07. | – | Vortrag Thema 9 | tba |
| – | Vortrag Thema 10 | tba | ||
| 13 | 14.07. | – | Vortrag Thema 11 | tba |
| – | Vortrag Thema 12 | tba | ||
| 14 | 21.07. | – | – | – |
| 15 | 28.07. | – | – | – |
Änderungen vorbehalten.
Vorlagen
- Bitte verwenden Sie diese LaTeX-Vorlage für die Ausarbeitung.