Algorithmen สาธารณะ
[search 0]
เพิ่มเติม

ดาวน์โหลดแอปเลย!

show episodes
 
Loading …
show series
 
26 | 0:00:00 Starten0:00:09 Seminar: Proofs from the book0:04:48 Theses 2018: External, Parallel, and Distributed Sorting0:11:12 Graph Generators0:17:23 High Quality Hypergraph Partitioning0:23:59 Kernbildung in der Praxis0:38:53 Start Vorlesung0:40:33 Randomisierte Algorithmen0:43:44 Approximationsalgorithmen0:49:41 Online Algorithmen…
 
24 | 0:00:00 Starten0:00:09 highest level preflow push0:06:51 Example0:13:50 Proof of Lemma 120:17:30 Claims0:28:47 Heuristic Improvements0:33:32 Experimental results0:33:39 Timings: Random Graphs0:36:16 Timings0:36:40 Asymptotics0:36:43 Zusammenfassung Flows und Matchings0:49:53 Sortieren durch Mehrwege-Mischen0:50:00 Das Sekundärspeichermodell0:5…
 
25 | 0:00:00 Starten0:00:15 Highest Level Preflow Push 0:00:55 Claims0:01:07 Proof of Lemma 12 0:02:32 Claims 0:12:13 Anfang der Übung 0:12:27 Themenübersicht 0:13:08 Preflow-push Algorithmus0:20:44 FIFO preflow-push Algorithmus 0:42:37 Matching0:44:31 Bipartite-Matching 0:46:40 Speichermodell 0:48:26 Latenzen0:49:47 I/O-efffizientes Design0:51:12 …
 
23 | 0:00:00 Starten0:07:03 Flüsse und Ford Fulkerson0:08:39 Max Flow - Min Cut0:12:42 Dinitz: Distanz Label0:14:37 Dinitz: Schichtgraph0:15:45 Dinitz: Blockierender Fluss0:17:21 Dinitz: Blockierender Fluss Operationen0:20:36 Dinitz: Kosten pro Blockierender Fluss0:24:14 Dinitz: Laufzeit0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network0:30:24…
 
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…
 
22 | 0:00:00 Starten0:00:09 Algorithms 1956-now0:00:47 Residual Graph0:02:25 A Bad Example for Ford Fulkerson0:03:19 Blocking Flows0:04:57 Dinitz Algorithm0:06:11 Blocking Flows Analysis 0:07:39 Dinitz Analysis0:17:14 Matching0:20:28 Maximum Cardinality Bipartite Matching0:23:44 Disadvantage of augmenting paths algorithms0:45:52 Übung 110:46:25 Kür…
 
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…
 
21 | 0:00:00 Starten0:00:18 Maximum Flows and Matchings0:00:37 Definitions: Network0:02:23 Flows0:06:45 Applications0:07:19 Applications in our Group0:14:39 Option 1: linear programming0:16:09 Algorithms 1956-now0:19:49 Example0:24:55 Residual Graph0:31:33 Ford Fulkerson Algorithm0:43:36 Übung0:44:35 SCC0:55:06 Floyd Warshall: SCC als Speedup Techn…
 
0 | 0:00:00 Starten0:00:18 Anwendungen von DFS0:05:13 Tiefensuchschema für G= (V,E)0:09:29 Starke Zusammenhangskomponenten0:12:53 SCCs generischer Algorithmus0:20:12 Ziel: Effizienter Algorithmus0:27:20 Invarianten0:39:53 Invarianten von Gc0:53:47 traverseNonTreeEdge(v,w)0:56:47 Backtrack(u, v)1:01:52 Beispiel1:11:28 Zusammenfassung: SCC Berechnung…
 
19 | 0:00:00 Starten0:00:09 Erinnerung0:21:19 Radix-Heaps0:35:25 Radix-Heap-Invariante0:40:45 Radix Heap: deleteMin0:45:28 Kosten der deleteMin-Operationen1:07:04 all-pair-shortest-path (APSP)1:23:03 Definition der Potentialeโดย Dr. rer. nat. Simon Gog
 
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 …
 
18 | 0:00:00 Starten0:00:09 Fortgeschrittene Graphenalgorithmen0:04:34 Allgemeine Definition0:06:17 Kante relaxieren0:07:11 Dijkstra's Agorithmus0:08:40 Beispiel0:09:00 Laufzeit0:14:55 Lineare Laufzeit für dichte Graphen0:26:30 Präfixminima einer Zufallsfolge0:27:32 Monotone ganzzahlige Prioritätslisten0:31:28 Bucket-Queue0:34:22 Operation0:35:17 L…
 
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-…
 
17 | 0:00:00 Starten0:00:46 Aufgabenvarianten0:01:16 Verteilte Eigenschaften0:01:30 Theoretiker-Quicksort0:06:08 Fortgeschrittene Datenstrukturen0:10:27 Adressierbare Prioritätslisten0:34:55 Adressierbare Prioritätslisten: Anwendungen0:38:27 Grundlegende Datenstruktur 0:39:29 Wälder bearbeiten0:40:59 Pairing Heaps (Paarungs-Haufen??)0:46:39 Pairing…
 
16 | 0:00:00 Starten0:00:09 Parallele Reduktion: Algorithmus0:05:38 Analyse paralleler Programme0:14:10 Parallele Präfixsummen0:44:36 Übung 70:45:28 Expertenauswahl0:49:41 Parallelverarbeitung0:52:09 PRAM0:54:56 Verbindungsnetzwerke1:01:33 Nachrichtenaustausch: Pipelining1:06:31 Anwendungen1:20:13 Parallele Programmierung…
 
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…
 
15 | 0:00:00 Starten0:00:33 Überblick0:01:07 Problemstellung0:04:06 Auswahl von Experten0:05:07 Auswahl von Experten: der deterministische Weighted Majority Algorithm (wma)0:07:49 Qualität von WMA 0:09:31 Beweis0:16:48 Verallgemeinerte Problemstellung0:18:17 Randomisiert: randWMA0:21:13 Qualität von randWMA0:23:06 Beweis0:31:57 Warum Parallelverarb…
 
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…
 
14 | 0:00:00 Starten0:01:57 LRU - Beispiel0:05:27 LRU ist K- Kompetitiv0:06:22 LRU ist K-Kompetitive – Beweisskizze0:15:44 Resource Augmentation: (h,k)-Seitenwechsel0:24:12 Randomisiert0:25:14 Randomisierte Onlinealgorithmen0:26:09 Widersacher: verschieden miese Typen0:30:04 Wettbewerbsfaktor0:31:52 RANDMARK Algorithmus0:35:50 Beweis0:55:17 Übung 6…
 
13 | 0:00:00 Starten0:02:50 Eine Reihe von Beispiele0:05:39 Beispiel Job-Scheduling0:07:07 Beispiel Skiausleihe0:09:30 Speicherverwaltung 0:12:04 Auswahl von Experten0:14:23 Beispiel Selbstorganisierende Datenstrukturen0:15:12 Online-Algorithmus0:19:55 Competitive Analysis0:24:45 Wettbewerbsfaktor0:27:53 Strikte c-Kompetitivität 0:30:07 Wettbewerbs…
 
12 | 0:00:00 Starten0:00:09 Orthogonal range searching0:01:01 Orthogonal range searching - 1D0:07:03 Orthogonal range searching - 2D0:17:40 Wavelet Tree Dominance Reporting Query0:17:54 Reduktion auf 1..n x 1..n0:18:18 Beispiel0:19:54 Wavelet Tree0:22:18 Beispiel0:24:30 Wavelet Tree Counting Query0:27:01 Wavelet Tree Dominance Counting Query0:32:57…
 
11 | 0:00:00 Starten0:06:23 Typische Fragestellungen0:15:56 Streckenschnitt: Naiver Algorithmus0:19:04 Idee: Plane-Sweep-Algorithmus0:24:57 Plane-Sweep für orth. Streckenschnitt0:29:03 Verallgemeinerung - Grundidee0:40:56 Verallgemeinerung - Beispiel0:49:50 Überlappungen finden0:52:30 2D Konvexe Hülle0:56:53 Graham's Scan1:02:07 Kleinste einschließ…
 
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…
 
10 | 0:00:00 Starten0:00:21 Wavelet Tree Example: Calculate Rank0:09:48 Huffman-shaped Wavelet Tree0:12:42 Practical Performance of FM-Index0:14:54 Succinct Data Structures0:17:09 Succinct representation of trees0:19:34 Child operation in detail0:22:09 Succinct representation of trees (2)0:29:34 LOUDS-level order unary degree sequence0:44:15 Anfang…
 
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…
 
09 | 0:00:00 Starten0:00:18 Range minimum queries (RMQs)0:00:43 Overview0:01:05 O(n), Olog(n)-solution 10:01:18 O(nlogn), O solution 20:01:38 O(nlog(logn)), O(1) solution0:02:17 O(n),O(1) solution0:02:33 LCA & +1RMQ0:02:51 O(n),O(1) solution0:08:08 LCA& +1RQM0:16:49 (O(n),O(1)) solution (4n+o(n) bits)0:34:19 (O(n),O(1)) solution (2n+0(n) bits )0:47…
 
08 | 0:00:00 Starten0:00:34 Verlustfreie Textkompression0:01:25 Theorie verlustfreier Textkompression0:10:57 Wörterbuchbasierte Textkompression0:12:58 Lempel-Ziv Kompresssion (LZ)0:17:44 Naive LZ Dekompression0:20:15 LZ- Verfeinerungen0:21:39 LCP zwischen beliebigen Suffixen0:23:44 Range minimum queries (RMQs)0:25:17 Overview0:26:08 O(n), Olog(n)- …
 
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…
 
07 | 0:00:00 Starten0:00:22 Suffix-Baum0:01:20 Alphabet-Modell0:02:41 Geordnetes ganzzahliges Alphabet0:04:39 Verallgemeinerung: Lexikographische Namen0:05:31 Ein erster Teile-und-Herrsche-Ansatz0:13:30 Asymmetrisches Divide-and-Conquer0:18:09 Rekursion, Beispiel0:25:39 Least Significant Digit First Radix Sort0:28:03 Stabiles Ganzzahliges Sortieren…
 
06 | 0:00:00 Starten0:00:32 4 Stringology (Zeichenkettenalgorithmen)0:04:16 Strings Sortieren0:15:40 Strings Sortieren - Laufzeitanalyse0:18:27 Naives Pattern Matching0:55:49 Volltextsuche von langsam bis Superschnell1:04:37 Suffixtabellen1:05:37 Etwas ""Stringology""-Notation1:07:03 Suffixe Sortieren1:14:18 Volltextsuche1:14:38 Suffix-Baum…
 
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…
 
05 | 0:00:00 Starten0:00:34 Turing-Reduzierbarkeit0:02:47 Pseudopolynomielle Laufzeit0:05:58 Zwei kleine Warnungen0:07:55 KNAPSACK Suchproblem0:10:22 KNAPSACK: Codierungen der Eingabe0:11:47 Schwere des KNAPSACK Suchproblems0:12:41 KNAPSACK: pseudopolynomielle Laufzeit0:22:08 Polynomielle Approximationsschema0:25:56 PTAS versus FPTAS0:26:34 Von pse…
 
04 | 0:00:00 Starten0:01:07 Suchprobleme0:04:15 Approximation bei Suchprobleme0:07:10 Approximation bei Zählprobleme0:08:51 Job Scheduling: Aufgabenstellung0:13:14 Naheliegender Algorithmus: listScheduling0:20:19 Eigenschaften des Algorithmus0:26:55 Approxiamtionsfaktor0:28:43 Eigenschaften des Algorithmus (2)0:34:43 Erinnerung: TSP-Suchproblem0:37…
 
03 | 0:00:00 Starten0:00:10 Kapitel: Randomisierte Algorithmen0:00:45 Überblick0:02:44 Erdos-Renyi-Zufallsgraphen0:04:59 ER-Graphen: einfache Beobachtungen0:11:05 Manchmal interessieren sehr große n und asymptotische Eigenschaften0:15:21 ER-Graphen:Durschmesser <=20:21:51 Zusammenhangskomponenten0:23:15 Erwartet konstanter Knotengrad0:24:21 Andere …
 
02 | 0:00:00 Starten0:01:08 Erinnerung an W-Theorie0:02:22 Randomisierter Quicksort0:04:34 randQS: Anzahl Vergleiche0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt.0:28:25 Chernoff-Schranken0:29:04 Einfache Schranken0:32:19 Chernoff-Schranken0:38:03 Chernoff-Schranken: Beweis von Teil 10:44:26 Chernoff-Schranken: Verienfachungen0:45:47 Chernoff-Sch…
 
01 | 0:00:00 Starten0:00:10 Kapitel: Randomisierte Algorithmen0:01:10 Überblick0:01:38 Sichtweisen für randomisierte Algorithmen0:03:33 Fundamentale Änderung0:04:03 Beispiel: Randomisierter Quicksort0:05:32 Zufallsvariablen überall0:05:49 Errinerung an W-Theorie0:09:32 Standardbeispiel: Würfeln0:15:26 Algorithmen mit unbekannter Laufzeit0:16:25 Alg…
 
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 Zusammenfassungโดย 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…
 
Loading …

คู่มืออ้างอิงด่วน

Google login Twitter login Classic login