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

26: Übung|
0:00:00 Starten
0:00:12 Vorbereitung Klausur: 1. Übungsblatt
0:05:44 2. Übungsblatt
0:06:34 3. Übungsblatt
0:08:49 4. Übungsblatt
0:18:32 5. Übungslbatt
0:25:58 6. Übungsblatt
0:30:05 7. Übungsblatt
0:34:44 8. Übungsblatt
0:41:35 Weihnachtsblatt
0:42:46 10. Übungsblatt
0:45:17 Weiterführende Vorlesungen
0:52:01 11. Übungsblatt
0:55:22 12. Übungsblatt
0:59:14 13. Übungsblatt
1:03:44 14. Übungsblatt

25: Vorlesung und Übung |
0:00:00 Starten
0:02:07 Caesar-Chiffre
0:05:07 Monoalphabetische Verschiebungschiffre
0:06:57 Vigenère-Verschlüsselung
0:20:34 Set Cover
0:27:01 Set Cover Beispiel 1
0:27:37 Set Cover ist NP-vollständig
0:27:53 Beweis ""Set Cover ist NP-hart""
0:35:36 Set Cover Beispiel 2
0:37:40 Beweis F erfüllbar
0:41:18 Bewies ""3SAT ist NP-hart""
0:42:14 Negation in die Blätter drücken
0:43:25 Nichtblattknoten -> Neue Variablen
0:47:21 Clique
0:47:43 Clique Beispiel
0:50:22 Subset Sum
0:50:50 Die Subset Sum Instanz
0:52:51 Integer Linear Programming (ILP)
0:53:30 Directed Hamilton Cycle (DHC)
0:56:23 Umgang mit NP-harten Problemen

24: Vorlesung und Übung |
0:00:00 Starten
0:00:18 Übung: Gedächtnislose Quellen
0:02:16 Übung: Entropiemaximierung
0:06:59 Übung: Decodierbarkeit
0:11:32 Übung: Theoretische Grenzen der Kompression
0:15:27 Übung: Fakten zur Kolmogorov Koplexität
0:20:03 Übung: Einige Beispiele für obere Schranken
0:23:46 Vorlesung: Elias-Fano Kodierung
0:24:37 Vorlesung: Elias-Fano Kodierung - Funktionsweise
0:33:53 Vorlesung: Elias-Fano Kodierung - Anwendung
0:37:15 Vorlesung: Wechselseitiger und bedingter Informationsgehalt
0:47:22 Vorlesung: Verbundentropie und bedingte Entropie
0:49:10 Vorlesung: Übertragungsmodell
0:49:35 Vorlesung: Der Symmetrische Binärkanal
0:53:31 Vorlesung: Transinformation (mutual information)
0:57:41 Vorlesung: Kanalkapazität
1:02:19 Vorlesung: Codierung zum Schutz gegen Übertragungsfehler
1:03:47 Vorlesung: Paritätscodes
1:13:56 Vorlesung: Beispiel ISBN-10
1:14:27 Vorlesung: Block-Codes

20: Vorlesung und Übung |
0:00:00 Starten
0:00:11 Directed Hamilton Cycle (DHC)
0:01:35 Beweis von »DHC ist NP-hart«
0:02:03 Reduktionen
0:02:43 DHC
0:03:34 Beweis von »DHC ist NP-hart«
0:05:07 Ein Knoten pro Variable
0:05:47 Gadget Kj mit 6 Knoten je Klausel
0:08:35 »Vorgesehene« Hamiltonkreise
0:12:12 Unmögliche Hamiltonkreise
0:14:16 Verbindungen der Gadgets
0:18:35 Beispiel
0:27:46 F erfüllbar - Instanz lösbar
0:29:28 Instanz lösbar - F erfüllbar
0:30:41 DHC - Hamilton Circle
0:34:32 Exkurs: Euler-Tour
0:36:11 Gesehene Reduktionen
0:36:53 Komplexität (verallgemeinerter) klassischer Spiele
0:43:48 10. Übung
0:44:23 Integer Linear Programming
0:44:51 ILP: 0-1-Belegung erzwingen
0:45:29 Beispiel: KNAPSACK
0:47:01 Pseudo-polynomieller Knapsack Algorithmus
0:56:04 Approximation von Knapsack
1:01:16 Domino
1:03:34 Domino: Probleme
1:04:00 2-Player Cooperative Dominoes
1:08:19 Weitere Domino-Varianten
1:09:28 Portal 2
1:12:14 3Sat - Super Mario World

23: Vorlesung|
0:00:00 Starten
0:00:42 Thema dieses Kapitels
0:04:32 Information
0:09:03 Wiederholung: Rechenregeln Logarithmus
0:11:49 Entropie
0:13:45 Bemerkungen zur Entropie
0:15:22 Entropie einer Münze mit Wkt p für Zahl
0:16:01 (Platzsparende) Codierungen
0:16:48 Codierungsbäume
0:19:51 Beispiel
0:20:57 Präfix-Codes
0:21:43 Beispiel
0:23:16 Quellencodierungstheorem
0:24:48 Quellencodierungstheorem-Beweis
0:34:37 Shannon-Fano Codierung
0:37:33 Codierungsbaum Shannon-Fano
0:37:46 Bemerkung
0:38:17 Beispiel: Shannon-Fano Codierung
0:38:36 Beispiel: Huffman-Codierung
0:40:41 Huffman-Codierung
0:41:28 Optimalität der Huffman-Codierung
0:41:37 Vorbereitendes Lemma
0:42:44 Vorbreitendes Lemma: Beweis
0:47:00 Beweis-Induktionsschluss
0:51:00 Nachteile der Huffman-Codierung
0:52:49 Lauflängenkodierung
0:59:53 Succinct Datenstrukturen
1:05:59 Bitvektoren mit Zugriff und Rank Operation
1:14:23 Komprimierte Datenstrukturen
1:16:32 Komprimierte Datenstrukturen: Wavelet Tree
1:26:49 Elias-Fano Kodierung

22: Vorlesung und Übung|
0:00:00 Starten
0:00:10 2: Berechenbarkeitstheorie | 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These
0:00:41 Berechenbarkeit Hauptergebnis
0:01:26 2.2 Intuitiver Berechenbarkeitsbgegriff
0:01:48 Beispiel
0:07:15 2.3 LOOP-, WHILE-, GOTO (=Registermaschinen) und RAM-Berechenbarkeit
0:08:41 LOOP-Programme
0:10:29 Äquivalenz von Maschinenmodellen
0:12:04 Markov-Algorithmen
0:14:08 Zellularautomaten
0:15:16 2.4 Primitiv rekursive Funktionen
0:16:11 2.5 Die Ackermannfunktion
0:18:06 Mehr schnell wachsende Funktionen
0:19:06 Wissen über Fleißige Biber
0:20:12 2.6 Halterproblem, Unentscheidbarkeit, Reduzierbarkeit
0:21:05 Paradoxien und Selbstbezüglichkeit
0:22:07 Semi-Entscheidbarkeit
0:24:02 Rekursive Aufzählbarkeit
0:24:51 Äquivalente Aussagen
0:25:30 2.7 Nicht-entscheidbare Probleme
0:26:32 Gödelnummer einer Turingmaschine
0:26:52 Diagonalsprache
0:28:34 Universelle Turingmaschine
0:30:35 Halteproblem
0:31:48 Das beschränkte Halteproblem
0:31:57 Mehr unentscheidbare Probleme
0:32:46 Unentscheidbarkeit von Leerheit
0:33:50 Postsches Korrespondenzproblem (PKP)
0:34:32 Hilberts 10. Problem - Diophantische Gleichungen
0:35:05 Abgeschlossenheit entscheidbarer Sprachen
0:35:31 Nebenläufige Ausführung
0:36:11 Terminologie und Konventionen
0:36:26 Komplexitätsmaße
0:37:37 Obere Schranken
0:37:53 Untere Schranken: Lösungsansätze
0:38:43 Eine Komplexitätsklasse
0:41:07 Polynomiale Reduzierbarkeit
0:43:20 Beispiel
0:48:02 Weitere NP-vollständige Probleme
0:48:31 11. Übung
0:49:09 NP-Schwere Reduktionen