Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18 episodes:

• February 09, 201819: 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

  ...more

  ---

• February 05, 201818: 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

  ...more

  ---

• January 25, 201817: 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

  ...more

  ---

• January 18, 201816: 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

  ...more

  ---

• January 18, 201815: 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

  ...more

  ---

• January 11, 201814: 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

  ...more

  ---

• December 22, 201712: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 14.12.2017

  12 |

  0:00:00 Starten

  0:02:26 Approximation mit relativer Gütegarantie

  0:03:38 Beispiel: Greedy-Algorithmus für KNAPSACK

  0:04:51 Definition

  0:06:07 Approximierbarkeit von COLOR

  0:20:05 Approximierbarkeit von TSP

  0:35:12 Approximationsschemata

  0:45:02 Ein FPAS für KNAPSACK

  1:04:10 Ein allgemeineres Resultat

  ...more

  ---

• December 22, 201713: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 19.12.2017

  13 |

  0:00:00 Starten

  0:01:15 Grammatiken

  0:06:22 Bemerkungen

  0:09:12 Die Chomsky Hierarchie

  0:19:54 Chomsky-0 Grammatiken und Semientscheidbarkeit

  0:22:25 Beweis- Beschreibung der Grammatik G

  0:28:36 Chomsky-3-Grammatiken und reguläre Sprachen

  0:37:52 Chomsky-1-Grammatiken bzw. kontextsensitive Sprachen

  0:41:58 Wiederholung: Das Problem CLIQUE

  0:49:01 Typ-2/ Kontextfreie Grammatiken

  ...more

  ---

• December 19, 201711: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 12.12.2017

  11 |

  0:00:00 Starten

  0:00:57 Nichtdeterministische Turingmaschine(n)

  0:06:41 Die Klassen NP und ANP

  0:11:10 A-NTMs sind nicht mächtiger als NTMs

  0:23:31 Polynomiale Transformation

  0:25:23 Polynomielle Transformation

  0:29:26 Komplexitätsklassen und Werkzeugkasten

  0:38:14 2SAT ∈ P

  0:54:26 NP-Vollständigkeit

  0:57:35 MAX2SAT

  1:11:27 Tipps für Reduktion auf Max2Color

  ...more

  ---

• December 07, 201710: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017

  10 |

  0:00:00 Starten

  0:03:27 Das Problem SUBSET SUM

  0:04:50 NP-Vollständigkeit von SUBSET SUM

  0:18:59 Das Problem Partition

  0:25:38 Das Problem KNAPSACK

  0:28:21 Beweis: NP-Vollständigkeit von KNAPSACK

  0:32:43 Auswirkung auf die Frage P=NP

  0:37:29 Zusammenfassung

  0:41:47 Die Klassen NPI, co-P und co-NP

  0:45:07 Vermutete Situation

  0:50:03 Das TSP-Komplement-Problem

  0:52:03 Lemma

  1:02:23 Suchprobleme

  1:05:08 Beispiel: TSP-Suchproblem

  1:06:53 Beispiel: Hamilton-Kreis Suchproblem

  1:08:09 Aufzählungsprobleme

  1:09:11 Reduzierbarkeit für Suchprobleme

  1:12:28 Orakel-Turing-Maschine

  1:13:56 Orakel-TM: Verhalten im Fragezustand

  1:16:35 Turing-Reduktion

  1:19:07 NP-schwer

  1:22:30 Beweisskizze

  ...more

  ---