-
Moduldetails
Dozent: Prof. Dr. Heribert Vollmer
Frequenz: zweijährlich (gerade) im Wintersemester
Veranstaltungsart: Vorlesung, Übung und Seminar (2V + 1Ü + 2S, 7 CP)
Prüfung: mündl. Prüfung
-
Vorlesungsinhalte
Das Modul vermittelt vertiefte Kenntnisse über Konzepte, Techniken und Phänomene der parametrisierten Komplexitätstheorie. Nach erfolgreichem Abschluss der LV können die Studierenden algorithmische Probleme hinsichtlich ihrer parametrisierten Komplexität analysieren. Sie beurteilen die Abhängigkeit der Komplexität von strukturellen Eigenschaften der Eingabeinstanz. Sie entwickeln Klassifikationen der Schwierigkeit von Berechnungsproblemen, abhängig von Eingabeparametern.
Gliederung:
- Die Klasse FPT
- Reduktionen
- Die W-Hierarchie
- Logik und Komplexität
- Paradigmen des Algorithmenentwurs
-
Informationen zur Prüfung
Die Abschlussprüfung des Moduls ist eine mündliche Prüfung.
Termin
Die Prüfungstermine vergeben wir über eine institutsinterne Website (siehe Link unten). Achtung: Dies ersetzt nicht die Anmeldung der Prüfung im QIS.
Anmeldung
Je nach Prüfungsordnung ist eine Anmeldung im QIS erforderlich (siehe Link unten).
Studienleistung
Falls Ihre Prüfungsordnung eine Studienleistung für dieses Modul vorsieht, kontaktieren Sie bitte den Dozenten.
Theorie der parametrisierten Komplexität
Letzte Änderung: 22.03.21
