Algorithmen 1, SS2019, Vorlesung

Algorithmen 1, SS2019, Vorlesung

By Karlsruher Institut für Technologie (KIT)Education
Download on the App Store

All Algorithmen 1, SS2019, Vorlesung episodes

  • 22: Algorithmen I, Vorlesung, SS 2019, 22.07.2019
    22 |
    0:00:00 Start
    0:00:23 Generische Optimierungsansätze
    0:05:36 Rucksackproblem
    0:09:28 Maximierungsprolem
    0:12:42 Black-Box-Löser
    0:17:38 Lineare Programmierung
    0:24:53 Kürzeste Wege
    0:29:29 Tierfutter
    0:35:21 Algorithmen und Implementierungen
    0:39:09 Ganzzahlige Lineare Programmierung
    0:53:05 Greedy-Algorithmen
    1:00:00 Dynamische Programmierung
    1:17:32 Algorithmenentwurf mittels dynamischer Programmierung
    1:23:01 Systematische Suche
    1 hr 25 min
  • 21: Algorithmen I, Vorlesung, SS 2019, 17.07.2019
    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
    1 hr 28 min
  • 20: Algorithmen I, Vorlesung, SS 2019, 15.07.2019
    20 |
    0:00:00 Start
    0:01:21 Kürzeste Wege: Definition
    0:02:23 Dijkstras Algorithmus. Pseudocode
    0:08:12 Dijkstra: negative Kantengewichte
    0:17:02 Monotone ganzzahlige Prioritätslisten
    0:19:49 Negative Zyklen
    0:21:55 Zurück zu Basiskonzepten
    0:26:31 Allgemeines Korrektheitskriterium
    0:31:09 Bellman-Ford-Algorithmus
    0:39:29 Beispiel
    0:43:57 Bellman-Ford: Laufzeit
    0:45:30 Azyklische Graphen
    0:49:38 Von überall nach überall
    0:52:15 Kürzeste Wege: Zusammenfassung
    0:57:10 Exkurs: Routing in Straßennetzwerken
    1:01:56 Ideen für Routenplanung
    1:03:47 Ansatz: Transit-Node Routing
    1:09:15 Zweite Beobachtung
    1:17:04 Offene Fragen
    1:18:36 Minimale Spannbäume (MST)
    1:23:59 Minimal aufspannende Wälder (MSF)
    1 hr 26 min
  • 19: Algorithmen I, Vorlesung, SS 2019, 03.07.2019
    19 |
    0:00:00 Start
    0:00:11 Rückblick: Kürzeste Wege
    0:02:00 Dijkstras Algorithmus
    0:02:54 Allgemeine Definition
    0:07:38 Kante relaxieren
    0:13:02 Dijkstras Algorithmus: Pseudocode
    0:16:44 Beispiel
    0:23:52 Korrektheit
    0:37:29 Implementierung
    0:40:10 Prioritätsliste
    0:46:50 Beispiel
    0:49:18 Dijkstra: Laufzeit
    0:58:32 Analyse im Mittel
    0:59:32 Monotone ganzzahlige Prioritätslisten
    1:01:18 Negative Kosten
    1:03:38 Zurück zu Basiskonzepten
    1:06:34 Allgemeines Korrektheitskriterium
    1:08:46 Bellman-Ford Algorithmus
    1 hr 10 min
  • 18: Algorithmen I, Vorlesung, SS 2019, 01.07.2019
    18 |
    0:00:00 Start
    0:07:02 Graph-Traversierung
    0:11:13 Breitensuche
    0:13:13 Tiefensuche
    0:21:56 DFS-Baum
    0:28:14 DFS-Nummerierung
    0:38:39 Topologische Sortierung
    0:43:27 Topologisches Sortieren mittels DFS
    0:55:01 Begriff Zusammenhang
    1:02:26 BFS vs DFS
    1:07:16 Kürzeste Wege : Definition
    1:17:22 Dijkstras Algorithmus
    1 hr 27 min
  • 17: Algorithmen I, Vorlesung, SS 2019, 26.06.2019
    17 |
    0:00:00 Start
    0:00:05 Rückblick und Überblick
    0:01:35 Graphen
    0:02:12 Repräsentation von Graphen
    0:02:33 Kantenfolgenrepräsentation
    0:03:31 Adjazenzfelder
    0:05:59 Kantenliste -> Adjazenzfeld
    0:07:29 Adjazenzlisten
    0:13:10 Customization (Zuschneiden)
    0:13:53 Beispiel: DAG-Erkennung
    0:23:23 Adjazenz-Matrix
    0:31:24 Pfade zählen mittels linearer Algebra (LA)
    0:35:54 Beispiel, wo Graphentheorie bei LA hilft
    0:38:56 Implizite Repräsentation
    0:40:53 Zusammenhangstest für Intervallgraphen
    0:43:46 Beispiel
    0:45:13 Graphpräsentation: Zusammenfassung
    0:52:00 Graph-Traversierung
    0:58:59 Breitensuche
    1:07:32 Repräsentation des Baums
    1:16:41 Repräsentation von Q und Q' mittels FIFO
    1:19:17 Tiefensuche
    1:24:26 DFS-Baum
    1 hr 28 min
  • 15: Algorithmen I, Übung, SS 2019, 19.06.2019
    15 |
    0:00:00 Start
    0:00:08 Übungsblatt 7, Pseudocode
    0:02:49 4. Übung
    0:02:52 Roadmap, Bucket Sort Spezial, Bucket Queue, Binary Radix Heap
    0:03:14 Erinnerung: Bucketsort
    0:06:46 Bucket Sort Spezial
    0:13:55 Spezielle Priority Queues
    0:14:55 Bucket Queue
    0:17:40 Binary Radix Heap
    0:22:52 Binary Radix Heap: deleteMin
    0:24:06 Binary Radix Heap
    0:25:54 Möglichkeit Ternärer Radix Heaps
    28 min
  • 14: Algorithmen I, Vorlesung, SS 2019, 17.06.2019
    14 |
    0:00:00 Start
    0:00:05 Rückblick und Überblick
    0:02:06 Sortierte Folgen
    0:07:56 Statisch: Sortiertes Feld mit binärer Suche
    0:18:14 Dynamisch sortierte Folgen
    0:26:49 Abgrenzung
    0:32:27 Sortierte Folgen - Anwendungen
    0:46:39 Binäre Baumsuche
    0:52:08 locate (k)
    1:00:15 Laufzeit von locate (k)
    1:03:05 Naives Einfügen
    1:08:07 Naives Einfügen - Beispiel
    1:11:25 Suchbäume balancieren
    1:16:25 Items
    1:20:24 Initialisierung
    1:22:27 Locate
    1 hr 27 min