Berechenbarkeit und Komplexität
| Semester: | Wintersemester 2016/17 |
| Veranstalter: | Prof. Schweitzer
|
| Bemerkungen: |
|
-
-
Einführung,
Organisation
- Di, 18.10.2016, 14:15 Uhr
-
-
Berechnungsprobleme,
Turingmaschinen,
TMs mit mehreren Spuren
- Fr, 21.10.2016, 14:15 Uhr
-
-
TMs mit mehreren Spuren,
TMs mit mehreren Bändern,
Universelle TMs
- Di, 25.10.2016, 14:15 Uhr
-
-
Random Access Machines,
Umwandlung von TMs und RAMs,
Church-Turing-These
- Fr, 28.10.2016, 14:15 Uhr
-
-
Abzählbarkeit,
Grenzen der Berechenbarkeit,
Diagonalsprache
- Fr, 04.11.2016, 14:15 Uhr
- Vorlesung 04 - Berechenbarkeit
-
-
Diagonalsprache,
Unterprogrammtechnik,
Halteproblem,
Collatz-Problem
- Di, 08.11.2016, 14:15 Uhr
-
-
Escaping,
Partielle Funktionen,
Satz von Rice
- Fr, 11.11.2016, 14:15 Uhr
-
-
Aufzähler,
Semi-Entscheidbarkeit
Rekursive Aufzählbarkeit,
Komplemente, Schnitte, Vereinigungen,
Reduktionen
- Di, 15.11.2016, 14:15 Uhr
-
-
Reduktionen,
Hilberts zehntes Problem
- Fr, 18.11.2016, 14:15 Uhr
-
-
Das Postsche Korrespondenzproblem,
Simulation von TMs durch PKP
- Di, 22.11.2016, 14:15 Uhr
-
-
WHILE und LOOP-Programme,
Eingeschränkte RAM
- Fr, 25.11.2016, 14:15 Uhr
-
-
LOOP-Programme,
Ackermann-Funktion,
Zusammenfassung Berechenbarkeit
- Di, 29.11.2016, 14:15 Uhr
-
-
Einführung Komplexität,
Komplixitätsklassen P, NP, EXPTIME,
Einige Probleme,
Nichtdeterministische TMs
- Di, 06.12.2016, 14:15 Uhr
- Vorlesung 12,
wurde nicht aufgezeichnet
-
-
Optimierungs- und Entscheidungsprobleme,
KP, BBP, TSP,
Zertifikate & Verifizierer,
COLORING, SAT
- Fr, 09.12.2016, 14:15 Uhr
-
-
NP-Schwere & NP-Vollständigkeit,
NP-Vollständigkeit von SAT & 3-SAT
- Di, 13.12.2016, 14:15 Uhr
-
-
SUBSET-SUM,
PARTITION,
NP-Vollständigkeit vorheriger Probleme
- Fr, 16.12.2016, 14:15 Uhr
-
-
NP-Vollständigkeit von CLIQUE,
Hamiltonkreisprobleme HC & DHC,
Evaluation (Kekse!),
NP-Vollständigkeit von TSP & {1,2}-TSP,
NP-Intermediate
- Di, 20.12.2016, 14:15 Uhr
-
-
Ausblick,
Approximationsalgorithmen,
Parametrisierte Algorithmen,
PSPACE, EXPTIME
- Di, 10.01.2017, 14:15 Uhr
-
-
Zusammenfassung
- Fr, 13.01.2017, 14:15 Uhr