10: Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20, 28.11.2019
Wagner, Dorothea; Sauer, Jonas
; Brückner, Guido; Zentrum für Mediales Lernen (ZML) [Hrsg.]
; Brückner, Guido; Zentrum für Mediales Lernen (ZML) [Hrsg.]- 0:00:00 Start
- 0:00:27 Letzte/Diese Vorlesung
- 0:04:04 Das Problem SUBSET SUM
- 0:05:37 NP-Vollständigkeit von SUBSET SUM
- 0:21:39 Das Problem PARTITION
- 0:22:29 Beweis: NP-Vollständigkeit von PARTITION
- 0:28:40 Das Problem KNAPSACK
- 0:31:18 Beweis: NP-Vollständigkeit von KNAPSACK
- 0:33:39 Auswirkung auf die Frage P= NP
- 0:40:15 Zusammenfassung
- 0:45:01 Die Klassen NPC und NPI
- 0:46:23 Die Klassen co-P und co-NP
- 0:51:28 Das TSP-Komplement-Problem
- 0:54:27 NP-vollständig vs. co-NP
- 0:58:19 Das Problem Subgraphisomorphie
- 1:00:17 Das Problem Graphisomorphie
- 1:02:06 Die Polynomielle Hierarchie
- 1:12:34 Suchprobleme
- 1:13:13 Beispiel: TSP-Suchproblem
- 1:14:53 Beispiel: Hamilton-Kreis Suchproblem
- 1:16:18 NP-Schwere bei Suchproblemen
- 1:20:15 Beispiel: Hamilton-Kreis Aufzählungsproblem
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 28.11.2019 |
| Erstellungsdatum | 28.11.2019 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2019-929 |
| Identifikator | KITopen-ID: 1000117084 |
| Lizenz | KITopen-Lizenz |
| Nachgewiesen in | OpenAlex |
| Serie | Theoretische Grundlagen der Informatik, Vorlesung, WS 2019/20 |
| Folge | 10 |