Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

Karlsruher Institut für Technologie (KIT)
  • 0,0 (0)
  • COURS
Podcast Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

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

  1. 06/02/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

  2. 30/01/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 h 13 min

  3. 24/01/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 h 31 min

  4. 14/01/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 h 27 min

  5. 10/01/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 h 11 min

  6. 17/12/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 h 15 min

  7. 12/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 h 27 min

  8. 06/12/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 h 19 min
Tout afficher (18)

À propos

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

Informations

Plus de contenus par Karlsruher Institut für Technologie

Vous aimeriez peut‑être aussi

Pour écouter des épisodes au contenu explicite, connectez‑vous.

Recevez les dernières actualités sur cette émission

Connectez‑vous ou inscrivez‑vous pour suivre des émissions, enregistrer des épisodes et recevoir les dernières actualités.
Choisissez un pays ou une région

Afrique, Moyen‑Orient et Inde

Asie‑Pacifique

Europe

Amérique latine et Caraïbes

États‑Unis et Canada