Education
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