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 10.12.2015, Vorlesung und Übung - 14
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
59 minutes 17 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 10.12.2015, Vorlesung und Übung - 14
14: Vorlesung und Übung|
0:00:00 Starten
0:00:10 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit
0:00:44 Paradoxien und Selbstbezüglichkeit
0:01:28 Entscheidbarkeit
0:01:47 Äquivalente Aussagen
0:02:37 2.7 Nicht-entscheidbare Probleme
0:03:04 Normierung von Turing-Maschinen
0:04:24 Gödelnummer (M) einer Turingmaschine M
0:09:01 Gödelnummer
0:09:59 Beispiel
0:10:39 Diagonalsprache
0:12:09 Kapitel 12
0:12:33 Satz: Diagonalsprache ist unentscheidbar
0:15:53 Korollar
0:16:20 Universelle Turingmaschine
0:25:00 Universelle Turingmaschine: 3Band - 1Band
0:28:18 Halteproblem
0:34:09 Das beschränkte Halteproblem
0:35:10 Mehr unentscheidbare Probleme
0:36:42 Unentscheidbarkeit von Leerheit
0:39:44 7. Übung
0:39:44 Universelle Turingmaschinen
0:41:18 Quines
0:43:17 Unentscheidbarkeit
0:44:24 Der Satz von Rice
0:47:14 Es gibt keine perfekten Virenscanner
0:48:11 Beweis über das Halteproblem
0:52:15 Einschub: Rekursionssatz
0:53:26 Beweis mit Rekursionssatz
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
