|
Computational Complexity (CC)5 ECTS (englische Bezeichnung: Computational Complexity)
Modulverantwortliche/r: Yiannis Giannakopoulos Lehrende:
Yiannis Giannakopoulos
Startsemester: |
SS 2022 | Dauer: |
1 Semester | Turnus: |
jährlich (SS) |
Präsenzzeit: |
45 Std. | Eigenstudium: |
105 Std. | Sprache: |
Englisch |
Lehrveranstaltungen:
-
-
Computational Complexity
(Vorlesung, 2 SWS, Yiannis Giannakopoulos, Mo, 10:00 - 12:00, Übung 1 / 01.250-128)
-
Übung zu Computational Complexity
(Übung, 1 SWS, Yiannis Giannakopoulos, Do, 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
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 |
|
|
|
|
UnivIS ist ein Produkt der Config eG, Buckenhof |
|
|