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

18 |
0:00:00 Start
0:00:11 Kodierung zum Schutz gegen Übertragungsfehler
0:01:42 Paritätscodes - Einfach binär
0:04:45 Kreuzsicherung
0:10:05 Paritätscodes
0:16:27 Block-Codes
0:17:03 Hamming-Distanz und Fehlerkorrektur
0:21:23 Beispiel

17 |
0:00:00 Start
0:03:24 Material für Informationstheorie
0:03:57 Information
0:12:08 Wiederholung: Rechenregeln Logarithmus
0:17:45 Entropie
0:24:46 Entropie zu einer Münze
0:26:09 (Platzsparende) Kodierungen
0:28:48 Präfix-Codes
0:31:13 Kodierungsbäume
0:36:18 Beispiel: Morse-Alphabet
0:37:38 Quellenkodierungstheorem
0:39:41 Beispiel: Shannon-Fano-Kodierung
0:44:44 Kodierungsbaum Shannon-Fano
0:45:44 Beispiel: Huffman-Kodierung
0:49:25 Vorbereitendes Lemma
0:55:09 Beweis - Induktionsschluss
1:00:43 Nachteile der Huffman-Kodierung
1:02:46 Lauflängenkodierung
1:10:49 Kodierung zum Schutz gegen Übertragungsfehler

16 |
0:00:00 Start
0:00:21 Letzte Vorlesung
0:07:22 Wdh.: Greibach-Normalform, Kellerautomat
0:11:54 Kellerautomaten
0:15:10 Beispiel - Greibach-Normalform
0:18:13 Beipiel - Kellerautomat
0:21:23 Beweis: Greibach-Normalform -> NPDA
0:27:20 Beweis: NPDA -> Kontextfreie Grammatik
0:52:53 Zwischenfazit zu kontextfreien Grammatiken
0:59:24 Das Post´sche Korrespondenzproblem
1:06:53 Eindeutigkeit von kontextfreien Grammatiken
1:10:13 Sprache der Korrekten Rechenwege

15 |
0:00:00 Start
0:00:19 Letzte Vorlesung
0:01:21 Heutige Vorlesung
0:03:24 Weiere Eigenschaften kontextfreier Sprachen
0:17:59 Ein Maschinenmodell für Chomsky-2
0:23:18 Greibach-Normalform
0:26:01 Beweis
0:53:04 Kellerautomaten

14 |
0:00:00 Start
0:00:31 Übersicht
0:04:47 Das Pumping-Lemma für kontextfreie Sprachen
0:13:52 Ogden´s Lemma für kontextfreie Sprachen
0:15:48 Beweis von Ogden´s Lemma
0:28:07 Echtheit der Chomsky-Hierarchie
0:30:18 Beweis
0:44:49 Eigenschaften kontextfreier Sprachen
0:48:12 Nutzlose Variablen
0:51:27 Schritt 1
1:01:10 Schritt 2
1:05:22 Endliche kontextfreie Sprachen
1:08:51 Beispielgraph

13 |
0:00:00 Start
0:01:20 Beispiele
0:04:40 Grammatiken
0:06:42 Bemerkungen
0:11:29 Die Chomsky-Hierarchie
0:24:56 Chomsky-0-Grammatiken und Semientscheidbarkeit
0:30:11 Beweis – Beschreibung der Grammatik G
0:40:28 Chomsky-3-Grammatiken und reguläre Sprachen
0:42:26 Beweis
0:53:06 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen
0:57:03 Satz