Institut für Theoretische Informatik, Algorithmik

Proseminar: Algorithmen für NP-schwere Probleme

im Sommersemester 2022

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 wurde eingerichtet.
  • Die Themen wurden zugeteilt.
  • Hier gibt es nun einen Link zu unserem Ipe-Tutorial.

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

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 Ausarbeitungen sind spätestens am 11.7. für Feedback an den jeweiligen Betreuer abzugeben. Die finale Abgabe erfolgt am 29. Juli (eine Woche später als ursprünglich angekündigt).
  • 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 25.04. Einführung und Themenvergabe Torsten
2 02.05. "How to Vortrag" Torsten
3 09.05. Kurzvorträge alle
4 23.05. Tim Zeitz, M.Sc. 1. Introduction and Definitions Henriette
Buch Kapitel 1, Seite 3-14
23.05. Matthias Wolf, M.Sc. 2. Kernelization Markus
Buch Kapitel 2.1 und 2.2, Seite 17-26
5 30.05. Laura Merker 3. Other Kernelization Techniques Darius
Buch Kapitel 2.3, 2.4 und 2.6, Seite 26-33 und 38-39
30.05. Christopher Weyand 4. Bounded Search Trees Maxim
Buch Kapitel 3 außer 3.4, Seite 51-60 und 67-69
6 13.06. Max Göttlicher 5. Parametrized Algorithms from LP-Relaxations Illia
Buch Kapitel 2.5 und 3.4, Seite 33-38 und 60-67
13.06. Maximilian Katzmann 6. Iterative Compression Eileen
Buch Kapitel 4 bis inklusive 4.3.1, Seite 77-88
7 20.06. Sascha Gritzbach, M.Sc. 7. Randomized Methods Kedi
Buch Kapitel 5 bis inklusive 5.3, Seite 99-108
20.06. Adrian Feilhauer 8. Chromatic Coding and Derandomization Mark
Buch Kapitel 5.5 und 5.6, Seite 113-122 außer Seite 120
8 27.06. Torsten Ueckerdt 9. Introduction to Treewidth Lars
Buch Kapitel 7 bis inklusive 7.2, Seite 151-162
27.06. Paul Jungeblut 10. Treewidth and Dynamic Programming Lena
Buch Kapitel 7.3, außer 7.3.3, Seite 162-171
9 04.07. Jonas Sauer, M.Sc. 11. Treewidth and Monadic Second-Order Logic Jonas
Buch Kapitel 7.4, Seite 177-184
04.07. Marcus Wilhelm 12. Computing Treewidth Dominik
Buch Kapitel 7.6, Seite 190-199

Änderungen vorbehalten.

Vorlagen

Betreuung