Parametrisierte Algorithmen
Die mündlichen Prüfungen finden am 20.08.21 statt. Bitte schicken Sie zur Vereinbarung eines Termins eine Email an: scale.info@iti.uka.de.
Update 26.07.21: Aktuell sind alle Prüfungstermine vergeben.
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.
Ablauf
Wir treffen uns zum ersten Termin am Montag den 12.4.21 um 10 Uhr in digitaler Form. Der Link zum Zoom Meeting steht im Ilias. Im ersten Treffen wird der weitere Ablauf der Vorlesung besprochen. Danach treffen wir uns wöchentlich jeweils montags um 10 und mittwochs um 14 Uhr.
Termine
| Montag (10 Uhr) | Mittwoch (14 Uhr) | ||
|---|---|---|---|
| 12.4. | Vorlesung | 14.4. | Übung |
| 19.4. | Vorlesung | 21.4. | Aktiv-Session |
| 26.4. | Vorlesung | 28.4. | Übung |
| 3.5. | Vorlesung | 5.5. | Aktiv-Session |
| 10.5. | Vorlesung | 12.5. | Übung |
| 17.5. | Vorlesung | 19.5. | Aktiv-Session |
| 24.5. | Pfingsten | 26.5. | Pfingsten |
| 31.5. | Vorlesung | 2.6. | Übung |
| 7.6. | Vorlesung | 9.6. | Aktiv-Session |
| 14.6. | Vorlesung | 16.6. | Übung |
| 21.6. | Vorlesung | 23.6. | Aktiv-Session |
| 28.6. | Vorlesung | 30.6. | Übung |
| 5.7. | Vorlesung | 7.7. | Aktiv-Session |
| 12.7. | Vorlesung | 14.7. | Übung |
| 19.7. | Vorlesung | 21.7. | Aktiv-Session |
Vorlesung
- LP-Relaxierung und Kernbildung: mit Klicks, ohne Klicks, Aufnahme (1080p, 292 MB), Aufnahme (720p, 176 MB)
- Branch and Reduce - Above Lower Bound: mit Klicks, ohne Klicks, Aufnahme (1080p, 237 MB), Aufnahme (720p, 143 MB)
- Baumzerlegung + planare Graphen: mit Klicks, ohne Klicks, Aufnahme (1080p, 303 MB), Aufnahme (720p, 180 MB)
- Courcelles Theorem + chordale Graphen: mit Klicks, ohne Klicks, Aufnahme (1080p, 250 MB), Aufnahme (720p, 151 MB)
- Parametrisierte Komplexität und Datenbanken: mit Klicks, ohne Klicks, Aufnahme (1080p, 286 MB), Aufnahme (720p, 174 MB)
Übungsblätter
Sei i gerade. Das i/2-te Übungsblatt wird am Mittwoch in Woche i ausgegeben und kann bis zum Mittwoch in Woche i+2 abgegeben werden.
- Blatt 0 (Abgabe bis 21.4.2021) blatt00.pdf
- Blatt 1 (Abgabe bis 5.5.2021) blatt01.pdf, Graphen für Aufgabe 4: graphen.zip
- Blatt 2 (Abgabe bis 19.5.2021) blatt02.pdf, Graphen für Aufgabe 4: graphen_fvs.zip
- Blatt 3 (Abgabe bis 9.6.2021) blatt03.pdf
- Blatt 4 (Abgabe bis 23.6.2021) blatt04.pdf
- Blatt 5 (Abgabe bis 7.7.2021) blatt05.pdf
- Blatt 6 (Abgabe bis 21.7.2021 blatt06.pdf