Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

Karlsruher Institut für Technologie (KIT)
  • 0.0 (0)
  • CURSOS
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 · VIDEO

    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 · VIDEO

    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 y 13 min

  3. 24/01/2020 · VIDEO

    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 y 31 min

  4. 14/01/2020 · VIDEO

    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 y 27 min

  5. 10/01/2020 · VIDEO

    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 y 11 min

  6. 17/12/2019 · VIDEO

    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 y 15 min

  7. 12/12/2019 · VIDEO

    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 y 27 min

  8. 06/12/2019 · VIDEO

    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 y 19 min
Ver todo (18)

Acerca de

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

Información

Más de Karlsruher Institut für Technologie

También te podría interesar

Para escuchar episodios explícitos, inicia sesión.

Mantente al día con este programa

Inicia sesión o regístrate para seguir programas, guardar episodios y enterarte de las últimas novedades.
Elige un país o región

Africa, Oriente Medio e India

Asia-Pacífico

Europa

Latinoamérica y el Caribe

Estados Unidos y Canadá