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
http://www.kit.edu/
Gesamtlänge aller Episoden: 1 day 7 minutes
08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 27.11.2018
08 | 0:00:00 Start 0:00:22 Letzte Vorlesung 0:06:59 Plan für heute 0:09:46 Pas Problem 3SAT 0:11:29 Beweis: NP-Vollständigkeit von 3SAT 0:30:58 Das Problem 2SAT 0:31:54 Das Problem MAX2SAT 0:33:51 Das Problem CLIQUE 0:35:32 Beweis: NP - Vollständigkeit von CLIQUE 0:48:25 Das Problem COLOR 0:50:25 NP-Vollständigkeit von 3COLOR 0:52:26 Konstruktion von 3COLOR-Instanz G 0:55:48 Polynomialität der Reduktion 0:56:35 Instanz/ erfüllbar 1:03:01 Zwischenstand Polynomiale Reduktion 1:13:41...
07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 22.11.2018
07 | 0:00:00 Start 0:00:03 NP-Vollständigkeit für Sprachen 0:03:38 NP-Vollständigkeit für Entscheidungsprobleme 0:05:28 Transitivität der poly...
06: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 15.11.2018
06 | 0:00:00 Start 0:00:09 Letzte Vorlesung 0:03:24 Die Universelle Sprache 0:14:02 Satz von Rice – Motivation 0:17:55 Bemerkungen zum Satz von Rice 0:22:13 Das Post'sche Korrespondenzproblem 0:31:13 Eigenschaften von (semi-)entscheidbaren Sprachen 0:32:25 Komplexitätstheorie 0:34:36 Wie sieht ein Problem aus? 0:37:46 Definition: Problem 0:40:37 Definition:Kodierungsschema 0:46:51 Äquivalenz von Kodierungsschemata 0:48:35 Entscheidungsprobleme 0:50:57 Korrespondenz von Entscheidungsproblemen...
05: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 13.11.2018
05 | 0:00:00 Start 0:00:10 Letzte Vorlesung 0:09:00 Beispiel - Turing Maschine 0:13:57 Bemerkungen zur TM 0:15:23 Definition zur TM 0:18:43 Notation: Konfiguration 0:19:54 Beispiel: Konfiguration 0:26:21 Definition: berechenbar / totalrekursiv 0:28:10 Beispiel 0:34:10 Entscheidbarkeit und Berechenbarkeit 0:39:01 Korollar 0:40:51 Die Church'sche These 0:44:25 Erweiterung der Turing-Maschine 0:51:23 Die Universelle Turing-Maschine 0:54:51 Die Gödelnummer 0:57:52 Die Gödelnummer -...
04: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 06.11.2018
04 | 0:00:00 Start 0:00:03 letzte Vorlesung - alternative Sicht 0:04:48 Alternative Sicht - Beispiel 0:13:20 Heutiges Thema (Frage, Antwort) 0:20:21 Definitionen: Rechtsinvarianz und Index 0:27:56 Nerode-Relation 0:31:10 Satz von Nerode 0:50:10 Korollar 0:52:20 Minimalität des Äquivalenzklassenautomats 0:59:19 Zusammenfassung 1:07:12 Turing-Maschinen und Berechenbarkeit 1:08:42 Die Registermaschine (RAM) 1:14:26 Die Turing-Maschine (TM)
03: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 30.10.2018
03 | 0:00:00 Start 0:00:03 Rückblick 0:04:19 Verallgemeinertes PL für reguläre Sprachen 0:16:10 Beispiel (3) - Anwendung Verallgemeinertes PL 0:24:06 Minimierung von Automaten - Äquivalenzklassenautomat 0:27:47 Finden nicht überflüssiger Zustände 0:31:00 Beispiel 0:37:13 Äquivalenz 0:46:38 Der Äquivalenzklassenautomat 1:04:07 Zeugen für Nichtäquivalenz 1:09:26 Vorgehensweise 1:15:59 Zusammenfassung
01: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 18.10.2018
01 | 0:00:00 Start 0:00:11 Endliche Automaten und Reguläre Sprachen 0:14:38 Nichtdeterministische endliche Automaten 0:21:06 Beispiel für NEA's 0:27:09 Äquivalenz von NEA's und DEA's 0:28:57 Beispiel Potenzmengenkonstruktion 1:11:43 Zusammenfassung
02: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 23.10.2018
02 | 0:00:00 Start 0:00:07 Letzte Vorlesung 0:04:01 Entfernen von e-Übergängen 0:15:37 EA - Regularität 0:15:51 Beweis 0:33:04 Beispiel 0:39:16 Satz von Kleene 0:40:27 Frage: Was können endliche Automaten nicht? 0:45:19 Pumping-Lemma für reguläre Sprachen 0:58:23 Verwendung des Pumping-Lemmas 1:05:20 Beispiel zum PL 1:18:10 Zusammenfassung