Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 28.01.2016, Vorlesung und Übung - 22

22: Vorlesung und Übung|
0:00:00 Starten
0:00:10 2: Berechenbarkeitstheorie | 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These
0:00:41 Berechenbarkeit Hauptergebnis
0:01:26 2.2 Intuitiver Berechenbarkeitsbgegriff
0:01:48 Beispiel
0:07:15 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit
0:08:41 LOOP-Programme
0:10:29 Äquivalenz von Maschinenmodellen
0:12:04 Markov-Algorithmen
0:14:08 Zellularautomaten
0:15:16 2.4 Primitiv rekursive Funktionen
0:16:11 2.5 Die Ackermannfunktion
0:18:06 Mehr schnell wachsende Funktionen
0:19:06 Wissen über Fleißige Biber
0:20:12 2.6 Halterproblem, Unentscheidbarkeit, Reduzierbarkeit
0:21:05 Paradoxien und Selbstbezüglichkeit
0:22:07 Semi-Entscheidbarkeit
0:24:02 Rekursive Aufzählbarkeit
0:24:51 Äquivalente Aussagen
0:25:30 2.7 Nicht-entscheidbare Probleme
0:26:32 Gödelnummer einer Turingmaschine
0:26:52 Diagonalsprache
0:28:34 Universelle Turingmaschine
0:30:35 Halteproblem
0:31:48 Das beschränkte Halteproblem
0:31:57 Mehr unentscheidbare Probleme
0:32:46 Unentscheidbarkeit von Leerheit
0:33:50 Postsches Korrespondenzproblem (PKP)
0:34:32 Hilberts 10. Problem - Diophantische Gleichungen
... mehr0:35:05 Abgeschlossenheit entscheidbarer Sprachen
0:35:31 Nebenläufige Ausführung
0:36:11 Terminologie und Konventionen
0:36:26 Komplexitätsmaße
0:37:37 Obere Schranken
0:37:53 Untere Schranken: Lösungsansätze
0:38:43 Eine Komplexitätsklasse
0:41:07 Polynomiale Reduzierbarkeit
0:43:20 Beispiel
0:48:02 Weitere NP-vollständige Probleme
0:48:31 11. Übung
0:49:09 NP-Schwere Reduktionen