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
KIT Campus – Studieren und mehr | 2013 by Karlsruher Institut für Technologie (KIT)

KIT Campus – Studieren und mehr | 2013

0 Listeners

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

CAD tutorial in Mechanical Design, WT13/14 by Karlsruhe Institute of Technology (KIT)

CAD tutorial in Mechanical Design, WT13/14

0 Listeners

KIT Campus – Studieren und mehr | 2014 by Karlsruher Institut für Technologie (KIT)

KIT Campus – Studieren und mehr | 2014

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

Edeltalk - mit Dominik & Kevin by Papaplatte & Reeze

Edeltalk - mit Dominik & Kevin

20 Listeners

Kulturwissenschaft gestern und morgen by Karlsruher Institut für Technologie (KIT)

Kulturwissenschaft gestern und morgen

0 Listeners