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