Hauptinhalt
CS 531 — Parametrisierte Algorithmen
(engl. Parameterized Algorithms)
| Niveaustufe, Verpflichtungsgrad | Vertiefungsmodul, abhängig vom importierenden Studiengang |
| Lehr- und Lernformen, Arbeitsaufwand |
Vorlesung (3 SWS), Übung (1 SWS), 180 Stunden (60 Std. Präsenzzeit, 120 Std. Selbststudium) |
| Leistungspunkte, Voraussetzungen zum Erwerb |
6 LP Studienleistung(en): Erreichen von mindestens 50 Prozent der Punkte aus den wöchentlich zu bearbeitenden Übungsaufgaben und mündliche Präsentation der Lösung von mindestens zwei der Übungsaufgaben. Prüfungsleistung: Mündliche Prüfung (Einzelprüfung) oder Klausur |
| Sprache, Benotung |
Englisch,Die Benotung erfolgt mit 0 bis 15 Punkten gemäß der Prüfungsordnung für den Studiengang M.Sc. Informatik. |
| Exportfach, Ursprung | Informatik, M.Sc. Informatik |
| Dauer des Moduls, Häufigkeit |
Ein Semester, Unregelmäßig |
| Modulverantwortliche(r) | Prof. Dr. Christian Komusiewicz |
Inhalt
- Parametrisierte und exakte Algorithmen
- Grundlegende algorithmische Techniken für parametrisierte Algorithmen: Suchbaumalgorithmen, Baumzerlegungen, Iterative Compression, Color Coding
- Datenreduktion und Kernelisierung
- Fortgeschrittene algorithmische Techniken für parametrisierte Algorithmen, beispielsweise Parametrisierung über untere Schranken, Inclusion-Exclusion, Representative Sets
- Parametrisierte Komplexitätstheorie
Qualifikationsziele
Die Studierenden können
- für schwere Berechnungsprobleme adäquate Parametrisierungen indentifizieren,
- effiziente Festparameteralgorithmen entwickeln und deren Laufzeit analysieren,
- Datenreduktionsregeln entwerfen und deren Effektivität analysieren und
- die algorithmische Schwierigkeit von parametrisierten Berechnungsproblemen nachweisen.
Voraussetzungen
Die erfolgreiche Teilnahme am Modul „Algorithmen und Datenstrukturen“ ist erforderlich; die erfolgreiche Teilnahme am Modul „Effiziente Algorithmen“ wird empfohlen.
Literatur
- Cygan et al. Parameterized Algorithms. Springer Verlag, 2015.
- Downey, Fellows: Fundamentals of Parameterized Complexity Theory. Springer Verlag 2013.
- Niedermeier: Invitation to Fixed-Parameter Algorithms. Oxford University Press, 2006.
- Flum, Grohe: Parameterized Complexity Theory. Springer Verlag, 2006.
Bitte beachten Sie:
Diese Seite beschreibt ein Modul gemäß dem im Wintersemester 2023/24 aktuellsten gültigen Modulhandbuch. Die meisten für ein Modul gültigen Regeln werden nicht durch die Prüfungsordnung festgelegt, und können daher von Semester zu Semester aktualisiert werden. Folgende Versionen liegen im Online-Modulhandbuch vor:
- WiSe 2016/17 (kein Äquivalent)
- SoSe 2018 (kein Äquivalent)
- WiSe 2018/19 (kein Äquivalent)
- WiSe 2019/20 (kein Äquivalent)
- WiSe 2020/21 (kein Äquivalent)
- SoSe 2021 (kein Äquivalent)
- WiSe 2021/22 (kein Äquivalent)
- WiSe 2022/23 (kein Äquivalent)
- WiSe 2023/24
Das Modulhandbuch enthält alle Module, unabhängig vom aktuellen Veranstaltungsangebot, vergleichen Sie dazu bitte das aktuelle Vorlesungsverzeichnis in Marvin.
Die Angaben im Online-Modulhandbuch wurden automatisch erstellt. Rechtsverbindlich sind die Angaben der Prüfungsordnung. Wenn Ihnen Unstimmigkeiten oder Fehler auffallen, sind wir für Hinweise dankbar.