Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08 - a podcast by Karlsruher Institut für Technologie (KIT)

08 |
0:00:00 Starten
0:00:37 Wiederholung: NP-Vollständigkeit
0:06:10 Wiederholung: Transitivität der poly. Transformation
0:06:40 Wiederholung: Korollar
0:07:37 Wiederholung: Das Problem SAT (satisfiability)
0:12:17 Das Problem 3-SAT
0:13:13 Beweis: NP-Vollständigkeit von 3-SAT
0:30:07 Das Problem 2SAT
0:34:40 Das Problem MAX2SAT
0:38:02 Das Problem CLIQUE
0:39:32 Beweis: NP-Vollständigkeit von CLIQUE
0:51:19 Das Problem COLOR
0:54:56 Beweis: NP-Vollständigkeit von 3COLOR
0:57:29 Konstruktion von 3COLOR-Instanz G
1:01:05 Beispielgraph zur Reduktion
1:04:20 Polynomialität der Reduktion
1:04:56 Instanz I erfüllbar => Instanz G erfüllbar
1:07:12 Instanz I erfüllbar <= Instanz G erfüllbar
1:08:02 Das Problem EXACT COVER
1:13:06 Beweis: NP-Vollständigkeit von EXACT COVER
1:14:28 Konstruktion von (X,S)
1:24:05 G dreifärbbar => (X,S) hat exakte Überdeckung
1:25:47 G dreifärbbar <= (X,S) hat exakte Überdeckung

Further episodes of Theoretische Grundlagen der Informatik, Vorlesung, WS16/17

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

Website of Karlsruher Institut für Technologie (KIT)