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
- FPT Grundlagen: mit Klicks, ohne Klicks
- Beschränkte Suchbäume: mit Klicks, ohne Klicks
- Iterative Kompression: mit Klicks, ohne Klicks
- Kernbildung - ähnliche Bäume: mit Klicks, ohne Klicks
- Lineare Programme: mit Klicks, ohne Klicks
- ILP-Relaxierung und Kernbildung: mit Klicks, ohne Klicks
- Branch and Reduce - Above Lower Bound: mit Klicks, ohne Klicks
- Color Coding: mit Klicks, ohne Klicks
- Baumweite: mit Klicks, ohne Klicks
- Baumzerlegung berechnen & planare Graphen: mit Klicks, ohne Klicks
- Courcelles Theorem & chordale Graphen: mit Klicks, ohne Klicks
- Untere Schranken - Reduktionen und W-Hierarchie: mit Klicks, ohne Klicks
- Untere Schranken - parametrisierte Komplexität und Datenbanken: mit Klicks, ohne Klicks
- Untere Schranken - ETH und SETH: mit Klicks, ohne Klicks
- Zusammenfassung: mit Klicks, ohne Klicks
Übungsblätter
- Übungsblatt 1: blatt01.pdf
- Übungsblatt 2: blatt02.pdf
- Übungsblatt 3: blatt03.pdf
- Übungsblatt 4: blatt04.pdf
- Übungsblatt 5: blatt05.pdf
- Übungsblatt 6: blatt06.pdf
- Übungsblatt 7: blatt07.pdf