Veranstaltungsart und -inhalt
|
| Titel |
Computational Complexity |
| Dozent |
PD Dr. Andreas Jakoby |
| Einordnung |
Diplom-Studiengang 6. Semester, Master-Studiengang 2. Semester, Master-Studiengang CLS 2. Semester |
| Inhalte |
- Struktur von Zeit- und Platz-Klassen
- Schaltkreis-Komplexität
- Polynomielle Hierarchie
- Orakel-Turingmaschinen und Relativierung
- Vergleich verschiedener Reduktionsarten
- Probabilistische Klassen
- Separation von Komplexitätsklassen
- Berechenbarkeit
|
| Qualifikationsziele |
- Fähigkeit, Probleme bezüglich verschiedener Aufwandmaße einzuordnen
- Kenntnis der Beziehungen zwischen Maschinenmodellen und Aufwandsmaßen
- Verständnis der grundlegenden Begriffe und Methoden der Komplexitätsanalyse
|
| Empfohlene Literatur |
- Reischuk, Komplexitätstheorie Teubner 1990
- D. Kozen, Theory of Computation, Springer 2000
- K. Wagner, G. Wechsung, Computational Complexity, Reidel 1986
- B. Cooper, Computability Theory, Chapman & Hall, 2004
|
Vorlesung |
| Dozent |
PD Dr. Andreas Jakoby |
| Umfang |
2 SWS, ECTS-Credits: 4 |
| Termine |
Mo 14:00 – 16:00, ITCS Seminarraum 2021
|
|
Folien
|
[V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 | V9 | V10 | V11 | V12 | V13 | V14 | V15 | alle]
|
Übung |
| Assistent |
Dipl.-Inf. Michael Elberfeld |
| Umfang |
1 SWS |
| Termine |
Do 10:00 – 11:00, ITCS Seminarraum 2021
|
|
Aufgaben
|
Übungswiki
|
