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)

Algorithmen 1, SS2019, Vorlesung

23: Algorithmen I, Übung, SS 2019, 24.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

22: Algorithmen I, Vorlesung, SS 2019, 22.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

21: Algorithmen I, Vorlesung, SS 2019, 17.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)

20: Algorithmen I, Vorlesung, SS 2019, 15.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

19: Algorithmen I, Vorlesung, SS 2019, 03.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

18: Algorithmen I, Vorlesung, SS 2019, 01.07.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

17: Algorithmen I, Vorlesung, SS 2019, 26.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

16: Algorithmen I, Vorlesung, SS 2019, 24.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

15: Algorithmen I, Übung, SS 2019, 19.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

14: Algorithmen I, Vorlesung, SS 2019, 17.06.2019

13 | 0:00:00 Start 0:00:12 Rückblick Vorlesung 03.06 0:01:48 Überblick heutige Vorlesung 0:02:48 Prioritätslisten 0:09:43 Anwendungen 0:10:47 Binäre Heaps 0:16:37 Implizite Baum Repräsentation 0:19:51 Pseudocode 0:23:30 Einfügen 0:32:19 Funktion deleteMin 0:36:23 Funktion siftDown 0:39:35 deleteMin: Beispiel 0:41:12 Binärer Heap - Analyse 0:45:32 Binärer Heap - Konstruktion 0:54:43 Ein nützlicher Rechentrick 1:00:41 Heapsort 1:02:31 Heapsort: Beispiel 1:03:06 Heapsort vs Quicksort vs Mergesort 1:06:15 Adressierbare Prioritätslisten 1:10:35 Adressierbare Binäre Heaps 1:12:55 Adressierbare Prioritätslisten - Laufzeiten 1:14:33 Prioritätslisten: Mehr 1:15:28 Zusammenfassung 1:17:45 Rückblick Vorlesung 12.06 1:17:56 Sortierte Folgen

13: Algorithmen I, Vorlesung, SS 2019, 12.06.2019

12 | 0:00:00 Start 0:10:03 Adaptives Sortieren 0:10:59 Insertion Sort: Adaptiv? 0:11:41 Insertion Sort: Erwartete Laufzeit 0:14:09 Natural Merge Sort 0:15:03 Erwartete Anzahl von Runs 0:19:51 Split Sort 0:22:41 Schnelle Mediansuche für Quicksort 0:33:01 Sortieralgorithmen in aktuellen Programmiersprachen Addison Wesley, 2005

12: Algorithmen I, Übung, SS 2019, 05.06.2019

09 | 0:00:00 Starten 0:00:24 Rückblick 0:06:17 Kollisionen 0:11:06 Analyse für zufällige Hash-Funktionen 0:21:54 Universelles Hashing 0:34:35 Beweis Theorem 0:42:08 Hashing mit linearer Suche(""linear probing"") 0:45:08 Der einfache Teil 0:51:03 Remove 1:01:36 Verketten vs. Lineare Suche 1:06:46 Kryptographische Hashfunktionen 1:10:29 Sotieren und Co 1:13:20 Lochkartensortierer 1:19:10 Einfache Sortieralgorithmen 1:21:52 Sentinels am Beispiel Sotieren durch Einfügen 1:24:47 Analyse - - - - - - - Titel der Serie: Algorithmen I, Vorlesung, SS 2019 Beschreibung der Serie: Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet: - Ergebnisüberprüfung (Checkers) und Zertifizierung - Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert - Grundbegriffe des Algorithm Engineering - Effektive Umsetzung verketteter Listen - Unbeschränkte Arrays, Stapel, und Warteschlangen - Hashtabellen: mit Verkettung, linear probing, universelles Hashing - Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort - Selektion: quickselect - Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten - Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit - Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus) - Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche) Literaturhinweise: Algorithms and Data Structures - The Basic Toolbox K. Mehlhorn und P. Sanders Springer 2008 Weiterführende Literatur Algorithmen - Eine Einführung T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein Oldenbourg, 2007 Algorithmen und Datenstrukturen T. Ottmann und P. Widmayer Spektrum Akademischer Verlag, 2002 Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen R. Sedgewick Pearson Studium 2003 Algorithm Design J. Kleinberg and É. Tardos Addison Wesley, 2005 Vöcking et al. Taschenbuch der Algorithmen Springer, 2008

09: Algorithmen I, Vorlesung, SS 2019, 27.05.2019

11 | 0:00:00 Start 0:00:05 Rückblick letzte Vorlesung 0:04:51 Quicksort: Effiziente Implementierung 0:10:56 Halbrekursive Implementierung 0:16:10 Quadratische Komplexität bei gleichen Elementen? 0:29:01 Vergleich Quicksort und Mergesort 0:34:13 Benchmark 0:38:52 Auswahl: Anwendungen 0:45:40 Quickselect: Analyse 0:49:28 Durchbrechen der unteren Schranke – Ganzzahliges Sortieren 0:58:59 Array-Implementierung 1:03:54 Least-Significant-Digit Radit Sort 1:09:39 Mehr zu ganzzahligem Sortieren 1:14:24 Mehr zu Sortieren

11: Algorithmen I, Vorlesung, SS 2019, 03.06.2019

10 | 0:00:00 Starten 0:00:12 Rückblick Vorlesung 27.05 0:03:46 Einfache Sortieralgorithmen 0:05:29 Sortieren durch Mischen 0:09:04 Beispiel 0:11:31 Mischen 0:12:51 Analyse 0:15:49 Untere Schranke 0:17:47 Nicht vergleichsbasierte untere Schranke 0:22:34 Baumbasierte Sortierer Darstellung 0:24:59 Beweis 0:32:29 Randomisierung, Mittlere Ausführungszeit 0:34:42 Quicksort 1:21:24 Größerer Basisfall 1:24:50 Halbrekursive Implementierung

hubhopper

Algorithmen 1, SS2019, Vorlesung

hubhopper