08: Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19, 27.11.2018
- 0:00:00 Start
- 0:00:22 Letzte Vorlesung
- 0:06:59 Plan für heute
- 0:09:46 Pas Problem 3SAT
- 0:11:29 Beweis: NP-Vollständigkeit von 3SAT
- 0:30:58 Das Problem 2SAT
- 0:31:54 Das Problem MAX2SAT
- 0:33:51 Das Problem CLIQUE
- 0:35:32 Beweis: NP - Vollständigkeit von CLIQUE
- 0:48:25 Das Problem COLOR
- 0:50:25 NP-Vollständigkeit von 3COLOR
- 0:52:26 Konstruktion von 3COLOR-Instanz G
- 0:55:48 Polynomialität der Reduktion
- 0:56:35 Instanz/ erfüllbar
- 1:03:01 Zwischenstand Polynomiale Reduktion
- 1:13:41 Das Problem EXACT COVER
- 1:16:23 NP - Vollständigkeit von EXACT COVER
- 1:18:00 Konstruktion
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 29.11.2018 |
| Erstellungsdatum | 27.11.2018 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2018-901 |
| Identifikator | KITopen-ID: 1000116084 |
| Lizenz | KITopen-Lizenz |
| Serie | Theoretische Grundlagen der Informatik, Vorlesung, WS 2018/19 |
| Folge | 8 |