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.11.2015, Vorlesung - 08
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 21 minutes 38 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 17.11.2015, Vorlesung - 08
08: Vorlesung |
0:00:00 Starten
0:00:07 Wiederholung
0:01:05 1.3.2 Das Pumping Lemma
0:03:48 Beweis Pumping Lemma
0:13:10 Hilfs Lemma
0:14:39 Anwendung Pumping Lemma
0:22:02 Faustregeln für Beweise mit dem Pumping Lemma
0:26:21 Abschlusseigenschaften
0:27:26 Abgeschlossenheit von KFG unter Vereinigungsmengen
0:29:37 Abgeschlossenheit von KFG unter Produktbildungen
0:30:38 Abgeschlossenheit von KFG unter *
0:33:25 Nichtabgeschlossenheit von KFG
0:38:23 1.3.4 Der CYK-Algorithmus ( Das Wortproblem für kontextfreie Sprachen )
0:41:07 CYK Algorithmus
0:44:29 Beispiel
0:52:24 Impementierung durch dynamische Programmierung
0:55:01 Analyse
1:00:32 1.3.5 Kellerautomaten
1:06:20 Konfiguration einer Kellermaschine
1:06:48 Funktionsweise einer Kellermaschine
1:09:07 Kellermaschine als Akzeptor
1:13:09 Beispiel
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
