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

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

19: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 08.02.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

18: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 30.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

17: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 23.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

16: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 16.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

15: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 11.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

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

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

12: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 14.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

13: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 19.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

11: Theoretische Grundlagen der Informatik, Übung, WS 2017/18, 12.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

10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017

09 | 0:00:00 Starten 0:00:39 NP-Vollständigkeit 0:02:03 Transitivität der poly. Transformation 0:02:31 Korollar 0:03:49 Das Problem 3-SAT 0:05:37 Beweis: NP-Vollständigkeit von 3-SAT 0:20:16 Das Problem 2SAT 0:22:09 Das Problem MAX2SAT 0:24:18 Das Problem CLIQUE 0:27:48 Beweis: NP-Vollständigkeit von CLIQUE 0:36:44 Das Problem COLOR 0:37:57 Beweis: NP-Vollständigkeit von 3COLOR 0:39:06 Konstruktion von 3COLOR-Instanz G 0:43:16 Beispielgraph zur Reduktion 0:45:12 Polynomialität der Reduktion 0:45:35 Instantz I erfüllbar auch Instanz G erfüllbar 0:45:57 Instanz G ist 3-färbbar 0:50:30 Das Problem EXACT COVER 0:53:51 Beweis: NP-Vollständigkeit von EXACT COVER 0:55:30 Konstruktion von (X,S) 1:04:50 G dreifärbbar (X,S) hat exakte Überdeckung

09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 28.11.2017

08 | 0:00:00 Starten 0:00:17 Gliederung 0:01:30 Turingmaschinen 0:19:04 Erweiterung von Turingmaschinen 0:19:18 Mehrere Spuren 0:23:26 Mehrere Bänder 0:25:01 Erweiterte Turingmaschinen 0:31:56 Entscheidbarkeit 0:32:09 Entscheidbarkeit - Definitionen 0:36:34 Entscheidbarkeit - Zusammenhänge 0:45:32 Entscheidbarkeit - Überblick 0:46:31 Entscheidbarkeit - Komplementbildung 0:48:09 Entscheidbarkeit - Überblick 0:51:01 Entscheidbarkeit - Beispiele 0:51:33 Diagonalsprache 0:55:42 Halteproblem 0:58:52 Iniverselle Sprache 0:59:23 Post'sches Korrespondenzproblem 1:02:59 Hilberts zehntes Problem 1:08:44 Äquivalenzproblem 1:09:35 Entscheidbarkeit - Werkzeugkasten 1:10:01 Satz von Rice 1:14:02 Zusammenfassung (Werkzeugkasten)

08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 21.11.2017

07 | 0:00:00 Starten 0:00:06 Definitionen zur TM 0:01:15 Unentscheidbarkeit der Diagonalsprache 0:02:42 Die Universelle Sprache 0:09:51 Satz von Rice - Motivation 0:17:10 Das Post'sche Korrespondenzproblem 0:21:44 Eigenschaften von (semi-)entscheibaren Sprachen 0:28:02 Komplexitätstheorie 0:32:53 Wie sieht ein Problem aus? 0:37:56 Definition: Problem 0:39:34 Definition: Kodierungsschema 0:43:19 Äquivalenz von Kodierungsschemata 0:44:33 Entscheidungsprobleme 0:46:43 Korrespondenz von Entscheidungsproblemen und Sprachen 0:51:27 Zeitkomplexität 0:53:04 Die Klasse P 0:56:35 Algorithmus OPT-TOUR (als Beweis) 0:59:27 Die Nichtdeterministische Turingmaschine 1:04:41 Übertragung auf Entscheidungsprobleme PI 1:07:16 Bemerkungen zur NTM 1:13:15 Die Klasse NP

07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 16.11.2017

06 | 0:00:00 Starten 0:01:54 Formale Definition der Tuting-Maschine 0:04:18 Definition zur TM 0:07:42 Motation: Konfiguration 0:10:03 Beispiel: Konfiguration 0:20:09 Definition: berechenbar/ totalrekursiv 0:22:30 Beispiel 0:30:39 Entscheidbarkeit und Berechenbarkeit 0:32:46 Korollar 0:34:56 Die Church'sche These 0:39:00 Erweiterungen der Turing-Maschine 0:44:35 Die universelle Turing-Maschine 0:48:15 Die Gödelnummer 0:53:04 Die Gödelnummer - Bemerkungen 0:55:28 Die Gödelnummer - Beispiel 0:58:51 Definition 0:59:21 Die Diagonalsprache 1:04:09 Die Diagonalsprache - Veranschaulichung 1:05:41 Unentscheidbarkeit der Diagonalsprache 1:07:53 Korollar 1:10:12 Paradoxien und Selbstbezüglichkeit 1:11:32 Halteproblem

06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 14.11.2017

05 | 0:00:00 Starten 0:00:21 Frage 0:04:24 Wiederholung Äquivalenzklassenautomat 0:09:44 Definitionen: Rechtsinvarianz und Index 0:17:24 Nerode- Relation 0:22:12 Satz von Nerode 0:25:40 Beweis zu Satz von Nerode: (1)-->(2) 0:31:49 Beweis zu Satz von Nerode: (2)-->(3) 0:37:57 Beweis zu Satz von Nerode: (3)-->(1) 0:46:16 Korollar 0:49:09 Minimalitäat des Äquivalenzklassenautomats 0:53:15 Zusammenfassung 0:56:04 Historisches 0:59:37 Turing-Maschinen und Berechenbarkeit 1:00:59 Die Registermaschine (RAM) 1:02:13 Befehle der Registermaschine (RAM) 1:03:12 Die Turing-Maschine (TM) 1:06:53 Formale Definition der Turing-Maschine 1:08:59 Bemerkung zur TM 1:12:15 Beispiel-Turing-Maschine 1:18:17 Definition zur TM

hubhopper

Theoretische Grundlagen der Informatik, Vorlesung, WS17/18

hubhopper