Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17, 01.12.2016, 08

Autor

Dorothea Wagner

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

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

Laufzeit (hh:mm:ss)

01:27:34

Serie

Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17

Publiziert am

08.12.2016

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz