Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Karlsruher Institut für Technologie (KIT)
27 episodes
8 months ago
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 15.12.2015, Vorlesung - 15
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 11 minutes 6 seconds
9 years ago
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
1:07:56 Äquivalenz von NTIME und OTIME
1:08:35 Die 1.000.000$ Frage
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
