Berechenbarkeit und Komplexität
| Semester: | Wintersemester 2022/23 |
| Veranstalter: | Prof. Grohe
|
| Bemerkungen: |
|
-
-
Einführung
- Di, 11.10.2022, 16:30 Uhr
-
-
Berechnungsprobleme und Turingmaschinen
- Mi, 12.10.2022, 08:30 Uhr
-
-
Mehrband-Turingmaschinen und die universelle Turingmaschine
- Di, 18.10.2022, 16:30 Uhr
-
-
Registermaschine (RAM), Church-Turing-These
- Mi, 19.10.2022, 08:30 Uhr
-
-
Unentscheidbare Probleme: Diagonalisierung
- Di, 25.10.2022, 16:30 Uhr
-
-
Unentscheidbarkeit des Halteproblems: Unterprogrammtechnik
- Mi, 26.10.2022, 08:30 Uhr
-
-
Der Satz von Rice
- Mi, 02.11.2022, 08:30 Uhr
-
-
Rekursive Aufzählbarkeit
- Di, 08.11.2022, 16:30 Uhr
-
-
Allgemeines Halteproblem und Hilberts 10. Problem
- Mi, 09.11.2022, 08:30 Uhr
-
-
Das Postsche Korrespondenzproblem
- Di, 15.11.2022, 16:30 Uhr
-
-
WHILE-Programme
- Mi, 16.11.2022, 08:30 Uhr
-
-
LOOP-Programme
- Di, 22.11.2022, 16:30 Uhr
-
-
Die Komplexitätsklassen P und NP
- Mi, 23.11.2022, 08:30 Uhr
-
-
Die Klasse NP und polynomielle Reduktion
- Di, 29.11.2022, 16:30 Uhr
-
-
NP-Vollständigkeit
- Di, 06.12.2022, 16:30 Uhr
-
-
NP-Vollständigkeit ausgewählter Zahlprobleme
- Di, 13.12.2022, 16:30 Uhr
-
-
NP-Vollständigkeit ausgewählter Graphprobleme
- Mi, 14.12.2022, 08:30 Uhr
-
-
Approximationsalgorithmen und Ausblick
- Di, 10.01.2023, 16:30 Uhr
- sehr zu empfehlen: Effiziente Algorithmen, Theorie-Wahlpflicht, die es nur im Bachelor gibt
-
-
Zusammenfassung
- Mi, 11.01.2023, 08:30 Uhr