Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Karlsruher Institut für Technologie (KIT)
27 episodes
8 months ago
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
All content for Theoretische Grundlagen der Informatik, Vorlesung, WS15/16 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 21.01.2016, Vorlesung und Übung - 20
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 23 minutes 5 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 21.01.2016, Vorlesung und Übung - 20
20: Vorlesung und Übung |
0:00:00 Starten
0:00:11 Directed Hamilton Cycle (DHC)
0:01:35 Beweis von »DHC ist NP-hart«
0:02:03 Reduktionen
0:02:43 DHC
0:03:34 Beweis von »DHC ist NP-hart«
0:05:07 Ein Knoten pro Variable
0:05:47 Gadget Kj mit 6 Knoten je Klausel
0:08:35 »Vorgesehene« Hamiltonkreise
0:12:12 Unmögliche Hamiltonkreise
0:14:16 Verbindungen der Gadgets
0:18:35 Beispiel
0:27:46 F erfüllbar - Instanz lösbar
0:29:28 Instanz lösbar - F erfüllbar
0:30:41 DHC - Hamilton Circle
0:34:32 Exkurs: Euler-Tour
0:36:11 Gesehene Reduktionen
0:36:53 Komplexität (verallgemeinerter) klassischer Spiele
0:43:48 10. Übung
0:44:23 Integer Linear Programming
0:44:51 ILP: 0-1-Belegung erzwingen
0:45:29 Beispiel: KNAPSACK
0:47:01 Pseudo-polynomieller Knapsack Algorithmus
0:56:04 Approximation von Knapsack
1:01:16 Domino
1:03:34 Domino: Probleme
1:04:00 2-Player Cooperative Dominoes
1:08:19 Weitere Domino-Varianten
1:09:28 Portal 2
1:12:14 3Sat - Super Mario World
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
Inhalt der Vorlesung sind die Grundlagen der Theoretischen Informatik: Berechnungsmodelle, Determinismus und Nichtdeterminismus, Fragen der Berechenbarkeit, Komplexitätstheorie, NP-Vollständigkeit, Grammatiken, formale Sprachen. Vorlesungsaufzeichnung: http://webcast.kit.edu
