18 Folgen

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

Theoretische Grundlagen der Informatik, Vorlesung, WS19/20 Karlsruher Institut für Technologie

    • Kurse

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

    • video
    18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 04.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

    • 27 Min.
    • video
    17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.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 Std. 13 Min.
    • video
    16: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 23.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 Std. 30 Min.
    • video
    15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 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 Std. 27 Min.
    • video
    14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 09.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 Std. 11 Min.
    • video
    13: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 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 Std. 14 Min.

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie