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

18 |
0:00:00 Starten
0:00:07 Fortsetzung Informationstheorie
0:01:06 Wiederholung Quellkodierung
0:01:46 Kanalkodierung
0:02:24 Codierung zum Schutz gegen Übertragungsfehler
0:04:17 Paritätscodes - Einfach Binär
0:07:27 Kreuzsicherung
0:12:20 Paritätscodes
0:13:33 Beweis
0:15:09 Paritätscodes gegen Vertauschungsfehler
0:18:42 Bsp: ISBN-10
0:18:56 ISBN
0:19:59 Block-Codes
0:20:31 Hamming-Distanz und Fehlerkorrektur
0:21:58 Maximum-Likelihood-Decoding
0:23:08 Shannon's Theorem
0:23:52 Block-Codes
0:25:13 Beweisskizze
0:26:37 Werbung
0:28:18 Vorlesung Planare Graphen
0:36:07 Proseminar Theoretical Computer Science Classics
0:39:53 ICPC Praktikum
0:42:04 PSE Energieinformatik

17 |
0:00:00 Starten
0:01:45 Thema dieses Kapitels
0:04:52 Material für Informationstheorie
0:05:32 Information
0:12:45 Wiederholung: Rechenregeln Logarithmus
0:13:53 Definition Information
0:14:52 Entropie
0:19:16 Bemerkung zur Entropie
0:19:31 Entropie einer Münze mit Wkt p für Zahl
0:20:44 (Platzsparende) Codierungen
0:22:12 Codierungsbäume
0:26:49 Präfix-Codes
0:29:08 Beispiel: Morse-Alphabet
0:30:15 Quellencodierungstheorem
0:31:47 Beispiel: Shannon-Fano Codierung
0:38:01 Codierungsbaum Shannon-Fano
0:38:59 Beispel: Huffman-Codierung
0:44:36 Optimalität der Huffman-Codierung
0:45:13 Vorbereitendes Lemma
0:47:00 VorbereitendesLemma: Beweis
0:51:10 Beweis - Induktionsschluss
0:57:00 Nachteile der Huffman-Codierung
0:59:05 Lauflängenkodierung

16 |
0:00:00 Starten
0:00:37 Kellerautomaten
0:03:49 Satz
0:05:15 Satz (2)
0:06:09 Beweis
0:30:19 Korollar
0:30:41 Übersicht Chomsky-2
0:32:46 Exkurs
0:34:16 Zwischenfazit zu kontextfreien Grammatiken
0:36:10 Satz (3)
0:38:18 Das Post'sche Korrespondenzproblem
0:39:47 Beweis (2)
0:43:33 Beweisskizze
0:44:07 Beweis (3)
0:45:50 Sprache der korrekten Rechenwege
0:51:59 Lemma
0:52:28 Beweis (4)
1:01:26 Bemerkung
1:02:03 Lemma (2)
1:02:27 Beweis (5)

15 |
0:00:00 Starten
0:00:07 Beweis
0:03:26 Kellerautomaten
0:09:17 Kellerautomaten - Visualisierung
0:10:09 Kellerautomaten - Arbeitsweise
0:18:33 Kellerautomaten - Beispiel
0:27:20 Kellerautomaten - Beispiel 2
0:31:02 Satz (1)
0:35:44 Satz (2)
0:39:19 Satz (3)

14 |
0:00:00 Starten
0:00:07 Wiederholung
0:12:03 Ogden´s Lemma für kontextfreie Sprachen
0:14:31 Beweis
0:29:20 Beweis - Teil 1
0:30:23 Beweis - Teil 2
0:39:23 Beweis - Teil 3
0:41:58 Nutzlose Variablen
0:43:38 Schritt 1
0:47:24 Beispiel: Schritt 1
0:51:28 Schritt 2
0:53:16 Beispiel: Schritt 2
0:56:45 Korollar
0:59:27 Beispielgraph

13 |
0:00:00 Starten
0:00:31 Wiederholung
0:02:13 Die Chmosky Hierarchie
0:08:16 Syntaxbäume
0:10:28 Syntaxbäume - Beispiel
0:15:54 Links/Rechtsabteilung, Eindeutigkeit
0:17:31 Beispiel
0:19:37 Chomsky-Normalform
0:20:56 Die Chomsky Hierarchie
0:21:21 Chomsky-Normalform
0:31:01 Schritt 1
0:34:21 Schritt 2
0:38:20 Schritt 3
0:49:34 Schritt 4
0:53:36 Abhängigkeitsgraph
0:54:42 Schritt 4 – Phase 1
0:56:47 Schritt 4 – Phase 2
1:02:02 Der CYK-Algorithmus
1:05:15 Beweis - Beschreibung des CYK-Algorithmus
1:08:33 CYK-Algorithmus – Beispiel
1:12:31 CYK-Algorithmus – Vorgehen
1:14:50 Beweis - Beschreibung des CYK-Algorithmus
1:15:39 CYK-Algorithmus – Vorgehen
1:16:10 CYK-Algorithmus – Beispiel
1:22:11 CYK-Algorithmus – Vorgehen
1:22:48 Ergebnisse zum Wortproblem