Algorithmen I, SS 2015, gehalten am 01.07.2015, Vorlesung 22 Algorithmen 1, SS2015, Vorlesung

22: Vorlesung |
00:00:07 Kap. 12: Generische Optimierungsansätze
00:00:23 Durchgehendes Beispiel: Rucksackproblem
00:01:19 Allgemein: Maximierungsproblem (L,f)
00:02:03 Black-Box-Löser
00:02:05 Ein einfaches Beispiel
00:02:07 Beispiel: Kürzeste Wege
00:02:09 Eine Anwendung – Tierfutter
00:02:17 Verfeinerungen
00:02:21 Ganzzahlige Lineare Programmierung
00:02:25 Umgang mit (M)ILPs
00:03:19 Nie zurückschauen – Greedy-Algorithmen
00:03:31 Optimale Greedy-Algorithmen
00:03:35 Beispiel: Rucksackproblem
00:03:43 Dynamische Programmierung – Aufbau aus Bausteinen
00:04:50 Beispiel: Rucksackproblem
00:08:34 Dynamische Programmierung
00:09:57 Beweis des Lemmas
00:12:27 Berechnung von P(i,C) elementweise
00:20:55 Rekonstruktion der Lösung
00:25:20 Beispiel
00:34:20 Algorithmenentwurf mittels dynamischer Programmierung
00:38:49 Anwendung dynamischer Programmierung
00:44:55 Gegenbeispiel: Teilproblemeigenschaft
00:46:25 Gegenbeispiel: Austauschbarkeit