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.

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. ??
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

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

Übungsblätter

Übungen

Aktivsessions

  1. Beschränkte Suchbäume: Folien, Notizen
  2. Iterative Kompression: Folien
  3. Kernbildung: Folien, Notizen