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 17.12.2015, Vorlesung und Übung - 16
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 24 minutes 21 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 17.12.2015, Vorlesung und Übung - 16
16: Übung und Vorlesung|
0:00:00 Starten
0:00:56 Rückblick: Chomsky-3
0:05:29 Rückblick: Chomsky-3 Verfahren
0:16:18 Rückblick: Chomsky-2
0:19:33 Rückblick: Chomsky-2 Verfahren
0:27:23 Rückblick: Chomsky-0/1
0:30:41 Rückblick: Entscheidbarkeit
0:36:54 Ausblick: Komplexitätstheorie
0:38:54 Video: Game of Life Automat
0:43:27 Video: Variante von Game of Life mit realen Werten
0:45:23 Vorlesung
0:46:03 Kapitel 2: Komplexitätstheorie
0:46:34 Obere Schranken
0:46:54 Untere Schranken
0:47:23 Untere Schranken: Lösungsansätze
0:49:08 Eine Komplexitätsklasse
0:50:00 Komplexitätsklasse P
0:50:31 P für verschiedene Maschinenmodelle
0:52:33 Komplexitätsklasse NP
0:53:29 Beispiel: Rucksackproblem
0:54:05 Alternative Definition von NTIME: Orakel
0:55:26 Äquivalenz von NTIME und OTIME
0:55:47 Die 1 000 000 $ Frage
0:57:09 Eine Komplexitätshierarchie
0:59:59 Polynomiale Reduzierbarkeit
1:02:10 Beispiel
1:09:05 NP-harte und NP-vollständige Probleme
1:15:09 Ein einfacher Weg zu Ruhm und Reichtum?
1:20:16 SAT: Das Erfüllbarkeitsproblem
1:23:34 Beweis von SAT ∈ NP
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
