18 | 0:00:00 Start 0:00:11 Kodierung zum Schutz gegen Übertragungsfehler 0:01:42 Paritätscodes - Einfach binär 0:04:45 Kreuzsicherung 0:10:05 Paritätscodes 0:16:27 Block-Codes 0:17:03 Hamming-Distanz und Fehlerkorrektur 0:21:23 Beispiel

17 | 0:00:00 Start 0:03:24 Material für Informationstheorie 0:03:57 Information 0:12:08 Wiederholung: Rechenregeln Logarithmus 0:17:45 Entropie 0:24:46 Entropie zu einer Münze 0:26:09 (Platzsparende) Kodierungen 0:28:48 Präfix-Codes 0:31:13 Kodierungsbäume 0:36:18 Beispiel: Morse-Alphabet 0:37:38 Quellenkodierungstheorem 0:39:41 Beispiel: Shannon-Fano-Kodierung 0:44:44 Kodierungsbaum Shannon-Fano 0:45:44 Beispiel: Huffman-Kodierung 0:49:25 Vorbereitendes Lemma 0:55:09 Beweis - Induktionsschluss 1:00:43 Nachteile der Huffman-Kodierung 1:02:46 Lauflängenkodierung 1:10:49 Kodierung zum Schutz gegen Übertragungsfehler

16 | 0:00:00 Start 0:00:21 Letzte Vorlesung 0:07:22 Wdh.: Greibach-Normalform, Kellerautomat 0:11:54 Kellerautomaten 0:15:10 Beispiel - Greibach-Normalform 0:18:13 Beipiel - Kellerautomat 0:21:23 Beweis: Greibach-Normalform -> NPDA 0:27:20 Beweis: NPDA -> Kontextfreie Grammatik 0:52:53 Zwischenfazit zu kontextfreien Grammatiken 0:59:24 Das Post´sche Korrespondenzproblem 1:06:53 Eindeutigkeit von kontextfreien Grammatiken 1:10:13 Sprache der Korrekten Rechenwege

15 | 0:00:00 Start 0:00:19 Letzte Vorlesung 0:01:21 Heutige Vorlesung 0:03:24 Weiere Eigenschaften kontextfreier Sprachen 0:17:59 Ein Maschinenmodell für Chomsky-2 0:23:18 Greibach-Normalform 0:26:01 Beweis 0:53:04 Kellerautomaten

14 | 0:00:00 Start 0:00:31 Übersicht 0:04:47 Das Pumping-Lemma für kontextfreie Sprachen 0:13:52 Ogden´s Lemma für kontextfreie Sprachen 0:15:48 Beweis von Ogden´s Lemma 0:28:07 Echtheit der Chomsky-Hierarchie 0:30:18 Beweis 0:44:49 Eigenschaften kontextfreier Sprachen 0:48:12 Nutzlose Variablen 0:51:27 Schritt 1 1:01:10 Schritt 2 1:05:22 Endliche kontextfreie Sprachen 1:08:51 Beispielgraph

13 | 0:00:00 Start 0:01:20 Beispiele 0:04:40 Grammatiken 0:06:42 Bemerkungen 0:11:29 Die Chomsky-Hierarchie 0:24:56 Chomsky-0-Grammatiken und Semientscheidbarkeit 0:30:11 Beweis – Beschreibung der Grammatik G 0:40:28 Chomsky-3-Grammatiken und reguläre Sprachen 0:42:26 Beweis 0:53:06 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen 0:57:03 Satz

12 | 0:00:00 Start 0:00:42 Wiederholung letzte Vorlesung 0:08:12 Definition 0:14:31 Metrisches TSP 0:16:07 Approximation von min-METRIC-TSP 0:27:08 Bemerkungen zur Approximierbarkeit 0:31:25 Approximationsschemata 0:37:51 Ein FPTAS für max-KNAPSACK 0:42:18 Pseudopolynomialer. optimaler Algorithmus für max-KNAPSACK 0:52:46 Maximierungsprobleme 1:01:47 Optimierungsprobleme 1:10:58 Approximierbarkeit von min-Vertex-Color 1:23:39 Abschluss des Kapitels zur Komplexitätstheorie

11 | 0:00:00 Start 0:01:57 Verallgemeinerte NP-Schwere 0:04:05 Das Problem INTEGER PROGRAMMING 0:07:55 INTEGER PROGRAMMING ist NP-schwer 0:16:21 Bemerkungen 0:21:18 Kapitel 0:24:34 Pseudopolynomiale Algorithmen 0:28:14 Beispiel: Problem KNAPSACK 0:37:52 Starke NP-Vollständigkeit 0:44:41 Kapitel 0:47:54 Absolute Approximationsalgorithmen 0:49:27 Das allgemeine KNAPSACK-Suchproblem 0:51:56 Negativ-Resultat 0:53:52 (Kontrapositions-)Beweis 0:59:35 Approximation mit relativer Gütegarantie 1:01:11 Genereller Ansatz 1:03:54 Beispiel: Greedy-Algorithmus für KNAPSACK 1:12:18 Grenzen für den Greedy-Algorithmus

10 | 0:00:00 Start 0:00:27 Letzte/Diese Vorlesung 0:04:04 Das Problem SUBSET SUM 0:05:37 NP-Vollständigkeit von SUBSET SUM 0:21:39 Das Problem PARTITION 0:22:29 Beweis: NP-Vollständigkeit von PARTITION 0:28:40 Das Problem KNAPSACK 0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK 0:33:39 Auswirkung auf die Frage P= NP 0:40:15 Zusammenfassung 0:45:01 Die Klassen NPC und NPI 0:46:23 Die Klassen co-P und co-NP 0:51:28 Das TSP-Komplement-Problem 0:54:27 NP-vollständig vs. co-NP 0:58:19 Das Problem Subgraphisomorphie 1:00:17 Das Problem Graphisomorphie 1:02:06 Die Polynomielle Hierarchie 1:12:34 Suchprobleme 1:13:13 Beispiel: TSP-Suchproblem 1:14:53 Beispiel: Hamilton-Kreis Suchproblem 1:16:18 NP-Schwere bei Suchproblemen 1:20:15 Beispiel: Hamilton-Kreis Aufzählungsproblem

09 | 0:00:00 Start 0:00:08 Letzte Vorlesung 0:08:16 Plan für heute 0:10:46 Das Problem 3SAT 0:12:53 Beweis: NP-Vollständigkeit von 3SAT 0:31:50 Das Problem 2SAT 0:34:00 Das Problem MAX2SAT 0:36:49 Das Problem CLIQUE 0:39:07 Beweis: NP-Voillständigkeit von CLIQUE 0:54:25 Das Problem COLOR 0:55:33 Beweis: NP-Vollständigkeit von 3COLOR 0:57:09 Konstruktion von 3COLOR-Instanz G 1:02:30 Polynomialität der Reduktion 1:03:12 Instanz G 3-färbbar 1:08:08 Zwischenstand Polynomiale Reduktion 1:10:27 Das Problem EXACT COVER 1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER 1:14:34 Konstruktion von (X, S) 1:22:00 G 3-färbbar -> exakte Überdeckung

08 | 0:00:00 Start 0:07:42 Bemerkungen zur NTM 0:11:20 Zeitkomplexität für NTM 0:14:40 Die Klasse NP 0:18:28 P vs NP 0:24:03 Polynomiale Transformation 0:34:35 Das Problem SAT 0:39:55 Satz von Cook 0:43:37 Setup 0:48:19 Konstruktion der Variablen 1:05:51 Zwischenbilanz

07 | 0:00:00 Start 0:00:29 Letzte Vorlesung 0:04:12 Halteproblem 0:10:25 Die universelle Sprache 0:16:34 Satz von Rice - Motivation 0:20:52 Bemerkungen zum Satz von Rice 0:22:30 Das Post´sche Korrespondenzproblem 0:34:51 Eigenschaften von (semi-) entscheidbaren Sprachen 0:39:07 Komplexitätstheorie 0:42:09 Wie sieht das Problem aus? 0:47:37 Definition: Problem 0:49:42 Definition: Kodierungsschema 0:55:30 Äquivalenz von kodierungsschemata 0:57:11 Entscheidungsproblem 1:02:21 Zeitkomplexität 1:07:08 Schwierigkeit von Entscheidungs- und Optimierungsproblem 1:11:35 Algorithmus OPT-TOUR (als beweis) 1/2 1:16:27 Laufzeit des Algorithmus 1:18:26 Zwischenstand Komplexitätstheorie 1:21:56 Die Nichtdeterministische turing-Maschine 1:23:25 Die Orakel-Turing-Maschine

06 | 0:00:00 Start 0:01:05 (deterministische) Turing-Maschine 0:06:34 Beispiel-Turing-Maschine 0:16:35 Definitionen zur TM 0:19:46 Notation: Konfiguration 0:29:18 Definition: berechenbar/ totalrekursiv 0:42:20 Entscheidbarkeit und Berechenbarkeit 0:48:02 Korollar 0:49:57 Die Church´sche These 0:55:21 Erweiterung der Turing-maschine 0:59:49 Die universelle Turing-Maschine 1:03:07 Die Gödelnummer 1:13:24 Die Diagonalsprache 1:18:20 Unentscheidbarkeit der Diagonalsprache 1:21:17 Paradoxien und Selbstbezüglichkeit 1:23:10 Halteproblem

05 | 0:00:00 Start 0:00:39 Kapitel 2 0:07:31 Alternative Sicht – Beispiel 0:16:52 Wiederholung Äquivalemzklassenautomat 0:19:38 Rechtsinvarianz und Index 0:26:04 Nerode-Relation 0:29:50 Satz von Nerode 0:46:15 Korollar 0:52:35 Minimalität des Äquivalenzklassenautomats 0:55:26 Zusammenfassung 1:01:27 Turing-Maschinen und Berechenbarkeit 1:03:20 Die Registermaschine (RAM) 1:11:08 Formale Definition der Turingmaschine 1:18:14 Beispiel-Turing-Maschine

04 | 0:00:00 Start 0:00:41 Satz (Pumping-Lemma für reguläre Sprachen) 0:03:23 Satz (Verallgemeinertes Pumping-Lemma) 0:13:22 Beispiel (3) - Anwendung Verallgemeinertes PL 0:21:54 Finden nicht überflüssiger Zustände 0:29:44 Der Äquivalenzklassenautomat 0:49:04 Beispiel zur Vorgehensweise 0:57:27 Zusammenfassung 1:01:50 Testen Sie sich

03 | 0:00:00 Start 0:00:00 Start 0:00:20 Nichtdeterministische endliche Automaten 0:05:09 Zwischenstand 0:10:45 Entfernen von ɛ​-Übergängen 0:21:09 EA -> Regularität 0:41:31 Beispiel 0:47:34 Satz von Kleene 0:48:58 Was können endliche Automaten nicht? 0:53:44 Pumping-Lemma für reguläre Sprachen 1:19:05 Zusammenfassung 1:20:03 Bemerkungen zu 'Testen Sie sich'-Aufgabe

02 | 0:00:00 Start 0:00:41 Kontextfreie Grammatiken 0:06:34 Kontextfreie Grammatiken - Beispiele 0:14:35 Endliche Automaten und Reguläre Sprachen 0:23:43 Nichtderterministische endliche Automaten 0:28:31 Beispiele für NEAs 0:31:52 Äquivalenz von NEAs und DEAs 0:34:54 Beispiel Potenzmengenkonstruktion 0:41:26 Erweiterung von ẟ 0:58:24 Induktionsanfang 1:13:24 Zusammenfassung

01 | 0:00:00 Start 0:03:28 Ziele der Vorlesung TGI 0:10:29 Wörter 0:20:06 Formale Sprachen 0:33:42 Reguläre Sprachen 0:38:59 Reguläre Ausdrücke 0:44:55 Reguläre Ausdrücke -Beispiele 0:53:09 Endliche Automaten