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/
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. Transformation 0:06:59 Beobachtung 0:10:58 Das Problem SAT (satisfiability) 0:16:04 Weitere Beispiele für SAT-Instanzen 0:17:42 Der Satz von Cook (Steven Cook, 1971) 0:22:03 Beweis: das Setup 0:28:37 Beweis: Konstruktion der Variablen 0:32:52 Beweis: Zielsetzung 0:37:44 Beweis: Konstruktion der Klauseln 0:38:03 Klauselgruppe 1: 0:39:46 Klauselgruppe 2: 0:40:36 Klauselgruppe 3: 0:41:32 Klauselgruppe 4: 0:44:44 Klauselgruppe 5: 0:45:27 Klauselgruppe 6: 0:47:04 Klauselgruppe 6,1: 0:48:59 Klauselgruppe 6,2: 0:52:30 Zwischenbilanz 0:58:13 Polynomialität der Transformation 0:58:34 Polynomialität - Klauselgruppe 1: 0:59:31 Polynomialität - Klauselgruppe 2: 1:00:12 Polynomialität - Klauselgruppe 3: 1:00:45 Polynomialität - Klauselgruppe 4: 1:01:31 Polynomialität - Klauselgruppe 5: 1:01:44 Polynomialität - Klauselgruppe 6,1: 1:02:15 Polynomialität - Klauselgruppe 6,2: 1:04:09 Heute im Rückblick: Der Satz von Cook