Algorithmen 1, SS2019, Vorlesung

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)

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

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

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)

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

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

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

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

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

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

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

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

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

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

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

08 | 0:00:00 Starten 0:00:05 Roadmap 0:01:12 Verkettete Liste 0:02:56 Skip List 0:06:33 Amortisierte Liste 0:09:45 Aggregat Methode 0:11:28 Hotlist 0:13:39 Hotlist Lookup 0:14:42 Hotlist Insert 0:16:25 Hotlist Amortisierung 0:18:07 Hotlist Delete 0:19:55 Hotlist Aufräumen 0:20:50 Hashtabelle 0:22:14 Duplikaterkennung 0:27:57 Bloom Filter

07 | 0:00:00 Start 0:00:09 Rückblick 0:01:47 Rückblick: unbeschränkte Arrays 0:02:37 Rückblick: amortisierte Analyse 0:03:37 Rückblick: Account-Methode 0:13:22 Stapel und Schlange 0:18:42 Stapel: Operationen 0:22:07 Warteschlangen 0:24:24 zyklisches Array 0:31:12 Deque: Double-Ended Queues 0:34:13 Vergleich: Listen - Felder 0:35:48 Vergleich: Operationen 0:45:54 Ausblick: Weitere Repräsentationen von Folgen 0:47:57 Hashing (Streuspeicherung) 0:51:07 Hashtabellen 0:55:44 Exkurs: Konventionen für Elemente 0:56:50 Hashing: Anwendungen 1:04:29 Kollisionen 1:07:20 Kollisionsauflösung 1:08:03 Hashing mit verketteten Listen 1:22:25 Beispiel: Variante des Geburtstagsparadoxon

06 | 0:00:00 Start 0:00:09 Rückblick Vorlesung 13.05 0:02:26 Folgen als Felder und Listen 0:05:06 Folgen 0:05:09 Ausblick: Komplexität typischer Operationen 0:05:39 Verkettete Listen 0:05:54 Listenglieder (Items) 0:09:22 Trick: Dummy Header 0:10:49 Die Listenklasse 0:16:07 Splice-Operation 0:24:24 Splice: Beispiel 0:25:31 Weitere Operationen: Einfach mit splice 0:27:52 Doch nicht so einfach? Speicherverwaltung! 0:31:14 Items löschen 0:32:49 Elemente einfügen 0:35:47 Ganze Listen manipulieren 0:39:54 Suchen 0:40:33 Ganze Listen manipulieren 0:42:55 Suchen 0:47:19 Funktionalität vs. Effizienz 0:51:24 Einfach verkettete Listen 0:52:44 Einfach verkettete Listen: Invariante? 0:53:59 Einfach verkettete Listen: splice 0:56:55 Einfach verkettete Listen: pushBack 0:59:23 Listen: Zusammenfassung 1:01:50 Felder (Arrays) 1:04:33 Unbeschränkte Felder 1:08:02 Unbeschränkte Felder: Grundidee 1:11:33 Unbeschränkte Felder mit teilweise ungenutztem Speicher 1:15:42 Unbeschränkte Felder: Vergrößern 1:20:08 Unbeschränkte Felder: Verkleinern 1:20:59 Amortisierte Komplexität für unbeschränkte Felder 1:23:40 Beweis: Account-Methode (Konto-Methode) 1:27:57 Amortisierte Analyse: verallgemeinert

05 | 0:00:00 Start 0:00:05 Rückblick Vorlesung 06.05. 0:02:49 Laufzeitanalyse / Rekurrenzen 0:11:03 Eine Rekurrenz für Teile und Herrsche 0:15:43 Master Theorem (einfache Form) 0:20:13 Beweisskizze: Allgemeines 0:25:10 Beweisskizze Fall d<b 0:36:09 Master Theorem Beispiele 0:39:16 Graphen 0:43:09 Bäume 0:44:56 Ein erster Graphalgorithmus 0:54:08 Exkurs: P und NP 1:13:20 Folgen als Felder und Listen 1:17:04 Ausblick: Komplexität typischer Operationen 1:21:27 Listenglieder (Items)

04 | 0:00:00 Start 0:00:05 Begrüßung 0:01:16 Übersicht 0:02:05 1. Effizienz von Algorithmen 0:08:26 Einabegröße und Laufzeit 0:11:23 O-Notation 0:20:35 Betrachtung über Grenzwerte 0:25:46 Basis des Logarithmus 0:26:39 2. Invarianten 0:35:38 3. Teile-und-Herrsche Methode