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

21: Vorlesung | 0:00:00 Starten 0:03:23 1.1 Allgemeines 0:04:18 1.1.1 Grammatiken 0:05:19 1.1.2 Chomsky-Hierachie 0:11:12 1.1.3 Wortproblem 0:12:17 1.1.4 Syntaxbäume 0:13:02 1.2 Reguläre Sprachen 0:14:03 1.2.1 (Deterministische) endliche Automaten 0:14:30 1.2.2 Nichtderterministische (endliche) Automaten 0:19:52 1.2.3 Reguläre Ausdrücke 0:27:01 1.2.4 Das Pumping Lemma (für reguläre Sprachen) 0:33:11 1.2.5 Äquivalenzrelationen und Minimalautomaten 0:46:13 1.2.6 Abschlusseigenschaften 0:58:50 1.3 Kontextfreie Sprachen 0:59:11 1.3.1 Normalformen 1:01:14 1.3.2 Das Pumping Lemma

19: Vorlesung | 0:00:00 Starten 0:03:08 Beweis SUBSET SUM 0:03:31 Beweis ""SUBSET SUM ist NP-hart"" 0:03:34 SUBSET SUM 0:06:04 Die SUBSET SUM Instanz 0:10:08 Beispiel 0:13:55 Beweisidee 0:18:29 F erfüllbar -> Instanz lösbar 0:20:42 Instanz lösbar -> F erfüllbar 0:23:44 Beispiel Rucksackproblem 0:24:29 Rucksackproblem 0:26:11 Reduktionen 0:26:56 PARTITION 0:28:30 Beweis SUBSET SUM <= pPARTITION 0:38:39 Integer Linear Programming (ILP) 0:40:14 Beweis von ""ILP ist NP-hart"" 0:41:18 Ist ILP in NP ? 0:44:52 Umgang mit NP-harten Probleme 0:55:29 Optimierungsprobleme 0:56:11 NP vollständig 0:57:26 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP) 1:00:20 alpha-Approximation von TSP 1:01:13 HamiltonCycle<=palpha-Approximation von TSP 1:05:45 Pseudopolynomielle Algorithmen 1:07:56 Beispiel Rucksackproblem

18: Vorlesung und Übung| 0:00:00 Starten 0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig 0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart"" 0:02:47 Wiederholung: Negationen in die Blätter drücken 0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen 0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz 0:05:05 Exkurs: 2SAT ∈ P 0:10:27 CLIQUE 0:14:22 Beweis Clique ∈ NP 0:15:01 Beweis von ""CLIQUE ist NP-hart"" 0:19:57 Beispiel 0:29:19 VERTEX COVER (Knotenüberdeckung) 0:31:14 Beweis VERTEX COVER ∈ NP 0:31:32 Beweis von ""VERTEX COVER ist NP-hart"" 0:39:11 Gesehene Reduktionen 0:39:39 Beweistechniken für A ≤p B: Spezialfälle 0:43:36 Beweistechniken für A ≤p B: Uminterpretation 0:44:28 Beweistechniken für A ≤p B: Gadgets 0:46:27 Beweistechniken für A ≤p B: Randbedingungen 0:47:33 9. Übung 0:47:35 Komplexitätsklassen - Einführung 0:56:38 Komplexitätsklassen - Fortführung 1:03:57 3SAT ≤p 3COLOR - Einführung 1:05:16 3SAT ≤p 3COLOR - Fortführung 1:09:00 3SAT ≤p 3COLOR - mit Gadget 1:14:08 1-aus-3SAT 1:20:37 XOR-(3)SAT 1:23:07 Einige weitere Varianten 1:26:08 PLANAR 3SAT 1:28:05 Knapsack und Subset Sum

17: Vorlesung| 0:00:00 Starten 0:00:53 Wiederholung Komplexitätstheorie 0:08:54 Polynominale Reduzierbarkeit 0:09:55 Beispiel 0:10:57 NP-harte und Np-Vollständige Probleme 0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ? 0:13:50 SAT: Das Erfüllbarkeitsproblem 0:17:03 Beweis von SAT 0:17:31 Beweis das SAT-NP-hart ist. 0:19:45 Variablen für F 0:24:53 Die Architektir von F= 0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist 0:31:44 Es kann nur einen geben 0:33:05 Randbedingung 0:37:00 Anfangsbedingung 0:38:46 Übergangsbedingung Ü1, t->t+1 0:42:01 Übergangsbedingung Ü2, t->t+1 0:42:42 Endebedingung E 0:43:56 Gesamtgröße von F 0:48:06 Weitere NP-vollständige Probleme 0:55:04 3SAT (KNF) 0:56:56 Satz: 3SAT ist NP-vollständig 0:58:29 Beweis ""3SAT ist NP-hart"" 1:00:12 Negation in die Blätter drücken 1:01:23 Beispiel 1:03:04 Nichtblattknoten -> Neue Variablen 1:05:52 Beispiel 1:06:34 Erfüllbarkeitsäquivalenz von F1 1:07:57 Beispiel 1:10:15 F1 -> 3KNF

16: Übung und Vorlesung| 0:00:00 Starten 0:00:56 Rückblick: Chomsky-3 0:05:29 Rückblick: Chomsky-3 Verfahren 0:16:18 Rückblick: Chomsky-2 0:19:33 Rückblick: Chomsky-2 Verfahren 0:27:23 Rückblick: Chomsky-0/1 0:30:41 Rückblick: Entscheidbarkeit 0:36:54 Ausblick: Komplexitätstheorie 0:38:54 Video: Game of Life Automat 0:43:27 Video: Variante von Game of Life mit realen Werten 0:45:23 Vorlesung 0:46:03 Kapitel 2: Komplexitätstheorie 0:46:34 Obere Schranken 0:46:54 Untere Schranken 0:47:23 Untere Schranken: Lösungsansätze 0:49:08 Eine Komplexitätsklasse 0:50:00 Komplexitätsklasse P 0:50:31 P für verschiedene Maschinenmodelle 0:52:33 Komplexitätsklasse NP 0:53:29 Beispiel: Rucksackproblem 0:54:05 Alternative Definition von NTIME: Orakel 0:55:26 Äquivalenz von NTIME und OTIME 0:55:47 Die 1 000 000 $ Frage 0:57:09 Eine Komplexitätshierarchie 0:59:59 Polynomiale Reduzierbarkeit 1:02:10 Beispiel 1:09:05 NP-harte und NP-vollständige Probleme 1:15:09 Ein einfacher Weg zu Ruhm und Reichtum? 1:20:16 SAT: Das Erfüllbarkeitsproblem 1:23:34 Beweis von SAT ∈ NP