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

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 04.02.2020

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

17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.01.2020

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

16: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 23.01.2020

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

15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 14.01.2020

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

14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 09.01.2020

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

13: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 17.12.2019

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

12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 10.12.2019

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

11: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 05.12.2019

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

10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.11.2019

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

09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.11.2019

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

08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 19.11.2019

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

07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 12.11.2019

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

06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 07.11.2019

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

05: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 31.10.2019

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

hubhopper

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

hubhopper