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.