Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21
1 hour 9 minutes Posted Dec 8, 2015 at 9:03 am.
Der Jarnik-Prim-Algorithmus
Analyse
Kruskals Algorithmus (1956)
Kruskals Algorithmus – Korrektheit
Union-Find Datenstruktur
Union-Find Datenstruktur – Erste Vision
Pfadkompression
Union by Rank
Analyse – nur Union by rank
Analyse – nur Pfadkompression
Analyse – Pfadkompression + Union by rank
Ackermannfunktion – Beispiele
Kruskal mit Union-Find
Union-Find Datenstruktur
Beispiel
Vergleich Jarnik-Prim – Kruskal
Analyse
Mehr MST-Algorithmen
Messungen, Zufallsgraph
Zusammenfassung
Kap. 12: Generische Optimierungsansätze
Durchgehendes Beispiel: Rucksackproblem
Allgemein: Maximierungsproblem (L, f)
Black-Box-Löser
Lineare Programmierung
Ein einfaches Beispiel
Beispiel: Kürzeste Wege
Eine Anwendung – Tierfutter
Verfeinerungen
Algorithmen und Implementierungen
Ganzzahlige Lineare Programmierung
Beispiel: Rucksackproblem
Umgang mit (M)ILPs
Nie zurückschauen – Greedy-Algorithmen
Optimale Greedy-Algorithmen
Beispiel: Rucksackproblem
0:00
1:09:58
Show notes
21: Vorlesung |
Watch Video
