19 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. Vorlesungsaufzeichnung: http://webcast.kit.edu

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18 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. Vorlesungsaufzeichnung: http://webcast.kit.edu

    • video
    19: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 08.02.2018

    19: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 08.02.2018

    19 |
    0:00:00 Starten
    0:01:39 Rückblick: Chomsky Typ 3
    0:04:53 Rückblick: Chomsky-3 Verfahren
    0:22:29 Rückblick: Chomsky-2
    0:35:13 Rückblick: Chomsky-0/1
    0:40:32 Entscheidbarkeit
    0:47:05 Domino
    0:53:04 2-PLAYER COOPERATIVE DOMINOES

    • 1 Std. 4 Min.
    • video
    18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 30.01.2018

    18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 30.01.2018

    18 |
    0:00:00 Starten
    0:03:53 Information
    0:12:40 Entropie
    0:18:49 (Platzsparende) Codierung
    0:20:33 Codierungsbäume
    0:25:54 Präfix-Codes
    0:28:27 Quellencodierungstheorem
    0:29:58 Beispiel: Shannon-Fano Codierung
    0:38:11 Beispiel: Huffman-Codierung
    0:46:53 Vorbereitendes Lemma
    0:56:09 Beweis - Induktionsschluss
    1:05:03 Lauflängenkodierung

    • 1 Std. 12 Min.
    • video
    17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 23.01.2018

    17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 23.01.2018

    17 |
    0:00:00 Starten
    0:00:24 Übersicht Chomsky-2
    0:03:13 WDh.: Greibach-Normalform, Kellerautomat
    0:09:07 Beweis
    0:47:57 Korollar
    0:48:46 Exkurs
    0:50:37 Zwischenfazit zu kontextfreien Grammatiken
    0:53:05 Unentscheidbare Probleme für kontextfreie Grammatiken
    0:55:26 Das Post'sche Korrespondenzproblem
    1:03:51 Eindeutigkeit von kontextfreien Grammatiken
    1:05:26 Beweisskizze
    1:09:07 Sprache der korrekten Rechenwege

    • 1 Std. 25 Min.
    • video
    16: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 16.01.2018

    16: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 16.01.2018

    16 |
    0:00:00 Starten
    0:01:12 Chomsky Hierarchie
    0:15:28 Chomsky-0-Grammatiken und DTM's
    0:28:42 Konstruktion von Grammatiken
    0:46:58 Sprache der korrekten Klammerausdrücke
    0:57:09 Chomsky-Normalform
    1:08:19 Der Cocke-Younger-Kasami Algorithmus

    • 1 Std. 23 Min.
    • video
    15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 11.01.2018

    15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 11.01.2018

    15 |
    0:00:00 Starten
    0:00:19 Kontextfreie Sprachen, Kontextfreie Grammatiken
    0:06:01 Pumping-Lemma für kontextfreie Sprachen
    0:08:05 Ogden's Lemma für kontextfreie Sprachen
    0:23:12 Satz
    0:37:41 Nutzlose Variablen
    0:54:28 Korrolar
    0:58:14 Beispielgraph

    • 1 Std. 7 Min.
    • video
    14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 09.01.2018

    14: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 09.01.2018

    14 |
    0:00:00 Starten
    0:00:22 Die Chomsky Hierarchie
    0:08:09 Typ-2/Kontextfrwiw Grammatiken
    0:08:51 Typ-2/ Grammatiken: Beispiel 1
    0:09:25 Typ-2/ Grammatiken: Beispiel 2
    0:11:56 Syntacbäume
    0:13:34 Syntaxbäume Beispiel
    0:18:27 Links/ Rechtsabteilung, Eindeutigkeit
    0:20:14 Beispiel
    0:23:08 Chomsky- Normalform
    0:30:41 Schritt 1
    0:34:39 Schritt 2
    0:38:44 Schritt 3
    0:47:14 Schritt 4
    0:52:48 Abhängigkeitsgraph
    0:54:23 Schritt 4- Phase 1
    0:56:45 Schritt 4 - Phase 2
    1:01:32 Sonderbehandlung
    1:02:24 Der CYK-Algorithmus
    1:04:53 Beweis - Beschreibung des CYK-Algorithmus
    1:09:04 CYK- Algorithmus - Beispiel
    1:10:47 Beweis - Beschreibung des CYK-Algorithmus
    1:12:54 CYK-Algorithmus - Vorgehen
    1:24:32 Ergebnisse zum Wortproble

    • 1 Std. 25 Min.

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie