Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

By Karlsruher Institut für Technologie (KIT)Education

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20 episodes

February 06, 2020 18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 04.02.2020
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
28 min
January 30, 2020 17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.01.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
1 hr 14 min
January 24, 2020 16: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 23.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
1 hr 31 min
January 14, 2020 15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 14.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
1 hr 28 min
January 10, 2020 14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 09.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
1 hr 12 min
December 17, 2019 13: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 17.12.2019
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
1 hr 15 min
December 12, 2019 12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 10.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
1 hr 28 min
December 06, 2019 11: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 05.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
1 hr 19 min
November 28, 2019 10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.11.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
1 hr 23 min
November 26, 2019 09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.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
1 hr 27 min