Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21 - a podcast by Karlsruher Institut für Technologie (KIT)

21: Vorlesung |
00:00:07 Der Jarnik-Prim-Algorithmus
00:04:27 Analyse
00:05:08 Kruskals Algorithmus (1956)
00:06:27 Kruskals Algorithmus – Korrektheit
00:07:14 Union-Find Datenstruktur
00:08:30 Union-Find Datenstruktur – Erste Vision
00:09:58 Pfadkompression
00:10:26 Union by Rank
00:10:58 Analyse – nur Union by rank
00:11:35 Analyse – nur Pfadkompression
00:12:04 Analyse – Pfadkompression + Union by rank
00:15:22 Ackermannfunktion – Beispiele
00:18:31 Kruskal mit Union-Find
00:21:15 Union-Find Datenstruktur
00:22:56 Beispiel
00:27:45 Vergleich Jarnik-Prim – Kruskal
00:28:55 Analyse
00:29:42 Mehr MST-Algorithmen
00:33:54 Messungen, Zufallsgraph
00:36:06 Zusammenfassung

00:38:21 Kap. 12: Generische Optimierungsansätze
00:39:27 Durchgehendes Beispiel: Rucksackproblem
00:42:08 Allgemein: Maximierungsproblem (L, f)
00:43:24 Black-Box-Löser
00:44:36 Lineare Programmierung
00:47:38 Ein einfaches Beispiel
00:50:16 Beispiel: Kürzeste Wege
00:53:59 Eine Anwendung – Tierfutter
00:56:08 Verfeinerungen
00:57:49 Algorithmen und Implementierungen
00:59:30 Ganzzahlige Lineare Programmierung
01:01:04 Beispiel: Rucksackproblem
01:02:04 Umgang mit (M)ILPs
01:03:45 Nie zurückschauen – Greedy-Algorithmen
01:04:38 Optimale Greedy-Algorithmen
01:05:16 Beispiel: Rucksackproblem

Further episodes of Algorithmen 1, SS2015, Vorlesung

Further podcasts by Karlsruher Institut für Technologie (KIT)

Website of Karlsruher Institut für Technologie (KIT)