Theoretische Grundlagen der Informatik, Vorlesung, WS18/19

Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Dozentin: Prof. Dr. Dorothea Wagner |  Karlsruher Institut für Karlsruher Technologie (KIT), Institut für Theoretische Informatik Vorlesungsaufzeichnung: http://webcast.kit.edu

http://www.kit.edu/

Eine durchschnittliche Folge dieses Podcasts dauert 1h22m. Bisher sind 18 Folge(n) erschienen. Dies ist ein wöchentlich erscheinender Podcast.

Gesamtlänge aller Episoden: 1 day 7 minutes

subscribe
share





  • 1
  • 2
  • 1
  • 2

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


share







 2019-02-12  59m
 
 

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


share







 2019-01-31  1h25m
 
 

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


share







 2019-01-29  1h28m
 
 

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


share







 2019-01-24  1h26m
 
 

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


share







 2019-01-18  1h13m
 
 

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


share







 2019-01-10  1h12m
 
 

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


share







 2018-12-21  1h28m
 
 

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


share







 2018-12-14  1h17m
 
 

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


share







 2018-12-13  1h12m
 
 

09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 04.12.2018


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


share







 2018-12-06  1h22m
 
 
  • 1
  • 2
  • 1
  • 2