Education
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