Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

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...

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...

16 | 0:00:00 Start 0:00:32 Letzte Vorlesung 0:02:51 Wdh...

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