KIT-Bibliothek
Audio-/Videodatei publizieren
Anleitung zum Publizieren

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

Auflösung 1280 x 720 Pixel
Seitenverhältnis 16:9
Audiobitrate 84934 bps
Audio Kanäle 2
Audio Codec aac
Audio Abtastrate 48000 Hz
Gesamtbitrate 890720 kbps
Farbraum yuv420p
Container mov,mp4,m4a,3gp,3g2,mj2
Medientyp video/mp4
Dauer 5254 s
Dateiname DIVA-2016-794_hd.mp4
Dateigröße 4.096 byte
Bildwiederholfrequenz 25
Videobitrate 799692 kbps
Video Codec h264

Embed-Code

Theoretische Grundlagen der Informatik, Vorlesung, WS 2016/17 Folgen 1-18 von 18