Scalable Algorithms (ITI)

Parametrisierte Algorithmen

Dozent: Thomas Bläsius

Übungsleiter: Marcus Wilhelm

Sehr viele in der Praxis auftretende Probleme sind NP-schwer und damit im Allgemeinen (vermutlich) nicht in polynomieller Zeit lösbar. Dennoch können diese Probleme häufig effizient gelöst werden, da die Eingaben “gutartig” sind. Eine Möglichkeit diese Gutartigkeit der Instanzen formal zu fassen bietet die Betrachtung der parametrisierten Komplexität. Dabei assoziiert man mit jeder Instanz einen Parameter k, der ein Maß für die Komplexität der Eingabe darstellt. Ziel ist es dann, einen Algorithmus zu finden, dessen Laufzeit nur polynomiell von der Eingabegröße n aber ggf. exponentiell von dem Parameter k abhängt. Im Vergleich zur groben Klassifizierung eines Problems als polynomiell lösbar bzw. NP-schwer bietet die parametrisierte Betrachtungsweise eine deutlich differenziertere Sicht auf schwere Probleme.

Link zum Vorlesungsverzeichnis: https://campus.studium.kit.edu/events/catalog.php#!campus/all/event.asp?gguid=0x7E87942CDA194AB08ECD78C1D78B1A9A
Discord Server: https://discord.gg/kFpseagY

Ablauf

Wir treffen uns jede Woche montags um 15:45 und donnerstags um 14:00 Uhr in Raum 301. Die erste Vorlesung wird am Montag den 24.10. um 15:45 stattfinden.

Prüfung

Die mündlichen Prüfungen werden am Donnerstag den 2. März und am Mittwoch den 5. April stattfinden. Für die Anmeldung, meldet euch bitte im Sekretariat bei Isabelle Junge isabelle.junge@kit.edu.

Beachtet: Der Termin am 5. April ist nicht mehr im Prüfungszeitraum für das Wintersemester und Zählt schon für das Sommersemester 2023.

Termine

Mo 15:45 Do 14:00
24.10. Vorlesung 27.10. Aktiv-Session
31.10. Vorlesung 03.11. Übung
07.11. Vorlesung 10.11. Aktiv-Session
14.11. Vorlesung 17.11. Übung
21.11. Vorlesung 24.11. Aktiv-Session
28.11. Vorlesung 01.12. Übung
05.12. Vorlesung 08.12. Aktiv-Session
12.12. Vorlesung 15.12. Übung
19.12. Aktiv-Session 22.12. siehe Weihnachtsvorlesung unten
09.01. Vorlesung 12.01. Übung
16.01. Vorlesung 19.01. Aktiv-Session
23.01. Vorlesung 26.01. Übung
30.01. Vorlesung 02.02. Aktiv-Session
06.02. Vorlesung 09.02. Übung
13.02. Vorlesung 16.02. Zusammenfassung

Weihnachtsvorlesung

Unser üblicher Termin am 22.12. entfällt. Dafür seid ihr alle herzlich zur Weihnachtsvorlesung am 22.12. um 11:30 im Gerthsen-Hörsaal (30.21) eingeladen. Dort werde ich im Rahmen der TGI-Vorlesung zeigen, dass das Kartenspiel Magic: The Gathering Turing-Vollständig ist.

Vorlesung

  1. FPT Grundlagen: mit Klicks, ohne Klicks
  2. Beschränkte Suchbäume: mit Klicks, ohne Klicks
  3. Iterative Kompression: mit Klicks, ohne Klicks
  4. Kernbildung - ähnliche Bäume: mit Klicks, ohne Klicks
  5. Lineare Programme: mit Klicks, ohne Klicks
  6. ILP-Relaxierung und Kernbildung: mit Klicks, ohne Klicks
  7. Branch and Reduce - Above Lower Bound: mit Klicks, ohne Klicks
  8. Color Coding: mit Klicks, ohne Klicks
  9. Baumweite: mit Klicks, ohne Klicks
  10. Baumzerlegung berechnen & planare Graphen: mit Klicks, ohne Klicks
  11. Courcelles Theorem & chordale Graphen: mit Klicks, ohne Klicks
  12. Untere Schranken - Reduktionen und W-Hierarchie: mit Klicks, ohne Klicks
  13. Untere Schranken - parametrisierte Komplexität und Datenbanken: mit Klicks, ohne Klicks
  14. Untere Schranken - ETH und SETH: mit Klicks, ohne Klicks
  15. Zusammenfassung: mit Klicks, ohne Klicks

Übungsblätter

Übungen

Aktivsessions

  1. Beschränkte Suchbäume: Folien, Notizen
  2. Iterative Kompression: Folien
  3. Kernbildung: Folien, Notizen
  4. ILP/Lenstra: Folien
  5. Color Coding: Folien
  6. Cops-and-Robber: Folien, Notizen
  7. Schwere Probleme: Folien, Notizen