|
Computational Complexity (CC)5 ECTS (englische Bezeichnung: Computational Complexity)
Modulverantwortliche/r: Yiannis Giannakopoulos Lehrende:
Yiannis Giannakopoulos
Start semester: |
SS 2022 | Duration: |
1 semester | Cycle: |
jährlich (SS) |
Präsenzzeit: |
45 Std. | Eigenstudium: |
105 Std. | Language: |
Englisch |
Lectures:
-
-
Computational Complexity
(Vorlesung, 2 SWS, Yiannis Giannakopoulos, Mon, 10:00 - 12:00, Übung 1 / 01.250-128)
-
Übung zu Computational Complexity
(Übung, 1 SWS, Yiannis Giannakopoulos, Thu, 12:00 - 14:00, Übung 5 / 01.254-128)
Inhalt:
This course covers:
P, NP, and NP-completeness
Complexity classes and reductions
Boolean circuits
The polynomial-time hierarchy
Space complexity
Randomized computation
Counting complexity
Introduction to the PCP theorem and hardness of approximation
Average-case complexity
Lernziele und Kompetenzen:
Upon successful completion of the module, students are able to:
formal limitations
P, NP and PSPACE)
and understand reductions between these classes
Boolean circuits and randomness
Verwendbarkeit des Moduls / Einpassung in den Musterstudienplan: Das Modul ist im Kontext der folgenden Studienfächer/Vertiefungsrichtungen verwendbar:
- Computational and Applied Mathematics (Master of Science)
(Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Specialisation: Modeling and applied analysis (MApA) and optimization (Opti) | Computational complexity)
- Computational and Applied Mathematics (Master of Science)
(Po-Vers. 2019w | NatFak | Computational and Applied Mathematics (Master of Science) | Gesamtkonto | Specialisation: Numerical analysis and simulation (NASi) and optimization (Opti) | Computational complexity)
Studien-/Prüfungsleistungen:
Computational complexity (Prüfungsnummer: 50921)
- Prüfungsleistung, mündliche Prüfung, Dauer (in Minuten): 30, benotet, 5 ECTS
- Anteil an der Berechnung der Modulnote: 100.0 %
- Erstablegung: SS 2022, 1. Wdh.: SS 2022
1. Prüfer: | Yiannis Giannakopoulos |
|
|
|