13 | 0:00:00 Starten0:00:36 Was wissen wir über die Jobs?0:02:32 Was wissen wir über die Prozessoren?0:05:44 Zufälliges Zuordnen0:07:08 Work Stealing0:10:58 Backtracking over Transition Functions0:12:02 An Abstract Model: Tree Shaped Computations0:17:37 Splitting Stacks0:21:27 Other Problem Categories0:27:01 Limits of the Model0:29:35 Receiver Init…

12 | 0:00:00 Starten0:00:10 Parallele Prioritätslisten0:02:03 Branch-and-Bound0:05:17 Einfache Probabilistische Eigenschaften0:08:11 Parallele Realisierung II0:09:58 Randomisierte Selektion0:15:14 Parallele Implementierung0:21:11 Implementierung IBM SP-2 m=2^240:23:27 Implementierung Cray T3D, m=2^240:26:07 Lastverteilung0:30:25 Kostenmaß0:34:35 Wa…

11 |0:00:00 Starten0:00:14 Finding lightest incident edges0:01:19 Pseudotrees - Rooted Trees0:03:00 Randomized Linear Time Algorithm0:04:24 Parallel Filter Kruskal0:05:40 Parallele Prioritätlisten0:10:34 Naive Implementierung0:11:30 Branch-and-Bound0:25:18 Sequentielles Branch-and-Bound0:35:27 Paralleles Branch-and-Bound0:38:20 Analyse0:52:09 Der A…

10 | 0:00:00 Starten0:00:10 Minimum Spannung Trees0:03:06 Selecting and Discarding MST Edges0:09:01 Kruskal's Algorithm0:12:41 Edge Contraction0:16:29 Finding lightest incident edges0:24:06 Structure of Resulting Components0:28:51 Pseudotrees -> Rooted Trees0:31:07 Rooted Trees -> Rooted Stars by Doubling0:32:43 Contraction0:42:36 Recursion0:45:21 …

09 | 0:00:00 Starten0:00:10 Datenaustausch bei unregelmäßigen Nachrichtenlängen0:02:02 Der Vogel-Strauß-Algorithmus0:05:41 h-Relation0:07:37 Offline h-Relationen im duplex Modell0:17:17 Offline h-Relationen im Simplex-Modell0:22:08 How Helper Hasten h-Relations0:23:02 Ein ganz simpler Fall0:24:53 Zwei Dreiecke0:31:25 Reduktion h-Relation =>(h/2) 2-…

08 | 0:00:00 Starten0:01:52 Kollektive Kommunikation0:05:06 All-to-all Personalized Communication0:08:09 Der 1-Faktor-Algorithmus0:14:46 Datenaustausch bei unregelmäßigen Nachrichtenlänge0:17:42 Ein einfacher verteilter Algorithmus- Der Zweiphasenalgorithmus0:33:27 List Ranking0:42:37 Motivation II0:45:26 Doubling using CREW PRAM, n=p0:55:37 Entfer…

07 | 0:00:00 Starten0:00:10 Analyse von Sample Sort0:07:27 Samples Sortieren0:07:46 Mehrwegemischen0:12:51 Multisequence Selection0:16:24 Splitter Selection0:19:44 Verteilte Multisequence Selection0:30:41 CRCW Sortieren in logarithmischer Zeit0:35:50 Beispiel0:37:54 Kollektive Kommunikation0:39:18 Präfixsummen0:41:29 Einfache Pipeline0:42:41 Hyperw…

06 | 0:00:00 Starten0:00:25 Schnelles ineffizientes Ranking0:02:41 Sortieren größerer Datenmengen0:02:48 Zurück zum schnellen Ranking0:04:42 Verallgemeinerung für m >>p nach schema F?0:10:01 Distributed memory parallel quicksort0:10:16 Load Balance0:24:28 Die gute Nachricht:0:32:19 Bessere Lastbalanceierung?0:35:32 Multi-Pivot Verfahren0:42:23 Anal…

05 | 0:00:00 Starten0:00:10 Analyse0:02:11 Noch ein optimaler Algorithmus0:02:22 Analyse, Telefonmodell0:02:38 Diskussion0:03:28 Sortieren0:04:04 Schnelles ineffizientes Ranking0:12:47 Sortieren größerer Datenmengen0:17:01 Zurück zum schnellen Ranking0:29:25 Beispiel0:29:40 row all-gather-merge0:32:47 Genauere Analyse, n 10 byte elemente pro PE0:36…

04 | 0:00:00 Starten0:00:10 Übung0:01:09 Starten0:17:12 Analyse0:19:48 Diskussion0:20:39 H-Trees0:22:18 Nachteile baumbasierter Broadcasts0:23:21 23-Broadcast: Two T(h)rees for the Price of one0:24:27 Root Process0:25:30 Other Process0:26:26 Belibiege Prozessorzahl0:28:35 Aufbau der Bäume0:29:21 Aufbau kleinerer Bäume(ohne Wurzel)0:30:39 Kanten fär…

02 | 0:00:00 Starten0:02:01 Analyse paralleler Algorithmen0:02:17 PRAM vs. reale Parallelrechner0:03:55 (Symmetric) Shared Memory0:05:03 Probleme0:07:22 Realistische Shared Memory Modelle0:09:05 Atomare Instruktionen: Compare-And-Swap0:09:17 Parallel External Memory0:10:15 Modelle mit Verbindungsnetzwerken0:11:13 Reale Maschinen Heute0:11:40 Umgang…

03 | 0:00:00 Starten0:00:10 Ein einfaches paralleles Modell: PRAMs0:00:46 PRAM vs. reale Parallelrechner0:01:33 Shared Memory0:01:58 Modelle mit Verbindungsnetzwerken0:02:23 Explizites ,,Store-and-Forward''0:04:17 Typische Verbindungsnetzwerke0:04:37 Vollständige Verknüpfung0:06:03 Graph- und Schaltkreisdarstellung v.Algorithmen0:07:06 Schaltkreise…

01 | 0:00:00 Starten0:01:22 Warum Parallelverarbeitung0:05:36 Thema der Vorlesung0:06:52 Überblick0:09:05 Schwesterveranstaltungen0:12:53 RAM/von Neumann Modell0:14:17 Algorithmenanalyse0:17:04 Ein einfaches paralleles Modell: PRAMs0:19:52 Zugriffskonflikte0:25:51 Beispiel: Global Or0:27:30 Beispiel: Maximum auf common CRCW PRAM0:33:07 Formulierung…

23 | 0:00:00 Starten0:00:06 Schnuppervorlesung Sicherheit0:00:39 Überblick0:03:10 Ziel0:04:56 Motivation0:09:01 Grundidee0:11:20 Erste Eigenschaften0:14:56 Überblick RSA0:21:55 RSA-Schlüsselgenerierung0:28:49 Korrektheit von RSA0:38:04 Sicherheit?0:43:31 Semantische Sicherheit für Public-Key-Verschlüsselung0:50:04 Äquivalenter Begriff: IND-CPA0:55:…

22 | 0:00:00 Starten0:01:04 Kap. 13: Zusammenfassung0:02:22 Zusammenfassung - Datenstrukturen0:07:39 Zusammenfassung - Algorithmen0:11:29 Zusammenfassung - Entwurfstechniken I0:15:46 Zusammenfassung - Entwurfstechniken II0:20:07 Zusammenfassung - Analysetechniken0:26:12 Zusammenfassung - weitere Techniken…

21 | 0:00:00 Starten0:00:06 Roadmap Übung0:00:38 Schwierige Probleme0:09:30 Erinnerung: Lineare Programme0:15:36 Erinnerung: Travelling Salesman Problem0:17:15 Ein ILP für TSP0:24:57 Heuristiken0:25:55 Ameisenalgorithmen0:30:41 Vertex Cover0:32:22 Approximation0:34:48 Eine Approximation für Vertex Cover0:39:05 Metaheuristiken und Nachbarschaften0:4…

20 | 0:00:00 Starten0:03:19 Wdh. Dynamische Programmierung0:08:34 Algorithmenentwurf mittels dynamischer Programmierung0:14:18 Anwendungen dynamischer Programmierung0:17:38 Gegenbeispiel: Teilproblemeigenschaft0:18:42 Gegenbeispiel: Austauschbarkeit0:20:53 Systematische Suche0:23:44 Beispiel: Branch-and-Bound für das Rucksackproblem0:32:09 Beispiel…

19 | 0:00:00 Starten0:00:06 Kap. 12: Generische Optimierungsansätze0:01:08 Durchgehendes Beispiel: Rucksackproblem0:04:07 Black-Box-Löser0:04:40 Lineare Programmieurng0:08:09 Beispiel: Kürzeste Wege0:09:11 Eine Anwendung - Tierfutter0:10:38 Verfeinerungen0:11:52 Algorithmen und Implementierungen0:13:15 Ganzzahlige Lineare Programmierung0:16:09 Umga…

18 | 0:00:00 Starten0:00:06 Kap. 11: Minimale Spannbäume0:03:34 Anwendungen0:13:56 Der Jarnik-Prim-Algorithmus0:24:48 Kruskals Algorithmus1:03:02 Vergleich Jarnik-Prim Kruskal1:04:09 Mehr MST-Algorithmen1:06:50 ZusammenfassungVon Prof. Dr. Jörn Müller-Quade

17 | 0:00:00 Starten0:00:37 Mehr zu kürzesten Wegen0:02:22 Exkurs: Routing in Straßennetzwerken0:05:58 Distanz zu einem Zielknoten t 0:07:25 Ideen für Routenplannung0:10:51 Approach: Transit-Node Routing0:16:55 Erste Beobachtung0:19:01 Zweite Beobachtung0:20:27 Transit-Node Routing0:24:28 Experimente0:27:25 Offene Fragen0:29:46 Anfang der Übung0:30…

16 | 0:00:00 Starten0:00:10 Allgemeine Definition0:02:19 Kante (u,v) relaxieren0:04:30 Dijkstras Algorithmus0:06:53 Beispiel0:11:27 Korrektheit0:12:23 v erreichbar -> 0:14:39 v gescannt ->0:18:46 Dijkstra: Implementierung?0:20:01 Prioritätsliste0:21:03 Imlementierung0:25:38 Beispiel0:29:27 Dijkstra: Laufzeit0:36:22 Analyse im Mittel0:37:23 Monotone…

15 | 0:00:00 Starten0:00:08 Tiefensuche0:11:31 DFS-Baum0:28:38 Topologische Sortierung0:40:32 Kap. 10: Kürzeste Wege0:45:23 Grundlagen0:52:47 Allgemeine Definitionen0:58:31 Dijkstras Algorithmus: PseudocodeDas Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:- Ergebnisüberprüfung (Checkers) und Ze…

14 | 0:00:00 Starten0:00:36 Kap. 8: Repräsentation von Graphen: Einleitung0:04:35 Repräsentation von Graphen0:08:29 Notation und Konventionen0:09:48 Ungerichtete -> gerichtete Graphen0:10:30 Operationen0:14:03 Kantenfolgenrepräsentation0:15:33 Adjazenzfelder0:19:36 Kantenliste -> Adjazenzfeld0:26:21 Operationen für Adjazenzfelder0:29:26 Kantenanfra…

13 | 0:00:00 Starten0:00:25 Sortierte Folgen0:01:35 Dynamische Sortierte Folgen0:02:34 Binäre Suchbäume0:03:16 Varianten, Bemerkung0:04:28 locate(k)0:07:26 Invariante von locate(k)0:09:06 Ergebnisberechnung von locate(k)0:11:09 Laufzeit von locate(k)0:12:47 Naives Einfügen0:15:22 Suchbäume balancieren0:17:48 (a, b)-Bäume1:06:59 Erweiterte Suchbäume…

12 | 0:00:00 Starten0:00:09 Adressierbare Prioritätslisten0:06:42 Adressierbare Binäre Heaps0:09:16 Adressierbare Prioritätslisten-Laufzeiten0:11:56 Prioritätslisten-Zusammenfassung0:13:41 Sortierte Folgen0:16:44 Statisch: Sortiertes Feld mit binärer Suche0:29:06 Dynamische Sortierte Folgen-Grundoperationen0:30:21 Mehr Operationen0:34:10 Abgrenzung…

11 | 0:00:00 Starten0:00:11 Vorlesung0:00:14 Heap-Algorithmus0:04:52 Prozedur siftDown0:12:20 deleteMin: Beispiel0:15:46 Binärer Heap0:27:34 Nützlicher Rechentrick0:32:02 Heapsort0:38:16 Heapsort, Quicksort, Mergesort0:40:43 Adressierbare Prioritätslisten0:40:48 Übung 0:41:39 Roadmap0:43:44 Erinnerung: Bucketsort0:44:45 Bucket Sort für [0, 1)0:51:4…

10 | 0:00:00 Starten0:00:08 Halbrekursive Implementierung0:04:39 Quadratische Komplexität bei gleichen Elementen?0:11:21 Vergleich Quicksort Mergesort0:15:33 Auswahl (Selection)0:20:18 Quickselect0:37:05 Array-Implementierung0:47:51 Least-Sigmificant-Digit Radix-Sortieren0:55:05 Mehr zu ganzzahligem Sortieren1:04:41 Prioritätslisten1:09:21 Binäre H…

09 | 0:00:00 Starten0:00:13 Quicksort-zufälliger Pivot 0:05:32 Satz: Quicksort hat erwartete Laufzeit0:20:42 Exkurs: Harmonische Summe0:27:19 Quicksort: Effiziente Implementierung0:38:01 Beispiel: Partinonierung0:41:31 Beispiel: Rekursion0:43:42 Größerer Basisfall0:45:48 Inplace? Wirklich?0:47:33 Halbrekursive Implementierung0:50:15 Quadratische Ko…

08 | 0:00:00 Starten0:00:31 Einfache Sortieralgorithmen0:07:38 Analyse0:11:03 Sortieren durch Mischen0:26:56 Baumbasierte Sortier-Darstellung0:43:46 Randomisierung, Mittlere Ausführungszeit0:44:35 Quicksort - erster VersuchVon Prof. Dr. Jörn Müller-Quade

07 | 0:00:00 Starten0:02:06 Verketten Lineare Suche0:06:50 Mehr Hashing0:10:29 Hashtabellen für assoziative Arrays0:14:49 Kryptographische Hashfunktion0:20:50 Sortieren & Co0:36:21 4. Übung zu Algorithmen 10:36:55 Hashtabelle mit einfach verketteten Listen0:40:13 Duplikaterkennung1:10:13 Bloom Filter…

06 | 0:00:00 Starten0:00:08 Hashing (Streuspeicherung)0:03:07 Hashtabellen0:06:19 Hashing: Anwendungen0:10:49 Ein (über)optimistischer Ansatz0:12:44 Kollisionen0:15:16 Kollisionsauflösung0:15:48 Hashing mit verketteten Listen0:22:30 Etwas Wahrscheinlichkeitstheorie für den Hausgebrauch0:41:59 Analyse für zufällige Hash-Funktion0:49:42 Universelles …

05 | 0:00:00 Starten0:00:08 Beginn Vorlesung0:01:08 Erinnerung VL vom 08.05.20170:01:47 Stapel und Schlangen0:06:03 Stapel0:10:30 Warteschlangen / First-In-First-Out / FIFO0:11:12 FIFO0:17:58 Warteschlangen0:20:38 Deque0:24:29 Vergleich: Listen - Felder0:27:57 Ausblick: Weitere Repräsentationen von Folgen0:29:15 Hashings (Steuerspeicherung)0:29:50 …

03 | 0:00:00 Starten0:01:03 Organisatorisches0:06:08 Effizienz von Algorithmen0:14:41 Eingabegröße und Laufzeit0:17:23 Genauer: (asymptotische) Laufzeit0:21:29 (Asymptotische) O-Notation0:22:56 O-Notation (Intuition)0:28:09 Asymptotische Notationen0:31:28 Betrachtung über Grenzwerte0:42:11 Basis des Logarithmus0:45:48 Invarianten1:06:51 Teile-und-H…

04 | 0:00:00 Starten0:00:15 P und NP0:03:17 Folgen0:05:22 Form Follows Function0:11:36 Listenglieder (Items)0:13:41 Trick: dummy header0:17:39 Die Listenklasse0:33:08 Items löschen0:35:41 Elemente einfügen0:40:29 Suchen0:46:15 Einfach verkettete Listen0:52:41 Listen: Zusammenfassung, Verallgemeinerungen0:53:44 Felder (Arrays)0:56:32 Unbeschränkte F…

0:00:00 Starten0:00:07 Erinnerung VL 24.04.20170:01:55 Karatsuba-Ofman Multiplikation0:04:33 Skalierung0:06:59 Blick über den Tellerrand0:09:45 Algorithmenanalyse0:13:07 Zweite Vereinfachung: Asymptotik0:19:44 O-Kalkül Rechenregeln0:23:29 Maschinenmodell: RAM0:31:59 ""Kleine"" ganze Zahlen?0:35:00 Algorithmenanalyse im RAM-Modell0:38:15 Mehr Maschi…

01 |0:00:00 Starten0:00:10 Algorithmus? Kann man das essen?0:01:30 Algorithmik0:02:59 Datenstruktur0:03:56 Themenauswahl: Werkzeugkasten0:06:34 Inhaltsübersicht0:10:11 Amuse Geule0:14:59 Addition0:18:47 Exkurs: Pseudocode0:21:38 Exkurs vom Exkurs: Wieso nicht C++/Java-like?0:24:00 Ziffernmultiplikation0:32:18 Schulmultiplikation0:38:06 Exkurs O-Kal…

26 | 0:00:00 Starten0:01:13 Fortgeschrittene Graphenalgorithmen: 2 Kürzeste Wege0:02:31 Monotone ganzzahlige Prioritätslisten0:03:05 Radix-Heaps0:04:38 All-Pairs Shortest Paths0:06:18 3 Anwendungen von DFS0:08:27 Algorithms 1956-now0:11:39 Preflow-Push Algorithms0:13:38 5 Externe Algorithmen0:15:04 6 Fixed-Parameter-Algorithmen0:16:16 Fixed paramet…

25 | 0:00:00 Starten0:00:24 Wavlet Tree0:08:46 Allgemeine Reporting Query0:09:02 Bitvektoren0:15:34 Suffix Array0:15:45 Backward Search0:20:37 Wavelet Tree Example: Calculate Rank0:24:21 Index size comparison0:26:55 Beginn Übung 130:27:01 Themenübersicht0:28:27 Geometrische Algorithmen0:32:55 Geometrische Methoden0:35:13 Sweep-Line0:39:04 One-Dimen…

24 | 0:00:00 Starten0:00:14 Verallgemeinerung0:10:21 Überlappungen finden0:11:52 Platzverbrauch0:12:45 Mehr Linienschnitt0:13:34 9.2 2D Konvexe Hülle0:17:35 Graham's Scan0:23:22 3D Konvexe Hülle0:25:05 9.3 Kleinste einschließende Kugel0:31:29 Kleinste einschließende Kugel - Korrektheitm0:35:57 Kleinste einschließende Kugel - Analyse0:49:17 9.4 2D B…

23 | 0:00:00 Starten0:00:07 Übung 12 - Online Algorithmen0:02:44 Grundlagen0:04:19 Gütemaß0:05:21 Ski Rental Problem0:06:46 Randomisierte Ski Rental Strategie0:18:02 Doubling Strategie0:18:52 Online Bidding0:40:30 Zusammenfassung0:41:39 Vorlesung: Kapitel 9 - Geometrische Algorithmen0:45:17 Elementare Geometrische Objekte0:49:22 Typische Fragestell…

22 | 0:00:00 Starten0:00:42 13 Onlinealgorithmen0:05:35 Examples0:08:09 Competitive analysis0:09:19 A typical online problem: ski rental0:11:31 Upper bound for ski rental0:14:33 Lower bound for ski rental0:18:07 Paging0:20:16 Definitions0:21:49 Paging algorithms0:25:11 Longest Forward Distance is optimal0:27:34 Using the claim0:29:01 Proof the clai…

21 | 0:00:00 Starten0:00:07 Burrows-Wheeler-Transformation0:12:23 Datenkompression0:18:42 Verlustfreie Textkompression0:30:39 Wörterbuchbasierte Textkompression0:33:02 Lempel-Ziv Kompression0:33:45 Naive Lempel-Ziv Kompression0:43:15 Naive LZ Dekompression0:45:08 LZ Beispiel0:45:16 LZ-Verfeinerung0:46:37 Begin Übung 110:48:29 Suche mit Suffix-Array…

20 | 0:00:00 Starten0:00:07 Wiederholung: Asymmetrisches Divide-and-Conquer0:03:50 Implementierung0:06:04 Verallgemeinerung: Differenzenüberdeckungen0:10:34 Verbesserungen / Verallgemeinerungen0:11:23 Suffixtabellenkonstruktion: Zusammenfassung0:12:00 Suche in Suffix Arrays0:14:13 LCP-Array0:15:56 Beispiel0:32:42 LCP-Array: Berechnung0:39:53 Suffix…

19 | 0:00:00 Starten0:00:09 Wiederholung: Suffix Tree und Suffix Array0:02:28 Kapitel 8 - Stringology (Zeichenkettenalgorithmen)0:03:37 Etwas ""Stringology""-Notation0:05:26 Suffixe Sortieren0:05:59 Anwendungen0:07:05 Volltextsuche0:07:28 Suffix-Baum0:08:33 Alphabet-Modell0:09:24 Geordnetes --> ganzzahliges Alphabet0:10:30 Verallgemeinerung: Lexiko…

18 | 0:00:00 Starten0:00:07 Stringology (Zeichenkettenalgorithmen)0:00:59 Top 10 query completion (Suchvolumina)0:04:18 Weitere Anwendungen0:10:19 Naives Pattern Matching0:17:29 Besserer Algorithmus0:27:53 Fallanalyse Palindrome0:41:09 Berechnung der Verschiebetabelle1:00:26 Multi Key Quicksort for Strings1:11:00 Matching von k pattern gegen einen …

17 | 0:00:00 Starten0:00:07 Übung 9 – Algorithmen 20:00:27 Themenübersicht0:02:21 Parallelverabeitung0:06:11 PRAM0:08:27 Verbindungsnetzwerke0:14:26 Anwendungen0:33:58 Parallele Programmierung0:35:53 Übung 8 – Algorithmen 20:36:07 Anwendungen0:38:33 Themenübersicht0:40:20 Approximationsalgorithmen1:06:46 Parametrisierte Algorithmen…

16 | 0:00:00 Starten0:00:09 Wiederholung0:11:01 9 Fixed-Parameter-Algorithmen0:30:14 10 Parallele Algorithmen0:35:16 10.1 Modell Nachrichtengekoppelte Parallelrechner0:46:53 10.2 Beispiel: Assoziative Operationen (=Reduktion)0:59:16 Präfixsummen1:04:46 10.3 SortierenVon Dr. rer. nat. Christian Schulz

15 | 0:00:00 Starten0:00:09 Wiederholung: Job Scheduling0:03:14 Wiederholung: List Scheduling0:10:08 Wiederholung: TSP0:13:43 Wiederholung: Metric TSP0:19:21 Pseudopolynomielle Algorithmen0:22:08 Rucksack Problem0:25:21 Dynamic Programming0:33:09 Fully Polynomial Time Approximation Scheme0:34:50 Beispielschranken0:36:22 FPTAS für Knapsack0:47:18 Le…

14 | 0:00:00 Starten0:00:10 Wiederholung0:09:49 8 Approximationsalgorithmen0:12:39 Job Scheduling0:26:47 Approximationsfaktor0:38:22 Traveling Salesman Problem0:51:22 Metric TSP0:53:54 Euler-Tour/Kreis0:59:01 AlgorithmusVon Dr. rer. nat. Christian Schulz

12 | 0:00:00 Starten0:01:10 Wiederholung0:17:28 Randomisierter Algorithmus0:33:34 Barabasi Albert Graph Generation0:52:54 7 Externe Algorithmen0:53:01 7.1 Das Sekundärspeichermodell1:07:02 7.2 Externe Stabel1:11:38 Run Formation1:13:03 Sortieren durch Externes Binäres MischenVon Prof. Dr. Peter Sanders