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 Homepage ist online.

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 Papier oder Buchkapitel zur eigenhändigen Bearbeitung.
  • 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.

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 Torsten
2 13.05. Kurzvorträge alle
3 20.05. „How to Vortrag“ und IPE-Tutorial Torsten
4 27.05. tba Introduction and Definitions tba
27.05. tba Kernelization tba
5 03.06. tba Other Kernelization Techniques tba
03.06. tba Bounded Search Trees tba
6 17.06. tba Parametrized Algorithms from LP-Relaxations tba
17.06. tba Iterative Compression tba
7 24.06. tba Randomized Methods tba
24.06. tba Chromatic Coding and Derandomization tba
8 08.07. tba Introduction to Treewidth tba
08.07. tba Treewidth and Dynamic Programming tba
9 15.07. tba Treewidth and Monadic Second-Order Logic tba
15.07. tba Computing Treewidth tba

Änderungen vorbehalten.

Betreuung