25 | 0:00:00 Starten 0:00:06 Prioritätslisten 0:03:14 Binäre Heaps 0:07:39 Adressierbare Prioritätslisten 0:08:26 Adressierbare Binäre Heaps 0:09:05 Sortierte Folgen 0:10:42 Binäre Suchbäume 0:16:08 Repräsentation von Graphen 0:23:11 Graphentraversierung 0:30:07 Kürzeste Wege 0:41:22 Minimale Spannbäume 0:46:37 Generische Optimierungsansätze 0:57:13 Zusammenfassung

Algorithmen 1, SS2016, Vorlesung

25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016

24 | 0:00:00 Starten 0:00:06 Kap. 13: Zusammenfassung 0:03:32 Zusammenfassung - Datenstrukturen 0:06:22 Zusammenfassung - Algorithmen 0:09:41 Zusammenfassung - Entwurfstechniken I 0:12:53 Zusammenfassung - Entwurfstechniken II 0:14:53 Zusammenfassung - Analysetechniken 0:18:06 Zusammenfassung - weitere Techniken 0:18:50 Schnelldurchlauf 0:19:32 Amuse Geule 0:20:05 Exkurs: Pseudocode 0:21:47 Exkurs O-Kalkül, die Erste 0:24:04 Algorithmentheorie 0:25:44 Invarianten 0:26:03 Master Theorem 0:29:27 Form Follows Function 0:30:56 Felder (Arrays) 0:31:46 Amortisierte Komplexität unbeschr. Felder 0:32:39 Beweis: Konto-Methode (oder Versicherung) 0:34:35 Hashing (Streuspeicherung) 0:39:27 Sortieren & Co

24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016

Die Vorlesung (23, 11.07.16, SS2016) konnte wegen technischer Probleme nicht aufgezeichnet werden. Der Vorlesungsinhalt ist aber identisch mit der Aufzeichnung vom 06.07.2015 (SS2015) 23 | 0:00:00 Starten 0:00:07 Dynamische Programmierung – Aufbau aus Bausteinen 0:02:12 "Systematische SuchSystematische Suche" 0:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem 0:20:42 Beispielrechnung 0:33:16 Branch-and-Bound – allgemein 0:34:48 Beispielrechnung 0:42:53 Lokale Suche – global denken, lokal handeln 0:47:44 Hill Climbing 0:49:08 Problem: Lokale Optima 0:51:55 Warum die Nachbarschaft wichtig ist 0:53:41 Jenseits von Hill Climbing 1:00:35 Evolutionäre Algorithmen 1:03:40 Zusammenfassung 1:10:03 Werbeblock 1:10:48 Kap. 13: Parallele Algorithmen 1:20:51 Rechnertypen 1:24:10 Gemeinsamer Speicher (shared memory) 1:25:07 Rechenmodell

23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016

22 | 0:00:00 Starten 0:00:10 Erinnerung VL 04.07.2016 0:04:13 Wiederholung Beispiel: Rucksackproblem 0:05:15 Nie zurückschauen - Greedy-Algorithmen 0:08:50 Beispiel: Rucksackproblem (1) 0:17:16 Dynamische Programmierung - Aufbau aus Bausteinen 0:18:29 Beispiel: Rucksackproblem (2) 0:21:09 Dynamische Programmierung 0:22:37 Beweis des Lemmas 0:29:10 Berechnung von P(i,C) elementweise 0:33:21 Rekonstruktion des Lösung 0:34:54 Beispiel 0:40:36 Beginn Übung 11 0:40:41 Roadmap 0:41:22 Schwierige Probleme 0:46:15 Erinnerung: Lineare Programme 0:47:48 LP graphisch 0:52:37 Erinnerung: Travelling Salesman Problem 0:53:59 Ein ILP für TSP 0:59:25 Heuristiken 1:01:14 Ameisen Algorithmen 1:04:50 Vertex Cover 1:06:25 Approximation 1:07:21 Eine Approximation für Vertex Cover 1:10:53 Metaheuristiken und Nachbarschaften 1:12:22 Nachbarschaftsheuristiken 1:19:10 Lokale Suche für Vertex Cover 1:20:13 Tabu-Suche für Vertex Cover 1:22:29 Zusammenfassung

22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016

21 | 0:00:00 Starten 0:00:06 Erinnerung VL 29.06.2016 0:02:08 Kruskals Algorithmus 0:04:38 Union-Find Datenstruktur 0:18:24 Pfadkompression 0:20:57 Union by Rank 0:26:19 Analyse Union by Rank bzw. Pfadkompression 0:40:55 Kruskal mit Union-Find 0:45:05 Beispiel 0:49:09 Vergleich Jarník-Prim - Kruskal 0:50:55 Mehr MST-Algorithmen 0:54:03 Zusammenfassung 0:56:05 Kap. 12: Generische Optimierungsansätze 0:56:47 Durchgehendes Beispiel: Rucksackproblem 0:58:30 Allgemein: Maximierungsproblem 1:00:28 Black-Box-Löser 1:01:45 Lineare Programmierung 1:04:22 Ein einfaches Beispiel 1:07:13 Beispiel: Kürzester Weg 1:09:27 Eine Anwendung - Tierfutter 1:11:04 Verfeinerungen 1:12:48 Algorithmen und Implementierungen 1:14:14 Ganzzahlige Lineare Programmierung 1:15:09 Beispiel: Rucksackproblem 1:16:20 Umgang mit (M)ILPs

21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016

20 | 0:00:00 Starten 0:00:06 Erinnerung VL 27.06.2016 0:02:09 Kap. 11: Minimale Spannbäume 0:02:28 Minimale Spannbäume (MST) 0:03:22 Minimale aufspannende Wälder (MSF) 0:03:36 Anwendungen 0:04:57 MST-Kanten auswählen und verwerfen: Die Schnitteigenschaft (Cut Property) 0:12:19 MST-Kanten auswählen und verwerfen: Die Kreiseigenschaft (Cycle Property) 0:15:54 Der Jarník-Prim-Algorithmus 0:28:39 Analyse 0:32:00 Kruskals Algorithmus (1956) 0:37:47 Kruskals Algorithmus - Korrektheit 0:40:56 Union-Find Datenstruktur 0:44:15 Beginn Übung 10 0:44:15 Kürzeste Wege Algorithmen: Bellman-Ford 0:45:40 Bellman-Ford: Pseudo-Code 0:46:40 Bellman-Ford: Korrektheit (Beweis-Idee) 0:48:53 Bellman-Ford: Beispiel 0:53:03 Bellman-Ford: Bestimmung eines negativen Kreises 0:55:03 Minimale Spannbäume 0:57:00 Minimale Spannbäume: Jarník-Prim 0:58:37 Minimale Spannbäume: Kruskal 1:00:00 Steinerbäume 1:05:42 Steinerbaum: Was kann schief gehen? 1:10:09 Problem des Handlungsreisenden (TSP)

20: Algorithmen I, Vorlesung und Übung, SS 2016, am 29.06.2016

19 | 0:00:00 Starten 0:02:13 Negative Kosten 0:07:10 Zurück zu Basiskonzepten 0:09:47 Mehr Basiskonzepte 0:11:45 Allgemeines Korrektheitskriterium 0:19:06 Algorithmen brutal - Bellman-Ford-Algorithmus für beliebige Kantengewichte 0:26:44 Beispiel 0:30:07 Bellman-Ford - Laufzeit 0:32:06 Ayklische Graphen 0:36:15 Von überall nach überall 0:38:54 Kürzeste Wege: Zusammenfassung 0:40:17 Mehr zu kürzesten Wegen 0:43:29 Exkurs: Routing in Straßennetzwerken 0:46:00 Straßennetzwerke 0:46:23 Distanz zu einem Zielknoten t 0:48:03 Ideen für Routenplanung 0:50:12 Approach: Transit-Node Routing 0:50:43 Beispiel 0:53:58 Erste Beobachtung 0:55:45 Zweite Beobachtung 0:57:22 Beispiel: Transitknoten 0:57:41 Experimente 0:58:23 Offene Fragen 0:59:31 Minimale Spannbäume 1:02:52 Minimale aufspannende Wälder 1:03:23 Anwendungen

19: Algorithmen I, Vorlesung, SS 2016, am 27.06.2016

18 | 0:00:00 Starten 0:00:06 Erinnerung VL 20.06.2016 0:02:10 Erinnerung: analoger Algorithmus 0:03:25 Dijkstra: Implementierung? 0:08:39 Prioritätsliste 0:10:22 Implementierung ≈ BFS mit PQ statt FIFO 0:15:06 Beispiel 0:17:27 Dijkstra: Laufzeit 0:26:20 Analyse im Mittel 0:28:34 Monotone ganzzahlige Prioritätslisten 0:29:57 Negative Kosten 0:30:33 Beginn Übung 9 0:30:39 Roadmap 0:30:59 Organisatorisches 0:31:37 Aufgabe 3 0:32:26 Breitensuche (Wie war das nochmal...) 0:34:48 Breitensuche für nicht zusammenhängende, ungerichtete Graphen 0:35:41 Breitensuche in DAGs für nicht zusammenhängende Graphen 0:38:08 Dijkstras Algorithmus 0:40:56 Bidirektionale Suche 0:45:09 Bidirektionale Suche - Definitionen 0:46:14 Bidirektionale Suche - Vorgehen 0:46:20 Pingo! Was sind gute Abbruchstrategien? 0:49:19 Abbruchstrategie (1) 0:53:36 Abbruchstrategie (2) 0:54:13 Beispiel 0:55:02 Bemerkungen 0:56:01 Graph-Datenstruktur 0:56:07 Pingo! Wie schnell wird eine Routing-Anfrage? 0:57:54 Speedup Techniques 0:59:38 Mehr davon?

18: Algorithmen I, Vorlesung und Übung, SS 2016, am 22.06.2016

17 | 0:00:00 Starten 0:00:08 Erinnnerung VL 15.06.2016 0:06:19 DFS-Nummerierung 0:09:29 Fertigstellungszeit 0:11:10 Kantenklassifizierung bei DFS 0:12:31 Erinnerung: Tiefensuchschema 0:16:48 Topologische Sortierung 0:19:43 Topologische Sortieren mittels DFS 0:25:19 Starke Zusammenhangskomponenten 0:29:45 Mehr DFS-basierte Linearzeitalgorithmen 0:32:40 BFS <-> DFS 0:36:14 Kap. 10: Kürzeste Weg 0:40:50 Anwendungen 0:43:23 Grundlagen 0:46:19 Azyklische Graphen 0:46:39 Kantengewicht >= 0 0:48:23 Dijkstras Algorithmus 0:53:07 Korrektheit der Bindfäden 0:54:53 Edsger Wybe Dijkstra 1930-2002 0:57:10 Allgemeine Definition 1:00:17 Kante (u,v) relaxieren 1:03:48 Dijkstras Algorithmus: Pseudocode 1:06:56 Beispiel 1:11:27 Korrektheit 1:13:03 v erreichbar -> v wird irgendwann gescannt

17 | 0:00:00 Starten 0:00:08 Erinnnerung VL 15.06.2016 0:06:19 DFS-Nummerierung 0:09:29 Fertigstellungszeit 0:11:10 Kantenklassifizierung bei DFS 0:12:31 Erinnerung: Tiefensuchschema 0:16:48 Topologische Sortierung 0:19:43 Topologische Sortieren mittels DFS 0:25:19 Starke Zusammenhangskomponenten 0:29:45 Mehr DFS-basierte Linearzeitalgorithmen 0:32:40 BFS DFS 0:36:14 Kap. 10: Kürzeste Weg 0:40:50 Anwendungen 0:43:23 Grundlagen 0:46:19 Azyklische Graphen 0:46:39 Kantengewicht >= 0 0:48:23 Dijkstras Algorithmus 0:53:07 Korrektheit der Bindfäden 0:54:53 Edsger Wybe Dijkstra 1930-2002 0:57:10 Allgemeine Definition 1:00:17 Kante (u,v) relaxieren 1:03:48 Dijkstras Algorithmus: Pseudocode 1:06:56 Beispiel 1:11:27 Korrektheit 1:13:03 v erreichbar -> v wird irgendwann gescannt

17: Algorithmen I, Vorlesung, SS 2016, am 20.06.2016

16 | 0:00:00 Starten 0:02:17 Graphentraversierung 0:03:44 Graphentraversierung als Kantenklassifizierung 0:07:01 Breitensuche 0:15:47 Repräsentation des Baums 0:22:01 Repräsentation von Q und Q' mittels FIFO 0:23:47 Alternative Repräsentation von Q und Q' 0:25:59 Tiefensuche 0:28:51 Tiefensuchschema für G = (V,E) 0:32:49 DFS-Baum 0:35:59 BEGINN ÜBUNG 0:36:12 Nachtrag: Quicksort, alternative Partitionierung 0:37:27 Grundlagen der Graphentheorie 0:37:37 Graphen und Relationen 0:40:14 Teilbarkeitsgraph 0:41:53 Der Hyperwürfel Q3 0:42:47 Knotengrad 0:43:36 Handshaking Lemma 0:47:19 Adjazenz- und Inzidenzmatrix 0:48:40 Beispiel Adjazenz- und Inzidenzmatrix 0:52:39 Graphen als Matrizen 0:52:57 Wiederholung: DAG 0:54:19 Graphen als Matrizen 0:56:34 Wege, Kreise und Zusammenhang 0:57:20 Eulersche und Hamiltone Kreise 0:59:15 Eulersche Kreise - Anwendungsbeispiel 1:01:07 Satz von Euler (Graphen) 1:07:28 Breitensuche 1:09:46 Beispielanwendung Breitensuche

16: Algorithmen I, Vorlesung und Übung, SS 2016, am 15.06.2016

15 | 0:00:00 Starten 0:00:10 Adjazenzfelder 0:02:11 Kantenliste --> Adjazenzfeld 0:06:06 Beispiel 0:07:28 Operationen für Adjanzenzfelder 0:11:40 Kantenanfragen 0:13:17 Adjazenzlisten 0:16:30 Adjazenzlisten aufrüsten 0:18:18 Customization (Zuschneiden) 0:19:37 Beispiel: DAG-Erkennung 0:26:59 Adjazenz-Matrix 0:33:00 Pfade zählen mittels LA 0:35:42 Beispiel, wo Graphentheorie bei LA hilft 0:40:09 Implizite Repräsentation 0:41:54 Zusammenhangstest für Intervallgraphen 0:42:01 Beispiel 0:47:21 Graphrepräsentation: Zusammenfassung

15: Algorithmen I, Vorlesung, SS 2016, am 13.06.2016

14 | 0:00:00 Starten 0:00:06 Erinnerung letzte Vorlesung 0:01:32 Erinnerung Grundidee sortierte Folgen 0:02:57 Abgrenzung 0:06:18 Sortierte Folgen - Anwendungen 0:07:19 Anwendungsbeispiel: Best Fit Bin Packing 0:11:52 Binäre Suchbäume 0:14:33 Varianten, Bemerkungen 0:16:12 locate(k) 0:22:07 Invariante von locate(k) 0:23:39 Ergebnisberechnung von locate(k) 0:25:11 Laufzeit von locate(k) 0:27:17 Naives Einfügen 0:30:41 Beispiel 0:32:14 Suchbäume balancieren 0:34:48 (a,b)-Bäume 0:37:31 Items 0:39:55 Initialisierung 0:40:52 Locate 0:42:46 Locate - Laufzeit 0:47:15 Einfügen - Algorithmenskizze 0:51:19 Einfügen - Beispiel 0:57:32 Einfügen - Korrektheit 0:59:20 Einfügen - Implementierungsdetails 1:01:28 Einfügen - Pseudocode 1:08:04 Entfernen - Algorithmenskizze 1:13:50 Entfernen - Beispiel 1:17:15 Entfernen - Korrektheit 1:18:02 Einfügen und Entfernen - Laufzeit 1:18:55 (a,b)-Bäume Implementierungsdetails 1:20:21 Mehr Operationen 1:22:36 Amortiersierte Analyse von insert und remove 1:23:12 Erweiterte (augmentierte) Suchbäume 1:24:07 Elternzeiger 1:25:59 Teilbaumgrößen

14: Algorithmen I, Vorlesung, SS 2016, am 06.06.2016

13 | 0:00:00 Starten 0:04:45 Heapsort <-> Quicksort <-> Mergesort 0:08:11 Adressierbare Prioritätslisten 0:12:46 Adressierbare Prioritätslisten: Anwendungen 0:16:26 Adressierbare Binäre Heaps 0:20:36 Adressierbare Prioritätslisten - Laufzeiten 0:21:33 Prioritätslisten: Mehr 0:23:22 Prioritätslisten: Zusammenfassung 0:24:21 Was haben wir jenseits von Prioritätslisten gelernt? 0:25:16 Sortierte Folgen 0:28:59 Statisch: Sortiertes Feld mit binärer Suche 0:33:44 Binäre Suche: Beispiel 0:35:11 Dynamische Sortierte Folgen - Grundoperationen 0:35:55 Mehr Operationen 0:38:01 Noch mehr Operationen 0:40:34 BEGINN ÜBUNG 0:40:49 Roadmap 0:41:24 Organisatorisches 0:43:45 Erinnerung: Bucketsort 0:45:20 Bucket Sort für [0,1) 0:53:41 Sortieren- Auf einen Blick 0:56:45 Priority Queues 0:59:00 Bucket Queue 1:02:55 Binary Radix Heap 1:17:48 Schnelle Heaps 1:18:34 Zusammenfassung

13 | 0:00:00 Starten 0:04:45 Heapsort Quicksort Mergesort 0:08:11 Adressierbare Prioritätslisten 0:12:46 Adressierbare Prioritätslisten: Anwendungen 0:16:26 Adressierbare Binäre Heaps 0:20:36 Adressierbare Prioritätslisten - Laufzeiten 0:21:33 Prioritätslisten: Mehr 0:23:22 Prioritätslisten: Zusammenfassung 0:24:21 Was haben wir jenseits von Prioritätslisten gelernt? 0:25:16 Sortierte Folgen 0:28:59 Statisch: Sortiertes Feld mit binärer Suche 0:33:44 Binäre Suche: Beispiel 0:35:11 Dynamische Sortierte Folgen - Grundoperationen 0:35:55 Mehr Operationen 0:38:01 Noch mehr Operationen 0:40:34 BEGINN ÜBUNG 0:40:49 Roadmap 0:41:24 Organisatorisches 0:43:45 Erinnerung: Bucketsort 0:45:20 Bucket Sort für [0,1) 0:53:41 Sortieren- Auf einen Blick 0:56:45 Priority Queues 0:59:00 Bucket Queue 1:02:55 Binary Radix Heap 1:17:48 Schnelle Heaps 1:18:34 Zusammenfassung

13: Algorithmen I, Vorlesung und Übung, SS 2016, am 01.06.2016

12 | 0:00:00 Starten 0:00:06 Erinnerung VL 25.03.2016 0:03:43 Erinnerungsfolie: Bucketsort 0:04:58 Erinnerungsfolie: Beispiel K=4 0:06:09 Array-Implementierung 0:13:04 Beispiel: a=(3,1,2,3,0,0,3,2,1), K=4 0:15:55 Kd Schlüssel 0:22:34 Beispiel: LSD-Radix-Sort 0:23:56 Mehr zu ganzzahligem Sortieren 0:30:18 Sortieren: vergleichsbasiert - ganzzahlig 0:34:21 Mehr zu Sortieren 0:38:18 Was haben wir jenseits von Sortieren gelernt? 0:40:05 Prioritätslisten 0:40:37 Prioritätslisten (priority queues) 0:42:43 Prioritätslisten - Anwendungen 0:46:20 Binäre Heaps 0:49:33 Implizite Baum-Repräsentation 1:01:53 Funktion deleteMin 1:07:50 Procedure siftDown 1:10:53 Beispiel: deleteMin 1:11:36 Binärer Heap - Analyse 1:12:47 Binärer Heap - Konstruktion 1:22:09 Ein nützlicher Rechentrick 1:24:00 Heapsort 1:27:03 Beispiel: Heapsort

12: Algorithmen I, Vorlesung, SS 2016, am 30.05.2016

11 | 0:00:00 Starten 0:00:06 Erinnerung VL vom 23.05.2016 0:13:52 Vergleich Quicksort vs Mergesort 0:21:31 Auswahl (Selection) 0:24:50 Beispiel 0:26:52 Auswahl Anwendungen 0:29:18 Quickselect 0:33:56 Beispiel 0:37:04 Quickselect - Analyse 0:37:59 Mehr zum Auswahlproblem 0:42:01 Durchbrechen der unteren Schranke - Ganzzahliges Sortieren 0:43:11 Schlüssel 0..K-1 - Eimer-Sortieren (bucket sort) 0:47:54 6.Übung zu Algorithmen 0:49:53 Quicksort 1:09:05 Dual Pivot Quicksort 1:19:21 Ganzzahliges Sortieren

hubhopper

Algorithmen 1, SS2016, Vorlesung

hubhopper