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

12 | 0:00:00 Starten 0:00:28 Grammatiken 0:01:26 Beispiele 0:05:33 Grammatiken 0:07:12 Bemerkungen 0:08:32 Beispiel 0:09:22 Die Chomsky Hierarchie 0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:24:58 Beweis - Beschreibung der Grammatik G 0:28:28 Beweis - Zusammenfassung 0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:32:04 Zwischenfazit 0:34:01 Chomsky-3-Grammatiken und reguläre Sprachen 0:35:27 Beweis 0:42:00 Bemerkung 0:43:05 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen 0:48:01 Satz 0:48:59 Bemerkung 0:49:17 Wiederholung: Das Problem CLIQUE 0:50:02 Satz 0:54:02 Bemerkung 1 0:54:53 Bemerkung 2 0:56:12 Notation 0:57:15 Typ-2 / Kontextfreie Grammatiken 0:57:40 Typ-2 Grammatiken: Beispiel 1 0:58:51 Typ-2 Grammatiken: Beispiel 2 1:00:44 Typ-2 Grammatiken: Beispiel 3

11 | 0:00:00 Starten 0:02:50 Approximation mit relativer Gütegarantie 0:03:31 Definition 0:04:49 Approximierbarkeit von COLOR 0:18:45 Approximierbarkeit von TSP 0:28:12 Approximationsschemata 0:38:45 Ein FPAS für KNAPSACK (1) 0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK 0:43:49 Ein FPAS für KNAPSACK (2) 0:58:51 Ein allgemeineres Resultat

10 | 0:00:00 Starten 0:03:37 VerallgemeinerteNP-Schwere 0:07:17 Das Problem INTEGER PROGRAMMING 0:26:15 Pseudopolynomiale Algorithmen 0:29:56 Beispiel: Problem KNAPSACK 0:40:20 Starke NP-Vollständigkeit 0:44:14 Absolute Approximationsalgorithmen 0:46:31 Das allgemeine KNAPSACK-Suchproblem 0:57:09 Approximation mit relativer Gütegarantie 0:59:53 Beispiel: Greedy-Algorithmus für KNAPSACK

09 | 0:00:00 Starten 0:06:41 Das Problem SUBSET SUM 0:07:46 NP-Vollständigkeit von SUBSET SUM 0:24:03 Das Problem PARTITION 0:31:06 Das Problem KNAPSACK 0:37:32 Auswirkungen auf die Frage P=NP 0:45:42 Zusammenfassung 0:47:57 Die Klassen NPI, co-P und co-NP 0:54:22 Das TSP-Komplement-Problem 0:57:40 Lemma 1:00:00 Bemerkung 1:01:25 Das Problem Subgraphisomorphie 1:03:14 Das Problem Graphismorphie 1:09:06 Suchprobleme 1:10:21 Beispiel: TSP-Suchproblem 1:11:03 Beispiel: Hamilton–Kreis Suchproblem 1:12:04 Aufzählungsprobleme 1:12:44 Reduzierbarkeit für Suchprobleme 1:15:36 Orakel-Turing-Machine 1:19:40 NP-schwer 1:20:39 Beweisskizze

08 | 0:00:00 Starten 0:00:37 Wiederholung: NP-Vollständigkeit 0:06:10 Wiederholung: Transitivität der poly. Transformation 0:06:40 Wiederholung: Korollar 0:07:37 Wiederholung: Das Problem SAT (satisfiability) 0:12:17 Das Problem 3-SAT 0:13:13 Beweis: NP-Vollständigkeit von 3-SAT 0:30:07 Das Problem 2SAT 0:34:40 Das Problem MAX2SAT 0:38:02 Das Problem CLIQUE 0:39:32 Beweis: NP-Vollständigkeit von CLIQUE 0:51:19 Das Problem COLOR 0:54:56 Beweis: NP-Vollständigkeit von 3COLOR 0:57:29 Konstruktion von 3COLOR-Instanz G 1:01:05 Beispielgraph zur Reduktion 1:04:20 Polynomialität der Reduktion 1:04:56 Instanz I erfüllbar => Instanz G erfüllbar 1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar 1:08:02 Das Problem EXACT COVER 1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:28 Konstruktion von (X,S) 1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung 1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung