Parallele Algorithmen, Vorlesung, WS17/18
…
continue reading
Algorithmen 1, SS2016, Vorlesung
…
continue reading
Algorithmen 1, SS2013, Vorlesung
…
continue reading
Algorithmen 1, SS2017, Vorlesung
…
continue reading
…
continue reading
lgorithmen 2, WS2016/17, Vorlesung
…
continue reading
1
13: Parallele Algorithmen, Vorlesung, WS 2017/18, 29.01.2018
1:26:31
1:26:31
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:26:31
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…
…
continue reading
1
12: Parallele Algorithmen, Vorlesung, WS 2017/18, 22.01.2018
1:29:53
1:29:53
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:29:53
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…
…
continue reading
1
11: Parallele Algorithmen, Vorlesung, WS 2017/18, 15.01.2018
1:27:27
1:27:27
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:27:27
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…
…
continue reading
1
10: Parallele Algorithmen, Vorlesung, WS 2017/18, 08.01.2018
1:10:09
1:10:09
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:10:09
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 …
…
continue reading
1
09: Parallele Algorithmen, Vorlesung, WS 2017/18, 18.12.2017
1:07:05
1:07:05
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:07:05
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-…
…
continue reading
1
08: Parallele Algorithmen, Vorlesung, WS 2017/18, 11.12.2017
1:29:13
1:29:13
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:29:13
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…
…
continue reading
1
07: Parallele Algorithmen, Vorlesung, WS 2017/18, 04.12.2017
1:32:50
1:32:50
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:32:50
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…
…
continue reading
1
06: Parallele Algorithmen, Vorlesung, WS 2017/18, 27.11.2017
1:31:29
1:31:29
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:31:29
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…
…
continue reading
1
05: Parallele Algorithmen, Vorlesung, WS 2017/18, 20.11.2017
1:35:03
1:35:03
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:35:03
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…
…
continue reading
1
04: Parallele Algorithmen, Vorlesung, WS 2017/18, 13.11.2017
54:01
54:01
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
54:01
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…
…
continue reading
1
02: Parallele Algorithmen,Vorlesung, WS 2017/18, 23.10.2017
1:24:30
1:24:30
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:24:30
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…
…
continue reading
1
03: Parallele Algorithmen,Vorlesung, WS 2017/18, 06.11.2017
1:27:23
1:27:23
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:27:23
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…
…
continue reading
1
01: Parallele Algorithmen, Vorlesung, WS 2017/18, 16.10.2017
1:09:28
1:09:28
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:09:28
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…
…
continue reading
1
23: Algorithmen 1, Vorlesung, SS 2017, 24.07.2017
1:22:51
1:22:51
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:22:51
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:…
…
continue reading
1
22: Algorithmen 1, Vorlesung, SS 2017, 17.07.2017
35:55
35:55
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
35: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…
…
continue reading
1
21: Algorithmen 1, Übung, SS 2017, 12.07.2017
55:29
55:29
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
55:29
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…
…
continue reading
1
20: Algorithmen 1, Vorlesung, SS 2017, 10.07.2017
1:12:32
1:12:32
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:12:32
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…
…
continue reading
1
19: Algorithmen 1, Vorlesung und Übung, SS 2017, 05.07.2017
1:14:44
1:14:44
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:14:44
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…
…
continue reading
1
18: Algorithmen 1, Vorlesung, SS 2017, 03.07.2017
1:10:32
1:10:32
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:10:32
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 ZusammenfassungDoor Prof. Dr. Jörn Müller-Quade
…
continue reading
1
17: Algorithmen 1, Vorlesung und Übung, SS 2017, 28.06.2017
1:02:08
1:02:08
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:02:08
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…
…
continue reading
1
16: Algorithmen 1, Vorlesung, SS 2017, 26.06.2017
1:04:41
1:04:41
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:04:41
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…
…
continue reading
1
15: Algorithmen 1, Vorlesung, SS 2017, 19.06.2017
1:00:41
1:00:41
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:00:41
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…
…
continue reading
1
14: Algorithmen 1, Vorlesung, SS 2017, 14.06.2017
1:25:31
1:25:31
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:25:31
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…
…
continue reading
1
13: Algorithmen 1, Vorlesung, SS 2017, 12.06.2017
1:17:11
1:17:11
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:17:11
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…
…
continue reading
1
12: Algorithmen 1, Vorlesung und Übung, SS 2017, 07.06.2017
1:25:52
1:25:52
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:25:52
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…
…
continue reading
1
11: Algorithmen 1, Vorlesung und Übung, SS 2017, 31.05.2017
1:15:43
1:15:43
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:15:43
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…
…
continue reading
1
10: Algorithmen 1, Vorlesung, SS 2017, 29.05.2017
1:23:04
1:23:04
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:23:04
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…
…
continue reading
1
09: Algorithmen 1, Vorlesung, SS 2017, 24.05.2017
1:26:18
1:26:18
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:26:18
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…
…
continue reading
1
08: Algorithmen 1, Vorlesung, SS 2017, 22.05.2017
1:00:40
1:00:40
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:00:40
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 VersuchDoor Prof. Dr. Jörn Müller-Quade
…
continue reading
1
07: Algorithmen 1, Vorlesung und Übung, SS 2017, 17.05.2017
1:19:15
1:19:15
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:19:15
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…
…
continue reading
1
06: Algorithmen 1, Vorlesung, SS 2017, 15.05.2017
1:26:01
1:26:01
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:26:01
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 …
…
continue reading
1
05: Algorithmen 1, Vorlesung und Übung, SS 2017, 10.05.2017
1:14:06
1:14:06
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:14:06
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 …
…
continue reading
1
03: Algorithmen 1, Übung, SS 2017, 03.05.2017
1:19:18
1:19:18
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:19:18
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…
…
continue reading
1
04: Algorithmen 1, Vorlesung, SS 2017, 08.05.2017
1:17:42
1:17:42
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:17:42
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…
…
continue reading
1
02: Algorithmen 1, Vorlesung, SS 2017, 26.04.2017, 02
1:16:52
1:16:52
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:16:52
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…
…
continue reading
1
01: Algorithmen 1, Vorlesung, SS 2017, 24.04.2017, 01
1:07:33
1:07:33
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:07:33
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 07.02.2017, 26
37:01
37:01
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
37:01
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…
…
continue reading
1
Algorithmen II, Vorlesung und Übung, WS 2016/17, 31.01.2017, 25
1:11:59
1:11:59
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:11:59
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 25.01.2017, 24
1:24:12
1:24:12
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:24:12
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…
…
continue reading
1
Algorithmen II, Übung und Vorlesung, WS 2016/17, 24.01.2017, 23
1:25:15
1:25:15
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:25:15
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22
1:17:17
1:17:17
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:17:17
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…
…
continue reading
1
Algorithmen II, Vorlesung und Übung, WS 2016/17, 11.01.2017, 21
1:27:55
1:27:55
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:27:55
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 10.01.2017, 20
1:28:14
1:28:14
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:28:14
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…
…
continue reading
1
Algorithmen II, Vorlesung und Übung, WS 2016/17, 21.12.2016, 19
1:31:49
1:31:49
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:31:49
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 20.12.2016, 18
1:32:06
1:32:06
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:32:06
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 …
…
continue reading
1
Algorithmen II, Übung, WS 2016/17, 14.12.2016, 17
1:17:41
1:17:41
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:17:41
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 13.12.2016, 16
1:18:37
1:18:37
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:18:37
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 SortierenDoor Dr. rer. nat. Christian Schulz
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 07.12.2016, 15
1:09:47
1:09:47
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:09:47
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…
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 06.12.2016, 14
1:03:21
1:03:21
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:03:21
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 AlgorithmusDoor Dr. rer. nat. Christian Schulz
…
continue reading
1
Algorithmen II, Vorlesung, WS 2016/17, 29.11.2016, 12
1:14:48
1:14:48
Later Afspelen
Later Afspelen
Lijsten
Vind ik leuk
Leuk
1:14:48
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 MischenDoor Prof. Dr. Peter Sanders
…
continue reading