Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Dozentin: Prof. Dr. Dorothea Wagner | Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: http://webcast.kit.edu
http://www.kit.edu/
17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 31.01.2019
17 | 0:00:00 Start 0:00:05 Thema dieses Kapitels 0:05:25 Material für Informationstheorie 0:06:28 Information 0:08:45 Beispiel 0:16:13 Wiederholung: Rechenregeln Logarithmus 0:17:53 Beispiel 2 0:20:11 Entropie 0:25:08 Bemerkung zur Entropie 0:29:31 (Platzsparende) kodierungen 0:33:25 Präfix-Codes 0:35:00 Codierungsbäume 0:41:32 Quellenkodierungstheorem 0:43:27 Beispiel: Schanon-Fano Kodierung 0:51:21 Beispiel: Huffman-Kodierung 0:56:30 Vorbereitendes Lemma 1:05:38 Beweis –Induktionsschluss 1:11:48 Nachteile der Huffman-Kodierung 1:15:27 Lauflängenkodierung 1:21:34 Geometrische Verteilung 1:23:07 Kodierung zum Schutz gegen Übertragungsfehler