Berechenbarkeit und Komplexität
| Semester: | Wintersemester 2015/16 |
| Veranstalter: | Prof. Grohe
|
| Bemerkungen: |
|
-
-
Motivation, Übersicht und Organisatorisches
- Fr, 23.10.2015, 16:15 Uhr
-
-
Teil 1 - Grundlagen
Modellierung von Problemen, Einführung der Turingmaschine
- Mo, 26.10.2015, 18:15 Uhr
-
-
Mehrband-Turingmaschinen und die universelle Turingmaschine
- Mo, 02.11.2015, 18:15 Uhr
-
-
Registermaschine (RAM), Church-Turing-These
- Fr, 06.11.2015, 16:15 Uhr
-
-
Teil 2 - Berechenbarkeit
Unentscheidbare Probleme: Diagonalisierung
- Mo, 09.11.2015, 18:15 Uhr
-
-
Unentscheidbarkeit des Halteproblems: Unterprogrammtechnik
- Fr, 13.11.2015, 16:15 Uhr
-
-
Der Satz von Rice
- Mo, 16.11.2015, 18:15 Uhr
-
-
Rekursive Aufzählbarkeit
- Fr, 20.11.2015, 16:15 Uhr
-
-
Allgemeines Halteproblem und Hilberts 10. Problem
- Mo, 23.11.2015, 18:15 Uhr
-
-
Das Postsche Korrespondenzproblem
- Fr, 27.11.2015, 16:15 Uhr
-
-
WHILE-Programme
- Mo, 30.11.2015, 18:15 Uhr
-
-
LOOP-Programme und Zusammenfassung Berechenbarkeit
- Mo, 07.12.2015, 18:15 Uhr
-
-
Teil 3 - Komplexität
Die Komplexitätsklassen P und NP
- Fr, 11.12.2015, 16:15 Uhr
-
-
Die Klasse NP und Polynomielle Reduktionen
- Mo, 18.01.2016, 18:15 Uhr
-
-
NP-Vollständigkeit
- Fr, 22.01.2016, 16:15 Uhr
-
-
NP-Vollständigkeit ausgewählter Zahlprobleme
- Mo, 25.01.2016, 18:15 Uhr
-
-
NP-Vollständigkeit ausgewählter Graphprobleme
- Fr, 29.01.2016, 16:15 Uhr
-
-
Ausblick: Algorithmen und Komplexität
- Mo, 01.02.2016, 18:15 Uhr