Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21

Autor

Hofheinz. Dennis

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

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

Laufzeit (hh:mm:ss)

01:09:58

Serie

Algorithmen 1, Vorlesung und Übung, SS 2015

Publiziert am

08.12.2015

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz