Institut für Theoretische Informatik, Algorithmik

Proseminar: Algorithmen für NP-schwere Probleme

im Sommersemester 2021

Thema

Wir beschäftigen uns mit Approximationsalgorithmen für NP-schwere Probleme. Diese Algorithmen zeichnen sich dadurch aus, dass sie Lösungen berechnen, für deren Güte Garantieren bewiesen werden können. Wir decken dabei sowohl verschiedene Probleme als auch verschiedene Techniken des Algorithmendesigns ab.

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 Approximation Algorithms von Vijay V. Vasirani.
  • Die Themen werden am ersten Termin, dem 12.04. bekanntgegeben und verteilt.
  • Jeder Teilnehmer wird von einem Mitarbeiter betreut. Dieser Mitarbeiter steht für Fragen und Hinweise nach voriger Absprache zur Verfügung.

Allgemeines

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. Außerdem erstellt jeder Teilnehmer eine Ausarbeitung im Umfang von 10 Seiten.
  • 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 zwei Wochen nach dem Vortrag für Feedback an den jeweiligen Betreuer abzugeben. Die finale Abgabe erfolgt eine Woche nach Erhalt des Feedbacks.
  • Die Seminarnote ergibt aus der Note für den Vortrag und die Ausarbeitung, sowie der Beteiligung am Seminar.

Zeitplan

# Termin Betreuung Thema Vortragende
1 12.04. Einführung und Themenvergabe
2 19.04. „How to Vortrag“ und IPE-Tutorial Torsten, Matthias
3 26.04. Kurzvorträge alle
4 03.05. Einführung in lineare Programme und Dualität Thomas
5 10.05. 1. TBD TBD
10.05. 2. TBD TBD
6 17.05. 3. TBD TBD
17.05. 4. TBD TBD
7 31.05. 5. TBD TBD
31.05. 6. TBD TBD
8 07.06. 7. TBD TBD
07.06. 8. TBD TBD
9 14.06. 9. TBD TBD
14.06. 10. TBD TBD
10 21.06. 11. TBD TBD
21.06. 12. TBD TBD

Änderungen vorbehalten.