Institut für Theoretische Informatik, Algorithmik

Proseminar: Algorithmen für NP-schwere Probleme

im Sommersemester 2019

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 Themen sind verteilt; die Homepage wurde dahingehend aktualisiert.

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 29.4. bekanntgegeben 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 Torsten Ueckerdt geleitet.

Allgemeines

Anmeldung

  • Alle Plätze sind belegt.
  • Teilnehmer melden sich bitte unter der Prüfungsnummer 7500173 („Proseminar Algorithmen für NP-schwere Probleme“) verbindlich für das Seminar an.

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 Seminarnote ergibt aus der Note für den Vortrag und Kurzvortrag, sowie der Beteiligung am Seminar.

Zeitplan

# Termin Betreuung Thema Vortragende
1 29.04. Einführung und Themenvergabe pdf Torsten
2 13.05. Kurzvorträge pdf alle
3 20.05. „How to Vortrag“ pdf und IPE-Tutorial Torsten
4 27.05. Valentin 1. Introduction and Definitions Max N.
27.05. 2. Kernelization Torsten
5 03.06. Lukas 3. Other Kernelization Techniques Liran
03.06. Lars 4. Bounded Search Trees Vera
6 17.06. Franziska, Matthias 5. Parametrized Algorithms from LP-Relaxations Christian
17.06. Guido 6. Iterative Compression Calvin
7 24.06. Sascha 7. Randomized Methods Luc
24.06. Marcel 8. Chromatic Coding and Derandomization Patrick
8 08.07. Tamara 9. Introduction to Treewidth Max B.
08.07. Torsten 10. Treewidth and Dynamic Programming Miriam
9 15.07. Jonas 11. Treewidth and Monadic Second-Order Logic Nicholas
15.07. Tobias 12. Computing Treewidth Dominik

Änderungen vorbehalten.

Betreuung