KIT-Bibliothek
Audio-/Videodatei publizieren

10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18, 05.12.2017

Autor

Dorothea Wagner

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

10 |
0:00:00 Starten
0:03:27 Das Problem SUBSET SUM
0:04:50 NP-Vollständigkeit von SUBSET SUM
0:18:59 Das Problem Partition
0:25:38 Das Problem KNAPSACK
0:28:21 Beweis: NP-Vollständigkeit von KNAPSACK
0:32:43 Auswirkung auf die Frage P=NP
0:37:29 Zusammenfassung
0:41:47 Die Klassen NPI, co-P und co-NP
0:45:07 Vermutete Situation
0:50:03 Das TSP-Komplement-Problem
0:52:03 Lemma
1:02:23 Suchprobleme
1:05:08 Beispiel: TSP-Suchproblem
1:06:53 Beispiel: Hamilton-Kreis Suchproblem
1:08:09 Aufzählungsprobleme
1:09:11 Reduzierbarkeit für Suchprobleme
1:12:28 Orakel-Turing-Maschine
1:13:56 Orakel-TM: Verhalten im Fragezustand
1:16:35 Turing-Reduktion
1:19:07 NP-schwer
1:22:30 Beweisskizze

Laufzeit (hh:mm:ss)

01:26:14

Serie

Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18

Publiziert am

07.12.2017

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz

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

Embed-Code

Theoretische Grundlagen der Informatik, Vorlesung, WS 2017/18 Folgen 1-19 von 19