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 19.01.2016, Vorlesung - 19
Theoretische Grundlagen der Informatik, Vorlesung, WS15/16
1 hour 8 minutes 38 seconds
9 years ago
Theoretische Grundlagen der Informatik, WS 2015/2016, gehalten am 19.01.2016, Vorlesung - 19
19: Vorlesung |
0:00:00 Starten
0:03:08 Beweis SUBSET SUM
0:03:31 Beweis ""SUBSET SUM ist NP-hart""
0:03:34 SUBSET SUM
0:06:04 Die SUBSET SUM Instanz
0:10:08 Beispiel
0:13:55 Beweisidee
0:18:29 F erfüllbar -> Instanz lösbar
0:20:42 Instanz lösbar -> F erfüllbar
0:23:44 Beispiel Rucksackproblem
0:24:29 Rucksackproblem
0:26:11 Reduktionen
0:26:56 PARTITION
0:28:30 Beweis SUBSET SUM <= pPARTITION
0:38:39 Integer Linear Programming (ILP)
0:40:14 Beweis von ""ILP ist NP-hart""
0:41:18 Ist ILP in NP ?
0:44:52 Umgang mit NP-harten Probleme
0:55:29 Optimierungsprobleme
0:56:11 NP vollständig
0:57:26 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)
1:00:20 alpha-Approximation von TSP
1:01:13 HamiltonCycle<=palpha-Approximation von TSP
1:05:45 Pseudopolynomielle Algorithmen
1:07:56 Beispiel Rucksackproblem
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
