07: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 22.11.2018
Autor
Herausgeber
Beteiligtes Institut
Institut für Theoretische Informatik (ITI)
Genre
Beschreibung
- 0:00:00 Start
- 0:00:03 NP-Vollständigkeit für Sprachen
- 0:03:38 NP-Vollständigkeit für Entscheidungsprobleme
- 0:05:28 Transitivität der poly. Transformation
- 0:06:59 Beobachtung
- 0:10:58 Das Problem SAT (satisfiability)
- 0:16:04 Weitere Beispiele für SAT-Instanzen
- 0:17:42 Der Satz von Cook (Steven Cook, 1971)
- 0:22:03 Beweis: das Setup
- 0:28:37 Beweis: Konstruktion der Variablen
- 0:32:52 Beweis: Zielsetzung
- 0:37:44 Beweis: Konstruktion der Klauseln
- 0:38:03 Klauselgruppe 1:
- 0:39:46 Klauselgruppe 2:
- 0:40:36 Klauselgruppe 3:
- 0:41:32 Klauselgruppe 4:
- 0:44:44 Klauselgruppe 5:
- 0:45:27 Klauselgruppe 6:
- 0:47:04 Klauselgruppe 6,1:
- 0:48:59 Klauselgruppe 6,2:
- 0:52:30 Zwischenbilanz
- 0:58:13 Polynomialität der Transformation
- 0:58:34 Polynomialität - Klauselgruppe 1:
- 0:59:31 Polynomialität - Klauselgruppe 2:
- 1:00:12 Polynomialität - Klauselgruppe 3:
- 1:00:45 Polynomialität - Klauselgruppe 4:
- 1:01:31 Polynomialität - Klauselgruppe 5:
- 1:01:44 Polynomialität - Klauselgruppe 6,1:
- 1:02:15 Polynomialität - Klauselgruppe 6,2:
- 1:04:09 Heute im Rückblick: Der Satz von Cook
Laufzeit (hh:mm:ss)
01:08:33
Serie
Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Publiziert am
23.11.2018
Fachgebiet
Lizenz
| Auflösung | 1280 x 720 Pixel |
| Seitenverhältnis | 16:9 |
| Audiobitrate | 128000 bps |
| Audio Kanäle | 2 |
| Audio Codec | aac |
| Audio Abtastrate | 48000 Hz |
| Gesamtbitrate | 934068 bps |
| Farbraum | yuv420p |
| Container | mov,mp4,m4a,3gp,3g2,mj2 |
| Medientyp | video/mp4 |
| Dauer | 4113 s |
| Dateiname | DIVA-2018-880_hd.mp4 |
| Dateigröße | 480.219.197 byte |
| Bildwiederholfrequenz | 25 |
| Videobitrate | 799967 bps |
| Video Codec | h264 |
Mediathek-URL
Embed-Code
Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19
Folgen 1-18
von 18
