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 (KIT)

    • Bildung
    • 5,0 • 1 Bewertung

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.

Kundenrezensionen

5,0 von 5
1 Bewertung

1 Bewertung

Top‑Podcasts in Bildung

Deutschlandfunk Nova
Greator – GEDANKENtanken
Ron Perduss / Audio Alliance
Quarks
Maxim Mankevich
Cari, Manuel und das Team von Easy German

Das gefällt dir vielleicht auch

Mehr von Karlsruher Institut für Technologie

Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)
Karlsruher Institut für Technologie (KIT)