Theoretische Grundlagen der Informatik, Vorlesung, WS18/19
Karlsruher Institut für Technologie (KIT)
18 episodes
5 months ago
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
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS18/19 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
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
07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 22.11.2018
Theoretische Grundlagen der Informatik, Vorlesung, WS18/19
1 hour 8 minutes 33 seconds
6 years ago
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
Theoretische Grundlagen der Informatik, Vorlesung, WS18/19
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
