Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 12.01.2016, Vorlesung - 17
Autor
Beteiligtes Institut
Institut für Theoretische Informatik (ITI)
Genre
Beschreibung
17: Vorlesung|
0:00:00 Starten
0:00:53 Wiederholung Komplexitätstheorie
0:08:54 Polynominale Reduzierbarkeit
0:09:55 Beispiel
0:10:57 NP-harte und Np-Vollständige Probleme
0:13:22 Ein einfacher Weg zu Ruhm und Reichtum ?
0:13:50 SAT: Das Erfüllbarkeitsproblem
0:17:03 Beweis von SAT
0:17:31 Beweis das SAT-NP-hart ist.
0:19:45 Variablen für F
0:24:53 Die Architektir von F=
0:27:08 Beweis w gehört zu der Sprache L, was daraus folgt das F erfüllbar ist
0:31:44 Es kann nur einen geben
0:33:05 Randbedingung
0:37:00 Anfangsbedingung
0:38:46 Übergangsbedingung Ü1, t->t+1
0:42:01 Übergangsbedingung Ü2, t->t+1
0:42:42 Endebedingung E
0:43:56 Gesamtgröße von F
0:48:06 Weitere NP-vollständige Probleme
0:55:04 3SAT (KNF)
0:56:56 Satz: 3SAT ist NP-vollständig
0:58:29 Beweis ""3SAT ist NP-hart""
1:00:12 Negation in die Blätter drücken
1:01:23 Beispiel
1:03:04 Nichtblattknoten -> Neue Variablen
1:05:52 Beispiel
1:06:34 Erfüllbarkeitsäquivalenz von F1
1:07:57 Beispiel
1:10:15 F1 -> 3KNF
Laufzeit (hh:mm:ss)
01:13:00
Serie
Theoretische Grundlagen der Informatik, Vorlesung, WS 2015/2016
Publiziert am
14.01.2016
Fachgebiet
Lizenz
| Auflösung | 1280 x 720 Pixel |
| Seitenverhältnis | 16:9 |
| Audiobitrate | 97839 bps |
| Audio Kanäle | 2 |
| Audio Codec | aac |
| Audio Abtastrate | 48000 Hz |
| Gesamtbitrate | 903759 bps |
| Farbraum | yuv420p |
| Container | mov,mp4,m4a,3gp,3g2,mj2 |
| Medientyp | video/mp4 |
| Dauer | 4380 s |
| Dateiname | DIVA-2016-51_hd.mp4 |
| Dateigröße | 4.096 byte |
| Bildwiederholfrequenz | 25 |
| Videobitrate | 799827 bps |
| Video Codec | h264 |
Mediathek-URL
Embed-Code
