Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

09: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 26.11.2019

Listen Later
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
...more
View all episodesView all episodes
Download on the App Store
Theoretische Grundlagen der Informatik, Vorlesung, WS19/20By Karlsruher Institut für Technologie (KIT)

More shows like Theoretische Grundlagen der Informatik, Vorlesung, WS19/20

View all
IEEE International Conference on Robotics and Automation, 2013 by Karlsruher Institut für Technologie (KIT)

IEEE International Conference on Robotics and Automation, 2013

0 Listeners

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2014, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2014, Vorlesung

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2014 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2014

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2015 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2015

0 Listeners

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2015, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Stochastik für Studierende des gymnasialen Lehramts Mathematik, SS2015, Vorlesung

0 Listeners

Internationales Forum am ZAK by Karlsruher Institut für Technologie (KIT)

Internationales Forum am ZAK

0 Listeners

Transport Phenomena in the Biosphere by Karlsruher Institut für Technologie (KIT)

Transport Phenomena in the Biosphere

0 Listeners

Einführung in die Geophysik 1, WS17/18, Vorlesung by Karlsruher Institut für Technologie (KIT)

Einführung in die Geophysik 1, WS17/18, Vorlesung

0 Listeners

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019 by Karlsruher Institut für Technologie (KIT)

Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019

0 Listeners