Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

Karlsruher Institut für Technologie (KIT)
  • 0.0 (0)
  • COURSES
Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

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. 02/16/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 07.02.2017, 18

    18 | 0:00:00 Starten 0:00:07 Fortsetzung Informationstheorie 0:01:06 Wiederholung Quellkodierung 0:01:46 Kanalkodierung 0:02:24 Codierung zum Schutz gegen Übertragungsfehler 0:04:17 Paritätscodes - Einfach Binär 0:07:27 Kreuzsicherung 0:12:20 Paritätscodes 0:13:33 Beweis 0:15:09 Paritätscodes gegen Vertauschungsfehler 0:18:42 Bsp: ISBN-10 0:18:56 ISBN 0:19:59 Block-Codes 0:20:31 Hamming-Distanz und Fehlerkorrektur 0:21:58 Maximum-Likelihood-Decoding 0:23:08 Shannon's Theorem 0:23:52 Block-Codes 0:25:13 Beweisskizze 0:26:37 Werbung 0:28:18 Vorlesung Planare Graphen 0:36:07 Proseminar Theoretical Computer Science Classics 0:39:53 ICPC Praktikum 0:42:04 PSE Energieinformatik

    47 min

  2. 02/09/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 02.02.2017, 17

    17 | 0:00:00 Starten 0:01:45 Thema dieses Kapitels 0:04:52 Material für Informationstheorie 0:05:32 Information 0:12:45 Wiederholung: Rechenregeln Logarithmus 0:13:53 Definition Information 0:14:52 Entropie 0:19:16 Bemerkung zur Entropie 0:19:31 Entropie einer Münze mit Wkt p für Zahl 0:20:44 (Platzsparende) Codierungen 0:22:12 Codierungsbäume 0:26:49 Präfix-Codes 0:29:08 Beispiel: Morse-Alphabet 0:30:15 Quellencodierungstheorem 0:31:47 Beispiel: Shannon-Fano Codierung 0:38:01 Codierungsbaum Shannon-Fano 0:38:59 Beispel: Huffman-Codierung 0:44:36 Optimalität der Huffman-Codierung 0:45:13 Vorbereitendes Lemma 0:47:00 VorbereitendesLemma: Beweis 0:51:10 Beweis - Induktionsschluss 0:57:00 Nachteile der Huffman-Codierung 0:59:05 Lauflängenkodierung

    1h 7m

  3. 02/03/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 26.01.2017, 16

    16 | 0:00:00 Starten 0:00:37 Kellerautomaten 0:03:49 Satz 0:05:15 Satz (2) 0:06:09 Beweis 0:30:19 Korollar 0:30:41 Übersicht Chomsky-2 0:32:46 Exkurs 0:34:16 Zwischenfazit zu kontextfreien Grammatiken 0:36:10 Satz (3) 0:38:18 Das Post'sche Korrespondenzproblem 0:39:47 Beweis (2) 0:43:33 Beweisskizze 0:44:07 Beweis (3) 0:45:50 Sprache der korrekten Rechenwege 0:51:59 Lemma 0:52:28 Beweis (4) 1:01:26 Bemerkung 1:02:03 Lemma (2) 1:02:27 Beweis (5)

    1h 11m

  4. 01/30/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 24.01.2017, 15

    15 | 0:00:00 Starten 0:00:07 Beweis 0:03:26 Kellerautomaten 0:09:17 Kellerautomaten - Visualisierung 0:10:09 Kellerautomaten - Arbeitsweise 0:18:33 Kellerautomaten - Beispiel 0:27:20 Kellerautomaten - Beispiel 2 0:31:02 Satz (1) 0:35:44 Satz (2) 0:39:19 Satz (3)

    47 min

  5. 01/20/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 12.01.2017, 14

    14 | 0:00:00 Starten 0:00:07 Wiederholung 0:12:03 Ogden´s Lemma für kontextfreie Sprachen 0:14:31 Beweis 0:29:20 Beweis - Teil 1 0:30:23 Beweis - Teil 2 0:39:23 Beweis - Teil 3 0:41:58 Nutzlose Variablen 0:43:38 Schritt 1 0:47:24 Beispiel: Schritt 1 0:51:28 Schritt 2 0:53:16 Beispiel: Schritt 2 0:56:45 Korollar 0:59:27 Beispielgraph

    1h 6m

  6. 01/20/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 10.01.2017, 13

    13 | 0:00:00 Starten 0:00:31 Wiederholung 0:02:13 Die Chmosky Hierarchie 0:08:16 Syntaxbäume 0:10:28 Syntaxbäume - Beispiel 0:15:54 Links/Rechtsabteilung, Eindeutigkeit 0:17:31 Beispiel 0:19:37 Chomsky-Normalform 0:20:56 Die Chomsky Hierarchie 0:21:21 Chomsky-Normalform 0:31:01 Schritt 1 0:34:21 Schritt 2 0:38:20 Schritt 3 0:49:34 Schritt 4 0:53:36 Abhängigkeitsgraph 0:54:42 Schritt 4 – Phase 1 0:56:47 Schritt 4 – Phase 2 1:02:02 Der CYK-Algorithmus 1:05:15 Beweis - Beschreibung des CYK-Algorithmus 1:08:33 CYK-Algorithmus – Beispiel 1:12:31 CYK-Algorithmus – Vorgehen 1:14:50 Beweis - Beschreibung des CYK-Algorithmus 1:15:39 CYK-Algorithmus – Vorgehen 1:16:10 CYK-Algorithmus – Beispiel 1:22:11 CYK-Algorithmus – Vorgehen 1:22:48 Ergebnisse zum Wortproblem

    1h 24m

  7. 01/12/2017

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 22.12.2016, 12

    12 | 0:00:00 Starten 0:00:28 Grammatiken 0:01:26 Beispiele 0:05:33 Grammatiken 0:07:12 Bemerkungen 0:08:32 Beispiel 0:09:22 Die Chomsky Hierarchie 0:20:09 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:24:58 Beweis - Beschreibung der Grammatik G 0:28:28 Beweis - Zusammenfassung 0:29:42 Chomsky-0 Grammatiken und Semientscheidbarkeit 0:32:04 Zwischenfazit 0:34:01 Chomsky-3-Grammatiken und reguläre Sprachen 0:35:27 Beweis 0:42:00 Bemerkung 0:43:05 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen 0:48:01 Satz 0:48:59 Bemerkung 0:49:17 Wiederholung: Das Problem CLIQUE 0:50:02 Satz 0:54:02 Bemerkung 1 0:54:53 Bemerkung 2 0:56:12 Notation 0:57:15 Typ-2 / Kontextfreie Grammatiken 0:57:40 Typ-2 Grammatiken: Beispiel 1 0:58:51 Typ-2 Grammatiken: Beispiel 2 1:00:44 Typ-2 Grammatiken: Beispiel 3

    1h 4m

  8. 12/23/2016

    Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 15.12.2016, 11

    11 | 0:00:00 Starten 0:02:50 Approximation mit relativer Gütegarantie 0:03:31 Definition 0:04:49 Approximierbarkeit von COLOR 0:18:45 Approximierbarkeit von TSP 0:28:12 Approximationsschemata 0:38:45 Ein FPAS für KNAPSACK (1) 0:40:02 Ein pseudopolynomialer, optimaler Algorithmus für KNAPSACK 0:43:49 Ein FPAS für KNAPSACK (2) 0:58:51 Ein allgemeineres Resultat

    1 hr
See All (18)

About

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

Information

More From Karlsruher Institut für Technologie

  • Einführung in die Geophysik 1, WS17/18, Vorlesung
    Courses
    Courses

    Updated 02/05/2018

  • IEEE International Conference on Robotics and Automation, 2013
    Courses
    Courses

    Updated 01/31/2014

  • Transport Phenomena in the Biosphere
    Courses
    Courses

    Updated 02/05/2018

  • The Karlsruhe Institute of Technology (KIT)
    Courses
    Courses

    Updated 12/03/2013

  • KIT Campus – Studieren und mehr | 2014
    Courses
    Courses

    Updated 09/19/2014

  • CAD tutorial in Mechanical Design, WT13/14
    Courses
    Courses

    Updated 11/28/2013

  • Kulturwissenschaft gestern und morgen
    Courses
    Courses

    Updated 04/20/2021

To listen to explicit episodes, sign in.

Stay up to date with this show

Sign in or sign up to follow shows, save episodes, and get the latest updates.
Select a country or region

Africa, Middle East, and India

Asia Pacific

Europe

Latin America and the Caribbean

The United States and Canada