18 | 0:00:00 Start 0:00:26 Werbung 0:01:14 Vorlesung ,,Algorithmen für planare Graphen"" 0:02:53 Proseminar ,,Algorithmen für NP-schwere Probleme"" 0:05:28 ICPC Praktikum 0:07:38 Kodierung zum Schutz gegen Übertragungsfehler 0:12:34 Paritätscodes - Einfach binär 0:18:38 Kreuzsicherung 0:25:26 Paritätscodes 0:28:05 Beweis 0:30:29 Paritätscodes gegen Vertauschungsfehler 0:36:17 Bsp:ISBN-10 0:40:51 Block-Codes 0:41:50 Hamming-Distanz und Fehlerkorrektur 0:46:58 Block-Codes 0:49:17 Beispiel

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

16 | 0:00:00 Start 0:00:32 Letzte Vorlesung 0:02:51 Wdh.: Greibach-Normalform, Kellerautomat 0:06:32 Beispiel - Greibach-Normalform 0:12:41 Beispiel - Kellerautomat 0:17:47 Beweis: Greibach-Normalform -NPDA 0:26:14 Übersicht 0:27:41 Beweis:NPDA - kontextfreie Grammatik 0:51:16 Exkurs 0:55:11 Zwischenfazit zu kontextfreien Grammatiken 0:57:12 Unentschedbare Probleme für kontextfreie Grammatiken 1:00:05 Das Post'sche Korrespondenzproblem 1:01:10 Beweis 1:06:43 Eindeutigkeit von kontextfreien Grammatiken 1:09:01 Sprache der korrekten Rechenwege 1:27:34 Zusammenfassung Chomsky-Hierarchie

15 | 0:00:00 Start 0:02:19 weitere Eigenschaften kontextfreier Sprachen 0:12:03 Ein maschinellmodell für Chomsky-2 0:18:04 Greibach-Normalform 0:21:01 Beweis - Ersetzung 0:29:08 Beweis - Definitionen 0:30:57 Beweis - Invarianten 0:36:26 Beweis - Verfahren Schritt 1 0:45:30 Beweis - Verfahren Schritt 2 0:50:05 Beweis - Verfahren Schritt 3 0:53:21 Kellerautomaten 0:59:08 Kellerautomaten - Arbeitsweise 1:15:30 Ein Maschinenmodell für Chomsky-2

14 | 0:00:00 Start 0:06:36 Das Pumping-Lemma für kontextfreie Sprachen 0:10:42 Ogden´s Lemma für kontextfreie Sprachen 0:14:06 Beweis von Odgen´s Lemma 0:29:34 Bemerkung 0:30:52 Echtheit der Chomsky-Hierarchie 0:32:47 Beweis - Teil 1 0:33:46 Beweis - Teil 2 0:48:59 Beweis - Teil 3 0:55:39 Eigenschaften kontextfreier Sprachen 0:58:31 Nutzlose Variablen 1:00:00 Schritt 1 1:07:39 Schritt 2

13 | 0:00:00 Start 0:00:09 Letzte Vorlesung 0:08:30 heutige Themen 0:09:05 Syntaxbäume 0:13:44 Eindeutigkeit 0:19:08 Chomsky-Normalform 0:52:24 CYK-Algorithmus

12 | 0:00:00 Start 0:00:31 Grammatiken, Beispiele 0:09:52 Grammatiken, Bemerkungen 0:16:13 Die Chomsky Hierarchie 0:29:17 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:36:03 Beweis - Beschreibung der Grammatik G 0:42:30 Beweis - Zusammenfassung 0:49:13 Chromsky-3 Grammatiken und reguläre Sprachen 1:02:28 Chromsky-1 Grammatiken bzw. kontextsensitive Sprachen 1:09:49 Wiederholung: Das Problem CLIQUE 1:20:25 Typ-2 / Kontextfreie Grammatiken

11 | 0:00:00 Start 0:00:15 Letzte Vorlesung 0:03:09 Definition 0:09:54 Metrisches TSP 0:20:53 Bemerkungen zur Approximierbarkeit 0:23:46 Approximationsschemata 0:29:50 Ein FPTAS für max-KNAPSACK 0:53:01 min-VERTEX-COLOR und min-EDGE-COLOR 0:54:39 Nicht-Existenz eines FPTAS 1:04:07 Approximierbarkeit von COLOR 1:14:46 Ein allgemeines Resutat

10 | 0:00:00 Start 0:01:01 Verallgemeinerte NP-Schwere 0:03:38 Das Problem INTEGER PROGRAMMING 0:07:18 INTEGER PROGRAMMING ist NP-schwer 0:15:12 Bemerkungen 0:23:00 Pseudopolynomiale Algorithmen 0:33:54 Starke NP-Vollständigkeit 0:40:34 Absolute Approximationsalgorithmen 0:44:01 Das allgemeine KNAPSACK-Suchproblem 0:47:08 Negativ-Resultat 0:50:24 (Kontrapositions-)Beweis 0:55:47 Approximation mit relativer Gütegarantie 0:57:13 Genereller Ansatz 1:06:09 Grenzen für den Greedy-Algorithmus

09 | 0:00:00 Start 0:00:57 Letzte Vorlesung 0:20:50 Diese Vorlesung 0:20:57 Das Problem PARTITION 0:28:58 Das Problem KNAPSACK 0:40:03 Zusammenfasung 0:59:24 Das Problem Subgraphisomorphie 1:00:45 Das Problem Graphisomorphie 1:02:28 Die Polynomielle Hierarchie 1:11:31 Suchprobleme 1:17:35 Aufzählungsprobleme

08 | 0:00:00 Start 0:00:22 Letzte Vorlesung 0:06:59 Plan für heute 0:09:46 Pas Problem 3SAT 0:11:29 Beweis: NP-Vollständigkeit von 3SAT 0:30:58 Das Problem 2SAT 0:31:54 Das Problem MAX2SAT 0:33:51 Das Problem CLIQUE 0:35:32 Beweis: NP - Vollständigkeit von CLIQUE 0:48:25 Das Problem COLOR 0:50:25 NP-Vollständigkeit von 3COLOR 0:52:26 Konstruktion von 3COLOR-Instanz G 0:55:48 Polynomialität der Reduktion 0:56:35 Instanz/ erfüllbar 1:03:01 Zwischenstand Polynomiale Reduktion 1:13:41 Das Problem EXACT COVER 1:16:23 NP - Vollständigkeit von EXACT COVER 1:18:00 Konstruktion

07 | 0:00:00 Start 0:00:03 NP-Vollständigkeit für Sprachen 0:03:38 NP-Vollständigkeit für Entscheidungsprobleme 0:05:28 Transitivität der poly. Transformation 0:06:59 Beobachtung 0:10:58 Das Problem SAT (satisfiability) 0:16:04 Weitere Beispiele für SAT-Instanzen 0:17:42 Der Satz von Cook (Steven Cook, 1971) 0:22:03 Beweis: das Setup 0:28:37 Beweis: Konstruktion der Variablen 0:32:52 Beweis: Zielsetzung 0:37:44 Beweis: Konstruktion der Klauseln 0:38:03 Klauselgruppe 1: 0:39:46 Klauselgruppe 2: 0:40:36 Klauselgruppe 3: 0:41:32 Klauselgruppe 4: 0:44:44 Klauselgruppe 5: 0:45:27 Klauselgruppe 6: 0:47:04 Klauselgruppe 6,1: 0:48:59 Klauselgruppe 6,2: 0:52:30 Zwischenbilanz 0:58:13 Polynomialität der Transformation 0:58:34 Polynomialität - Klauselgruppe 1: 0:59:31 Polynomialität - Klauselgruppe 2: 1:00:12 Polynomialität - Klauselgruppe 3: 1:00:45 Polynomialität - Klauselgruppe 4: 1:01:31 Polynomialität - Klauselgruppe 5: 1:01:44 Polynomialität - Klauselgruppe 6,1: 1:02:15 Polynomialität - Klauselgruppe 6,2: 1:04:09 Heute im Rückblick: Der Satz von Cook

06 | 0:00:00 Start 0:00:09 Letzte Vorlesung 0:03:24 Die Universelle Sprache 0:14:02 Satz von Rice – Motivation 0:17:55 Bemerkungen zum Satz von Rice 0:22:13 Das Post'sche Korrespondenzproblem 0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen 0:32:25 Komplexitätstheorie 0:34:36 Wie sieht ein Problem aus? 0:37:46 Definition: Problem 0:40:37 Definition:Kodierungsschema 0:46:51 Äquivalenz von Kodierungsschemata 0:48:35 Entscheidungsprobleme 0:50:57 Korrespondenz von Entscheidungsproblemen und Sprachen 0:52:43 Entscheidungsprobleme und Turing-Maschinen 0:54:34 Zeitkomplexität 0:57:38 Die Klasse P 1:01:00 Schwierigkeit von Entscheidungs- und Optimierungsproblem 1:04:53 Algorithmus OPT-TOUR (als Beweis) 1:10:08 Bemerkungen zum Algorithmus 1:13:17 Zwischenstand Komplexitätstheorie 1:17:01 Die Nichtdeterministische Turing-Maschine 1:23:02 Übertragung auf Entscheidungsprobleme II

05 | 0:00:00 Start 0:00:10 Letzte Vorlesung 0:09:00 Beispiel - Turing Maschine 0:13:57 Bemerkungen zur TM 0:15:23 Definition zur TM 0:18:43 Notation: Konfiguration 0:19:54 Beispiel: Konfiguration 0:26:21 Definition: berechenbar / totalrekursiv 0:28:10 Beispiel 0:34:10 Entscheidbarkeit und Berechenbarkeit 0:39:01 Korollar 0:40:51 Die Church'sche These 0:44:25 Erweiterung der Turing-Maschine 0:51:23 Die Universelle Turing-Maschine 0:54:51 Die Gödelnummer 0:57:52 Die Gödelnummer - Bemerkungen 1:00:43 Die Gödelnummer - Beispiel 1:01:53 Definition 1:04:27 Die Diagonalsprache 1:09:32 Die Diagonalsprache - Veranschaulichung 1:10:40 Unentscheidbarkeit der Diagonalsprache 1:13:33 Korollar 1:14:03 Paradoxien und Selbstbezüglichkeit 1:15:46 Halteproblem

04 | 0:00:00 Start 0:00:03 letzte Vorlesung - alternative Sicht 0:04:48 Alternative Sicht - Beispiel 0:13:20 Heutiges Thema (Frage, Antwort) 0:20:21 Definitionen: Rechtsinvarianz und Index 0:27:56 Nerode-Relation 0:31:10 Satz von Nerode 0:50:10 Korollar 0:52:20 Minimalität des Äquivalenzklassenautomats 0:59:19 Zusammenfassung 1:07:12 Turing-Maschinen und Berechenbarkeit 1:08:42 Die Registermaschine (RAM) 1:14:26 Die Turing-Maschine (TM)

03 | 0:00:00 Start 0:00:03 Rückblick 0:04:19 Verallgemeinertes PL für reguläre Sprachen 0:16:10 Beispiel (3) - Anwendung Verallgemeinertes PL 0:24:06 Minimierung von Automaten - Äquivalenzklassenautomat 0:27:47 Finden nicht überflüssiger Zustände 0:31:00 Beispiel 0:37:13 Äquivalenz 0:46:38 Der Äquivalenzklassenautomat 1:04:07 Zeugen für Nichtäquivalenz 1:09:26 Vorgehensweise 1:15:59 Zusammenfassung

01 | 0:00:00 Start 0:00:11 Endliche Automaten und Reguläre Sprachen 0:14:38 Nichtdeterministische endliche Automaten 0:21:06 Beispiel für NEA's 0:27:09 Äquivalenz von NEA's und DEA's 0:28:57 Beispiel Potenzmengenkonstruktion 1:11:43 Zusammenfassung

02 | 0:00:00 Start 0:00:07 Letzte Vorlesung 0:04:01 Entfernen von e-Übergängen 0:15:37 EA - Regularität 0:15:51 Beweis 0:33:04 Beispiel 0:39:16 Satz von Kleene 0:40:27 Frage: Was können endliche Automaten nicht? 0:45:19 Pumping-Lemma für reguläre Sprachen 0:58:23 Verwendung des Pumping-Lemmas 1:05:20 Beispiel zum PL 1:18:10 Zusammenfassung