KIT | KIT-Bibliothek | Impressum | Datenschutz

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

Hofheinz. Dennis

  • 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
Open Access Logo


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
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft
KITopen Landing Page