Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Karlsruher Institut für Technologie (KIT)
27 episodes
8 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. Vorlesungsaufzeichnung: http://webcast.kit.edu
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 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. Vorlesungsaufzeichnung: http://webcast.kit.edu
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 14.01.2016, Vorlesung und Übung - 18
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 31 minutes 10 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 14.01.2016, Vorlesung und Übung - 18
18: Vorlesung und Übung|
0:00:00 Starten
0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig
0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart""
0:02:47 Wiederholung: Negationen in die Blätter drücken
0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen
0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz
0:05:05 Exkurs: 2SAT ∈ P
0:10:27 CLIQUE
0:14:22 Beweis Clique ∈ NP
0:15:01 Beweis von ""CLIQUE ist NP-hart""
0:19:57 Beispiel
0:29:19 VERTEX COVER (Knotenüberdeckung)
0:31:14 Beweis VERTEX COVER ∈ NP
0:31:32 Beweis von ""VERTEX COVER ist NP-hart""
0:39:11 Gesehene Reduktionen
0:39:39 Beweistechniken für A ≤p B: Spezialfälle
0:43:36 Beweistechniken für A ≤p B: Uminterpretation
0:44:28 Beweistechniken für A ≤p B: Gadgets
0:46:27 Beweistechniken für A ≤p B: Randbedingungen
0:47:33 9. Übung
0:47:35 Komplexitätsklassen - Einführung
0:56:38 Komplexitätsklassen - Fortführung
1:03:57 3SAT ≤p 3COLOR - Einführung
1:05:16 3SAT ≤p 3COLOR - Fortführung
1:09:00 3SAT ≤p 3COLOR - mit Gadget
1:14:08 1-aus-3SAT
1:20:37 XOR-(3)SAT
1:23:07 Einige weitere Varianten
1:26:08 PLANAR 3SAT
1:28:05 Knapsack und Subset Sum
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
