Education
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 1:07:56 Äquivalenz von NTIME und OTIME 1:08:35 Die 1.000.000$ Frage