Proseminar: Schwere Probleme und die Kunst der Reduktion

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.

• Kenntnisse aus den Vorlesungen „Algorithmen 1“ und „Theoretische Grundlagen der Informatik“ sind erforderlich.
• Die Kenntnis von Graphen, grundlegenden Algorithmentechniken und Komplexitätsklassen wird vorausgesetzt.

• Jede:r Teilnehmer:in erhält eine wissenschaftliche Quelle zur eigenhändigen Bearbeitung.
• Die Themen werden am ersten Termin, dem 20.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.

• Organisation: Torsten Ueckerdt und Thomas Bläsius
• Ort: Gebäude 50.34, Raum 301 (Am Fasanengarten 5, 76131 Karlsruhe).
• Zeit: Montags von 9:45 Uhr bis 11:15 Uhr.
• Sprache: Die Proseminarsprache ist Deutsch.

• Alle Plätze sind belegt.

• 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.

Änderungen vorbehalten.

Hier ein paar Informationen und Materialien für die Ausarbeitung:

• Beispiel Ausarbeitung für die Reduktion, die auch schon im Vortrags-Tutorial enthalten war. Orientiert euch sowohl vom groben Umfang als auch vom Schreibstil her gerne daran.
• Es gibt auch noch eine kommentierte Version der Ausarbeitung, mit vielen Anmerkungen dazu, warum Dinge so geschrieben wurde. (Beachte: funktioniert ggf. nicht gut, wenn der Bildschirm zu klein ist.)
• LaTeX Quellen der Beispielausarbeitung. Verwendet das bitte als Template für eure Ausarbeitung.
• Empfehlungen zum Schreiben einer mathematischen Ausarbeitung. Nicht spezifisch für unser Proseminar, enthält aber viele gute Hinweise.

• Thomas Bläsius
• Miriam Goetze
• Max Göttlicher
• Kolja Kühn
• Martin Schirneck
• Elly Schmidt
• Samuel Schneider
• Torsten Ueckerdt
• Jean-Pierre von der Heydt
• Marcus Wilhelm
• Wendy Yi
• Michael Zündorf