KIT-Bibliothek
Audio-/Videodatei publizieren
Anleitung zum Publizieren

Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 14.01.2016, Vorlesung und Übung - 18

Autor

Peter Sanders, Lorenz Hübschle-Schneider, Tobias Maier

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

18: Vorlesung und Übung|
0:00:00 Starten
0:00:10 Wiederholung: Satz: 3SAT ist NP-vollständig
0:02:06 Wiederholung: Beweis ""3SAT ist NP-hart""
0:02:47 Wiederholung: Negationen in die Blätter drücken
0:03:07 Wiederholung: Nichtblattknoten --> Neue Variablen
0:03:37 Wiederholung: Erfüllbarkeitsäquivalenz
0:05:05 Exkurs: 2SAT ∈ P
0:10:27 CLIQUE
0:14:22 Beweis Clique ∈ NP
0:15:01 Beweis von ""CLIQUE ist NP-hart""
0:19:57 Beispiel
0:29:19 VERTEX COVER (Knotenüberdeckung)
0:31:14 Beweis VERTEX COVER ∈ NP
0:31:32 Beweis von ""VERTEX COVER ist NP-hart""
0:39:11 Gesehene Reduktionen
0:39:39 Beweistechniken für A ≤p B: Spezialfälle
0:43:36 Beweistechniken für A ≤p B: Uminterpretation
0:44:28 Beweistechniken für A ≤p B: Gadgets
0:46:27 Beweistechniken für A ≤p B: Randbedingungen

0:47:33 9. Übung
0:47:35 Komplexitätsklassen - Einführung
0:56:38 Komplexitätsklassen - Fortführung
1:03:57 3SAT ≤p 3COLOR - Einführung
1:05:16 3SAT ≤p 3COLOR - Fortführung
1:09:00 3SAT ≤p 3COLOR - mit Gadget
1:14:08 1-aus-3SAT
1:20:37 XOR-(3)SAT
1:23:07 Einige weitere Varianten
1:26:08 PLANAR 3SAT
1:28:05 Knapsack und Subset Sum

Laufzeit (hh:mm:ss)

01:31:10

Serie

Theoretische Grundlagen der Informatik, Vorlesung, WS 2015/2016

Publiziert am

21.01.2016

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz

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

Embed-Code

Theoretische Grundlagen der Informatik, Vorlesung, WS 2015/2016 Folgen 1-27 von 27