Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21
- 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
| Zugehörige Institution(en) am KIT | Institut für Theoretische Informatik (ITI) |
| Publikationstyp | Audio & Video |
| Publikationsdatum | 08.12.2015 |
| Erstellungsdatum | 29.06.2015 |
| Sprache | Deutsch |
| DOI | 10.5445/DIVA/2015-935 |
| Identifikator | KITopen-ID: 1000113572 |
| Lizenz | KITopen-Lizenz |
| Serie | Algorithmen 1, Vorlesung und Übung, SS 2015 |
| Folge | 21 |