Theoretische Grundlagen der Informatik, Vorlesung, WS17/18 Karlsruher Institut für Technologie (KIT)

19 |
0:00:00 Starten
0:01:39 Rückblick: Chomsky Typ 3
0:04:53 Rückblick: Chomsky-3 Verfahren
0:22:29 Rückblick: Chomsky-2
0:35:13 Rückblick: Chomsky-0/1
0:40:32 Entscheidbarkeit
0:47:05 Domino
0:53:04 2-PLAYER COOPERATIVE DOMINOES

18 |
0:00:00 Starten
0:03:53 Information
0:12:40 Entropie
0:18:49 (Platzsparende) Codierung
0:20:33 Codierungsbäume
0:25:54 Präfix-Codes
0:28:27 Quellencodierungstheorem
0:29:58 Beispiel: Shannon-Fano Codierung
0:38:11 Beispiel: Huffman-Codierung
0:46:53 Vorbereitendes Lemma
0:56:09 Beweis - Induktionsschluss
1:05:03 Lauflängenkodierung

17 |
0:00:00 Starten
0:00:24 Übersicht Chomsky-2
0:03:13 WDh.: Greibach-Normalform, Kellerautomat
0:09:07 Beweis
0:47:57 Korollar
0:48:46 Exkurs
0:50:37 Zwischenfazit zu kontextfreien Grammatiken
0:53:05 Unentscheidbare Probleme für kontextfreie Grammatiken
0:55:26 Das Post'sche Korrespondenzproblem
1:03:51 Eindeutigkeit von kontextfreien Grammatiken
1:05:26 Beweisskizze
1:09:07 Sprache der korrekten Rechenwege

16 |
0:00:00 Starten
0:01:12 Chomsky Hierarchie
0:15:28 Chomsky-0-Grammatiken und DTM's
0:28:42 Konstruktion von Grammatiken
0:46:58 Sprache der korrekten Klammerausdrücke
0:57:09 Chomsky-Normalform
1:08:19 Der Cocke-Younger-Kasami Algorithmus

15 |
0:00:00 Starten
0:00:19 Kontextfreie Sprachen, Kontextfreie Grammatiken
0:06:01 Pumping-Lemma für kontextfreie Sprachen
0:08:05 Ogden's Lemma für kontextfreie Sprachen
0:23:12 Satz
0:37:41 Nutzlose Variablen
0:54:28 Korrolar
0:58:14 Beispielgraph

14 |
0:00:00 Starten
0:00:22 Die Chomsky Hierarchie
0:08:09 Typ-2/Kontextfrwiw Grammatiken
0:08:51 Typ-2/ Grammatiken: Beispiel 1
0:09:25 Typ-2/ Grammatiken: Beispiel 2
0:11:56 Syntacbäume
0:13:34 Syntaxbäume Beispiel
0:18:27 Links/ Rechtsabteilung, Eindeutigkeit
0:20:14 Beispiel
0:23:08 Chomsky- Normalform
0:30:41 Schritt 1
0:34:39 Schritt 2
0:38:44 Schritt 3
0:47:14 Schritt 4
0:52:48 Abhängigkeitsgraph
0:54:23 Schritt 4- Phase 1
0:56:45 Schritt 4 - Phase 2
1:01:32 Sonderbehandlung
1:02:24 Der CYK-Algorithmus
1:04:53 Beweis - Beschreibung des CYK-Algorithmus
1:09:04 CYK- Algorithmus - Beispiel
1:10:47 Beweis - Beschreibung des CYK-Algorithmus
1:12:54 CYK-Algorithmus - Vorgehen
1:24:32 Ergebnisse zum Wortproble