Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 15.12.2015, Vorlesung - 15

15: Vorlesung|
0:00:00 Starten
0:01:24 Halteproblem
0:02:27 Das beschränkte Halteproblem
0:02:57 Mehr unentscheidbare Probleme
0:03:15 Unentscheidbarkeit von Leerheit
0:09:13 Unentscheidbarkeit von Vollständigkeit
0:09:31 Metaprogrammierung
0:11:03 Postsches Korrespondenzproblem (PKP)
0:12:16 Beispiel
0:19:04 PCP ist semientscheidbar
0:20:25 PCP ist unentscheidbar
0:22:56 Hilberts 10. Problem- Diophantische Gleichungen
0:25:32 Abgeschlossenheit entscheidbarer Sprachen
0:27:58 Anwendung der nebenläufigen Ausführung
0:30:05 Nebenläufige Ausführung
0:33:51 2 Kompexitätstheorie
0:35:04 Terminologie und Konventionen
0:35:47 Komplexitätsmaße
0:38:34 Beispiel: Hamiltonkreisproblem
0:41:42 Beispiel Rucksackproblem
0:43:32 Beispiel: Handlungsreisendenproblem
0:46:08 Obere Schranken
0:47:05 Untere Schranken
0:51:19 Untere Schranken: Lösungsansätze
0:53:32 Eine Komplexitätsklasse
0:55:14 Polynom
0:56:00 Komplexitätsklasse P
0:57:02 P für verschiedene Maschinenmodelle
0:59:19 Transformation Optimierungsproblem -> Entscheidungsproblem
1:02:22 Noch eine Komplexitätsklasse
1:05:15 Komplexitätsklasse NP
1:05:50 Beispiel: Rucksackproblem
1:06:49 Alternative Definition von NTIME: Orakel
... mehr1:07:56 Äquivalenz von NTIME und OTIME
1:08:35 Die 1.000.000$ Frage