====== 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:** [[people:thomasblaesius|]] **Übungsleiter:** [[people:marcuswilhelm|]] \\ \\ 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 [[https://ilias.studium.kit.edu/goto.php?target=crs_1437040&client_id=produktiv|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 ===== - FPT Grundlagen: {{ :teaching:2021ss:param_algo:01-fpt-grundlagen.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:01-fpt-grundlagen-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:01-fpt-grundlagen-1080p.mp4?linkonly |Aufnahme (1080p, 250 MB)}}, {{ :teaching:2021ss:param_algo:01-fpt-grundlagen-720p.mp4?linkonly |Aufnahme (720p, 152 MB)}} - Beschränkte Suchbäume: {{ :teaching:2021ss:param_algo:02-beschraenkte-suchbaeume.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:02-beschraenkte-suchbaeume-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:02-beschraenkte-suchbaeume-1080p.mp4?linkonly |Aufnahme (1080p, 276 MB)}}, {{ :teaching:2021ss:param_algo:02-beschraenkte-suchbaeume-720p.mp4?linkonly |Aufnahme (720p, 169 MB)}} - Iterative Kompression: {{ :teaching:2021ss:param_algo:03-iterative-kompression.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:03-iterative-kompression-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:03-iterative-kompression-1080p.mp4?linkonly |Aufnahme (1080p, 233 MB)}}, {{ :teaching:2021ss:param_algo:03-iterative-kompression-720p.mp4?linkonly |Aufnahme (720p, 143 MB)}} - Kernbildung: {{ :teaching:2021ss:param_algo:04-kernbildung-aehnliche-baeume.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:04-kernbildung-aehnliche-baeume-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:04-kernbildung-aehnliche-baeume-1080p.mp4?linkonly |Aufnahme (1080p, 287 MB)}}, {{ :teaching:2021ss:param_algo:04-kernbildung-aehnliche-baeume-720p.mp4?linkonly |Aufnahme (720p, 168 MB)}} - Lineare Programme: {{ :teaching:2021ss:param_algo:05-dualitaet-lenstra.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:05-dualitaet-lenstra-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:05-dualitaet-lenstra-1080p.mp4?linkonly |Aufnahme (1080p, 270 MB)}}, {{ :teaching:2021ss:param_algo:05-dualitaet-lenstra-720p.mp4?linkonly |Aufnahme (720p, 165 MB)}} - LP-Relaxierung und Kernbildung: {{ :teaching:2021ss:param_algo:06-ilp-relaxierung-und-kernbildung.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:06-ilp-relaxierung-und-kernbildung-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:06-ilp-relaxierung-und-kernbildung-1080p.mp4?linkonly |Aufnahme (1080p, 292 MB)}}, {{ :teaching:2021ss:param_algo:06-ilp-relaxierung-und-kernbildung-720p.mp4?linkonly |Aufnahme (720p, 176 MB)}} - Branch and Reduce - Above Lower Bound: {{ :teaching:2021ss:param_algo:07-branch-and-reduce-above-lower-bound.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:07-branch-and-reduce-above-lower-bound-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:07-branch-and-reduce-above-lower-bound-1080p.mp4?linkonly |Aufnahme (1080p, 237 MB)}}, {{ :teaching:2021ss:param_algo:07-branch-and-reduce-above-lower-bound-720p.mp4?linkonly |Aufnahme (720p, 143 MB)}} - Color Coding: {{ :teaching:2021ss:param_algo:08-color-coding.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:08-color-coding-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:08-color-coding-1080p.mp4?linkonly |Aufnahme (1080p, 289 MB)}}, {{ :teaching:2021ss:param_algo:08-color-coding-720p.mp4?linkonly |Aufnahme (720p, 171 MB)}}, {{ :teaching:2021ss:param_algo:08.5-color-coding-nachtrag-1080p.mp4?linkonly |Nachtrag (1080p, 37 MB)}}, {{ :teaching:2021ss:param_algo:08.5-color-coding-nachtrag-720p.mp4?linkonly |Nachtrag (720p, 22 MB)}} - Baumweite: {{ :teaching:2021ss:param_algo:09-baumweite.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:09-baumweite-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:09-baumweite-1080p.mp4?linkonly |Aufnahme (1080p, 294 MB)}}, {{ :teaching:2021ss:param_algo:09-baumweite-720p.mp4?linkonly |Aufnahme (720p, 178 MB)}} - Baumzerlegung + planare Graphen: {{ :teaching:2021ss:param_algo:10-baumzerlegung.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:10-baumzerlegung-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:10-baumzerlegung-1080p.mp4?linkonly |Aufnahme (1080p, 303 MB)}}, {{ :teaching:2021ss:param_algo:10-baumzerlegung-720p.mp4?linkonly |Aufnahme (720p, 180 MB)}} - Courcelles Theorem + chordale Graphen: {{ :teaching:2021ss:param_algo:11-courcelle-chordale-graphen.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:11-courcelle-chordale-graphen-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:11-courcelle-chordale-graphen-1080p.mp4?linkonly |Aufnahme (1080p, 250 MB)}}, {{ :teaching:2021ss:param_algo:11-courcelle-chordale-graphen-720p.mp4?linkonly |Aufnahme (720p, 151 MB)}} - Reduktionen und W-Hierarchie: {{ :teaching:2021ss:param_algo:12-untere-schranken.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:12-untere-schranken-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:12-untere-schranken-720p.mp4?linkonly |Aufnahme (720p, 194 MB)}} - Parametrisierte Komplexität und Datenbanken: {{ :teaching:2021ss:param_algo:13-w3-relationale-db.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:13-w3-relationale-db-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:13-w3-relationale-db-1080p.mp4?linkonly |Aufnahme (1080p, 286 MB)}}, {{ :teaching:2021ss:param_algo:13-w3-relationale-db-720p.mp4?linkonly |Aufnahme (720p, 174 MB)}} - ETH und SETH: {{ :teaching:2021ss:param_algo:14-eth-seht.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:14-eth-seht-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:14-eth-seht-1080p.mp4?linkonly |Aufnahme (1080p, 296 MB)}}, {{ :teaching:2021ss:param_algo:14-eth-seht-720p.mp4?linkonly |Aufnahme (720p, 178 MB)}} - Zusammenfassung: {{ :teaching:2021ss:param_algo:15-zusammenfassung.pdf |mit Klicks}}, {{ :teaching:2021ss:param_algo:15-zusammenfassung-print.pdf |ohne Klicks}}, {{ :teaching:2021ss:param_algo:15-zusammenfassung-1080p.mp4?linkonly |Aufnahme (1080p, 289 MB)}}, {{ :teaching:2021ss:param_algo:15-zusammenfassung-720p.mp4?linkonly |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) {{ :teaching:2021ss:param_algo:blatt00.pdf |}} * Blatt 1 (Abgabe bis 5.5.2021) {{ :teaching:2021ss:param_algo:blatt01.pdf |}}, Graphen für Aufgabe 4: {{ :teaching:2021ss:param_algo:graphen.zip |}} * Blatt 2 (Abgabe bis 19.5.2021) {{ :teaching:2021ss:param_algo:blatt02.pdf |}}, Graphen für Aufgabe 4: {{ :teaching:2021ss:param_algo:graphen_fvs.zip |}} * Blatt 3 (Abgabe bis 9.6.2021) {{ :teaching:2021ss:param_algo:blatt03.pdf |}} * Blatt 4 (Abgabe bis 23.6.2021) {{:teaching:2021ss:param_algo:blatt04.pdf|}} * Blatt 5 (Abgabe bis 7.7.2021) {{:teaching:2021ss:param_algo:blatt05.pdf|}} * Blatt 6 (Abgabe bis 21.7.2021 {{:teaching:2021ss:param_algo:blatt06.pdf|}} ===== Zusätzliche Materialien ===== * Aktivsession 1 (Beschränkte Suchbäume): {{ :teaching:2021ss:param_algo:01-suchbaum.pdf |Folien}} * Aktivsession 2 (Kernbildung): {{ :teaching:2021ss:param_algo:02-kernbildung.pdf |Folien}} * Aktivsession 3 (ILP/Lenstra): {{ :teaching:2021ss:param_algo:03-lp-lenstra.pdf |Folien}} * Aktivsession 4 (Color Coding): {{ :teaching:2021ss:param_algo:04-color-coding.pdf | Folien}} * Aktivsession 5 (Cops-and-Robber): {{ :teaching:2021ss:param_algo:05-cops-and-robbers.pdf |Folien}} * Aktivsession 6 (Schwere Probleme): {{ :teaching:2021ss:param_algo:06-schwere-probleme.pdf |Folien}}