Algorithmen 1, SS2019, Vorlesung episodes:

• July 30, 201923: Algorithmen I, Übung, SS 2019, 24.07.2019

  23 |

  0:00:00 Start

  0:00:13 Übung: Überblick

  0:03:26 Dijkstras Algorithmus

  0:07:19 Bellmann Ford Algorithmus

  0:14:50 Minimale Spannbäume

  0:20:31 Steinerbäume

  0:27:20 Problem des Handlungsreisenden (TSP)

  ...more

  

  ---

• July 25, 201922: 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

  ...more

  

  ---

• July 18, 201921: 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

  ...more

  

  ---

• July 16, 201920: 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)

  ...more

  

  ---

• July 05, 201919: 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

  ...more

  

  ---

• July 04, 201918: 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

  ...more

  

  ---

• June 27, 201917: 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

  ...more

  

  ---

• June 25, 201916: Algorithmen I, Vorlesung, SS 2019, 24.06.2019

  16 |

  0:00:00 Start

  0:00:11 Wiederholung

  0:11:16 Locate

  0:19:22 Einfügen-Algorithmenskizze

  0:50:36 Zusammenfassung

  0:53:43 Graphen

  0:58:43 Graphen-Anwendung

  1:05:15 Operationen

  1:10:05 Kantenfolgenrepräsentation

  1:13:28 Adjazenzfelder

  ...more

  

  ---

• June 25, 201915: 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

  ...more

  

  ---

• June 25, 201914: 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

  ...more

  

  ---