21: Algorithmen I, Vorlesung, SS 2019, 17.07.2019 Algorithmen 1, SS2019, Vorlesung

21 |
0:00:00 Start
0:00:10 Rückblick
0:01:58 Heutige Vorlesung
0:03:31 Minimale Spannbäume
0:08:34 MST-Kanten auswählen und verwerfen
0:22:22 Jarnik-Prim-Algorithmus
0:37:10 Analyse - Jarnik-Prim-Algorithmus
0:38:04 Kruskals-Algorithmus
0:45:14 Kruskals Algorithmus - Korrektheit
0:49:51 Union-Find Datenstruktur
1:03:25 Pfadkompression
1:08:34 Union by Rank
1:10:11 Analyse - nur Union by Rank
1:11:33 Analyse - nur Pfadkompression
1:12:05 Analyse - Pfadkompression und Union by Rank
1:15:21 Ackermannfunktion - Beispiele
1:15:44 Kruskal mit Union-Find
1:21:09 Vergleich Jarnik-Prim vs. Kruskal
1:23:00 Mehr MST-Algorithmen
1:25:11 Zusammenfassung