Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

By Karlsruher Institut für Technologie (KIT)Education

Theoretische Grundlagen der Informatik, Vorlesung, WS18/19 episodes

February 12, 2019 18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 07.02.2019
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
1 hr
January 31, 2019 17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 31.01.2019
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
1 hr 26 min
January 29, 2019 16: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 29.01.2019
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
1 hr 29 min
January 24, 2019 15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 22.01.2019
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
1 hr 27 min
January 18, 2019 14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 17.01.2019
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
1 hr 14 min
January 10, 2019 13: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 08.01.2019
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
1 hr 13 min
December 21, 2018 12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 20.12.2018
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
1 hr 29 min
December 14, 2018 11: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 13.12.2018
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
1 hr 18 min
December 13, 2018 10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 11.12.2018
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
1 hr 13 min
December 13, 2018 10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 11.12.2018
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
1 hr 13 min