Algorithmen I, SS 2015, gehalten am 01.07.2015, Vorlesung 22
50 minutes Posted Dec 8, 2015 at 9:04 am.
Kap. 12: Generische Optimierungsansätze
Durchgehendes Beispiel: Rucksackproblem
Allgemein: Maximierungsproblem (L,f)
Black-Box-Löser
Ein einfaches Beispiel
Beispiel: Kürzeste Wege
Eine Anwendung – Tierfutter
Verfeinerungen
Ganzzahlige Lineare Programmierung
Umgang mit (M)ILPs
Nie zurückschauen – Greedy-Algorithmen
Optimale Greedy-Algorithmen
Beispiel: Rucksackproblem
Dynamische Programmierung – Aufbau aus Bausteinen
Beispiel: Rucksackproblem
Dynamische Programmierung
Beweis des Lemmas
Berechnung von P(i,C) elementweise
Rekonstruktion der Lösung
Beispiel
Algorithmenentwurf mittels dynamischer Programmierung
Anwendung dynamischer Programmierung
Gegenbeispiel: Teilproblemeigenschaft
Gegenbeispiel: Austauschbarkeit
0:00
50:02
Show notes
22: Vorlesung |
Watch Video
