09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.11.2019 - a podcast by Karlsruher Institut für Technologie (KIT)

09 |
0:00:00 Start
0:00:08 Letzte Vorlesung
0:08:16 Plan für heute
0:10:46 Das Problem 3SAT
0:12:53 Beweis: NP-Vollständigkeit von 3SAT
0:31:50 Das Problem 2SAT
0:34:00 Das Problem MAX2SAT
0:36:49 Das Problem CLIQUE
0:39:07 Beweis: NP-Voillständigkeit von CLIQUE
0:54:25 Das Problem COLOR
0:55:33 Beweis: NP-Vollständigkeit von 3COLOR
0:57:09 Konstruktion von 3COLOR-Instanz G
1:02:30 Polynomialität der Reduktion
1:03:12 Instanz G 3-färbbar
1:08:08 Zwischenstand Polynomiale Reduktion
1:10:27 Das Problem EXACT COVER
1:12:53 Beweis: NP-Vollständigkeit von EXACT COVER
1:14:34 Konstruktion von (X, S)
1:22:00 G 3-färbbar -> exakte Überdeckung

Further episodes of Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

Further podcasts by Karlsruher Institut für Technologie (KIT)

Website of Karlsruher Institut für Technologie (KIT)