====== Parametrisierte Algorithmen ====== **Dozent:** [[people:thomasblaesius|]] **Übungsleitung:** [[people:vonderheydt|]], [[people:marcuswilhelm|]], [[people:wendyyi|]] \\ \\ 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/search.php#!campus/all/event.asp?gguid=0xB657319F05404E33B29FC7D5770C0936 \\ Link zum Discord: https://discord.gg/JrM8qaJvCK ===== 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 21.10. um 15:45** stattfinden. ===== Prüfung ===== Link zur Terminbuchung: https://cloud.iti.kit.edu/index.php/apps/appointments/pub/909aEDbt9vr7rElC/form Es gibt Termine am 24. Februar, 11. März, 24. März und 7. April. Sollte es an eurem Wunschtag keinen freien Termin mehr geben, dann meldet euch nochmal. Wenn ihr es schafft halbwegs defragmentiert Termine zu buchen, dann wäre das hilfreich. **Beachtet:** Für die Prüfung ist der Übungsschein Voraussetzung. Vermutlich läuft das so ab, dass ihr euch einen Termin bucht und euch im Campussystem für den Schein anmeldet. Wir tragen den Schein am Ende des Semesters als bestanden ein und dann könnt ihr euch im Campussystem noch für die Prüfung anmelden. ===== Termine ===== ^ Mo 15:45 |^ Do 14:00 || | 21.10. | Vorlesung | 24.10. | Aktiv-Session | | 28.10. | Vorlesung | 31.10. | Übung | | 04.11. | Vorlesung | 07.11. | Aktiv-Session | | 11.11. | Vorlesung | 14.11. | Übung | | 18.11. | Vorlesung | 21.11. | Aktiv-Session | | 25.11. | Vorlesung | 28.11. | Übung | | 02.12. | Vorlesung | 05.12. | Aktiv-Session | | 09.12. | Vorlesung | 12.12. | Übung | | 16.12. | Vorlesung | 19.12. | Aktiv-Session | | 06.01. | frei | 09.01. | Übung | | 13.01. | Vorlesung | 16.01. | Vorlesung | | 20.01. | Vorlesung | 23.01. | Übung | | 27.01. | Vorlesung | 30.01. | Aktiv-Session | | 03.02. | Vorlesung | 06.02. | Übung | | 10.02. | Vorlesung | 13.02. | Zusammenfassung | ===== Vorlesung ===== - FPT Grundlagen: {{ :teaching:2024ws:param_algo:01-fpt-grundlagen.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:01-fpt-grundlagen-print.pdf |ohne Klicks}} - Beschränkte Suchbäume: {{ :teaching:2024ws:param_algo:02-beschraenkte-suchbaeume.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:02-beschraenkte-suchbaeume-print.pdf |ohne Klicks}} - Iterative Kompression: {{ :teaching:2024ws:param_algo:03-iterative-kompression.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:03-iterative-kompression-print.pdf |ohne Klicks}} - Kernbildung -- ähnliche Bäume: {{ :teaching:2024ws:param_algo:04-kernbildung-aehnliche-baeume.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:04-kernbildung-aehnliche-baeume-print.pdf |ohne Klicks}} - Lineare Programme: {{ :teaching:2024ws:param_algo:05-dualitaet-lenstra.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:05-dualitaet-lenstra-print.pdf |ohne Klicks}} - ILP-Relaxierung und Kernbildung: {{ :teaching:2024ws:param_algo:06-ilp-relaxierung-und-kernbildung.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:06-ilp-relaxierung-und-kernbildung-print.pdf |ohne Klicks}} - Branch and Reduce - Above Lower Bound: {{ :teaching:2024ws:param_algo:07-branch-and-reduce-above-lower-bound.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:07-branch-and-reduce-above-lower-bound-print.pdf |ohne Klicks}} - Color Coding: {{ :teaching:2024ws:param_algo:08-color-coding.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:08-color-coding-print.pdf |ohne Klicks}} - Baumweite & dynamische Programme: {{ :teaching:2024ws:param_algo:09-baumweite.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:09-baumweite-print.pdf |ohne Klicks}} - Baumzerlegung berechnen & planare Graphen: {{ :teaching:2024ws:param_algo:10-baumzerlegung.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:10-baumzerlegung-print.pdf |ohne Klicks}} - Courcelles Theorem & chordale Graphen: {{ :teaching:2024ws:param_algo:11-courcelle-chordale-graphen.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:11-courcelle-chordale-graphen-print.pdf |ohne Klicks}} - Untere Schranken - Reduktionen und W-Hierarchie: {{ :teaching:2024ws:param_algo:12-untere-schranken.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:12-untere-schranken-print.pdf |ohne Klicks}} - Untere Schranken - parametrisierte Komplexität und Datenbanken: {{ :teaching:2024ws:param_algo:13-w3-relationale-db.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:13-w3-relationale-db-print.pdf |ohne Klicks}} - Untere Schranken - ETH und SETH: {{ :teaching:2024ws:param_algo:14-eth-seht.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:14-eth-seht-print.pdf |ohne Klicks}} - Zusammenfassung: {{ :teaching:2024ws:param_algo:15-zusammenfassung.pdf |mit Klicks}}, {{ :teaching:2024ws:param_algo:15-zusammenfassung-print.pdf |ohne Klicks}} ===== Übungsblätter ===== * {{ :teaching:2024ws:param_algo:blatt01.pdf |}} {{ :teaching:2024ws:param_algo:loesung01.pdf |}} * {{ :teaching:2024ws:param_algo:blatt02.pdf |}} {{ :teaching:2024ws:param_algo:vertex_cover.zip |}} {{ :teaching:2024ws:param_algo:loesung02.pdf |}} * {{ :teaching:2024ws:param_algo:blatt03.pdf |}} {{ :teaching:2024ws:param_algo:closest_string.zip |}} {{ :teaching:2024ws:param_algo:loesung03.pdf |}} Update 27.11: Die Aufgabe die neu gespawnt ist, ist nur aus Versehen nachträglich auf dem Blatt gelandet. Sie gibt jetzt nicht übertragbare Bonuspunkte (zählt also nicht zur Gesamtpunktzahl des Blatts). * {{ :teaching:2024ws:param_algo:blatt04.pdf |}} {{ :teaching:2024ws:param_algo:loesung04.pdf |}} * {{ :teaching:2024ws:param_algo:blatt05.pdf |}} {{ :teaching:2024ws:param_algo:closest_string_assignment_2.zip |}} {{ :teaching:2024ws:param_algo:loesung05.pdf |}} * {{ :teaching:2024ws:param_algo:blatt06.pdf |}} {{ :teaching:2024ws:param_algo:baumzerlegte_graphen.zip |}} {{ :teaching:2024ws:param_algo:loesung06.pdf |}} * {{ :teaching:2024ws:param_algo:blatt07.pdf |}} {{ :teaching:2024ws:param_algo:loesung07.pdf |}} ===== Übungen ===== {{ :teaching:2024ws:param_algo:01-uebung.pdf | Übung 1}} {{ :teaching:2024ws:param_algo:02-uebung.pdf | Übung 2}} {{ :teaching:2024ws:param_algo:03-uebung.pdf | Übung 3}} {{ :teaching:2024ws:param_algo:04-uebung.pdf | Übung 4}} {{ :teaching:2024ws:param_algo:05-uebung.pdf | Übung 5}} {{ :teaching:2024ws:param_algo:06-uebung.pdf | Übung 6}} {{ :teaching:2024ws:param_algo:07-uebung.pdf | Übung 7}} {{ :teaching:2024ws:param_algo:07-loesungshinweis.pdf |}} ===== Aktivsessions ===== - Beschränkte Suchbäume: {{ :teaching:2024ws:param_algo:01-suchbaum.pdf |Folien}}, {{ :teaching:2024ws:param_algo:01-suchbaum-notes.pdf |Notizen}} - Iterative Kompression: {{ :teaching:2024ws:param_algo:02-iterative-kompression.pdf |Folien}} - Kernbildung: {{ :teaching:2024ws:param_algo:03-kernbildung.pdf |Folien}} - ILP/Lenstra: {{ :teaching:2024ws:param_algo:04-lp-lenstra.pdf |Folien}} - Color Coding: {{ :teaching:2024ws:param_algo:05-color-coding-print.pdf |Folien}} - Schwere Probleme: {{ :teaching:2024ws:param_algo:07-schwere-probleme.pdf |Folien}} [[teaching:2024ws:param_algo:active_notes:start|mehr Notizen]]