Hauptinhalt
CS 576 — Komplexitätstheorie
(engl. Computational complexity theory)
| Niveaustufe, Verpflichtungsgrad | Vertiefungsmodul, abhängig vom importierenden Studiengang |
| Lehr- und Lernformen, Arbeitsaufwand |
Vorlesung (4 SWS), Übung (2 SWS), 270 Stunden (90 Std. Präsenzzeit, 180 Std. Selbststudium) |
| Leistungspunkte, Voraussetzungen zum Erwerb |
9 LP Studienleistung(en): Präsentation von Zwischenständen, Teilnahme an der Blockveranstaltung 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
- Komplexitätsklassen, etwa LOGSPACE, P, NP, PSPACE
- Zeit- und Platzhierarchien
- Reduktionen und Vollständigkeit
- Determinismus / Nichtdeterminismus und Randomisierung
- Schaltkreiskomplexität
- Parametrisierte Komplexität
- Fine-Grained Complexity Theory
Qualifikationsziele
Die Studierenden können
- Probleme hinsichtlich deren Berechnungsschwierigkeit klassifizieren,
- verschiedene Klassen von Problemen untereinander vergleichen,
- die Berechnungsmächtigkeit verschiedener Maschinenmodelle, etwa randomisierter und nichtdeterministischer Turingmaschinen, vergleichen.
Voraussetzungen
Erfolgreiche Teilnahme am Modul Theoretische Informatik aus dem Bachelorstudiengang Informatik.
Literatur
- Sanjeev Arora, Boaz Barak: Computational Complexity - A Modern Approach. Cambridge University Press 2009
- Christos H. Papadimitriou: Computational complexity. Academic Internet Publ. 2007
- Ingo Wegener: Complexity theory - exploring the limits of efficient algorithms. Springer 2005
- Rodney G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Texts in Computer Science, Springer 2013
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.