Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

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