PODCAST

Algorithmen 2, Vorlesung, WS17/18

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

01:06:01

26: Algorithmen 2, Vorlesung, WS 2017/18, 06.02.2018

Algorithmen 2, Vorlesung, WS17/18 ·

2018/02/08

26 | 0:00:00 Starten 0:00:09 Seminar: Proofs from the book 0:04:48 Theses 2018: External, Parallel, and Distributed Sorting 0:11:12 Graph Generators 0:17:23 High Quality Hypergraph Partitioning 0:23:59 Kernbildung in der Praxis 0:38:53 Start Vorlesung 0:40:33 Randomisierte Algorithmen 0:43:44 Approximationsalgorithmen 0:49:41 Online Algorithmen

01:28:02

24: Algorithmen 2, Vorlesung, WS 2017/18, 30.01.2018

Algorithmen 2, Vorlesung, WS17/18 ·

2018/02/07

24 | 0:00:00 Starten 0:00:09 highest level preflow push 0:06:51 Example 0:13:50 Proof of Lemma 12 0:17:30 Claims 0:28:47 Heuristic Improvements 0:33:32 Experimental results 0:33:39 Timings: Random Graphs 0:36:16 Timings 0:36:40 Asymptotics 0:36:43 Zusammenfassung Flows und Matchings 0:49:53 Sortieren durch Mehrwege-Mischen 0:50:00 Das Sekundärspeichermodell 0:51:59 Externe Stapel 1:08:30 Externes (binäres) Mischen 1:08:56 Run Formation 1:10:11 Sortieren durch Externes Binäres Mischen 1:12:01

01:27:53

25: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2018/02/06

25 | 0:00:00 Starten 0:00:15 Highest Level Preflow Push 0:00:55 Claims 0: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 Algorithmus 0:20:44 FIFO preflow-push Algorithmus 0:42:37 Matching 0:44:31 Bipartite-Matching 0:46:40 Speichermodell 0:48:26 Latenzen 0:49:47 I/O-efffizientes Design 0:51:12 Blockgrößen 0:55:33 Externes Sortieren 1:02:00 Strings Sortieren 1:02:56 Stringology (Zeichenkettenalgorithmen) 1:05:15 Suche in Suffix

01:26:58

23: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2018/02/05

23 | 0:00:00 Starten 0:07:03 Flüsse und Ford Fulkerson 0:08:39 Max Flow - Min Cut 0:12:42 Dinitz: Distanz Label 0:14:37 Dinitz: Schichtgraph 0:15:45 Dinitz: Blockierender Fluss 0:17:21 Dinitz: Blockierender Fluss Operationen 0:20:36 Dinitz: Kosten pro Blockierender Fluss 0:24:14 Dinitz: Laufzeit 0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network 0:30:24 Maximum Cardinality Bipartite Matching 0:31:35 Preflow-Push Algorithms 0:34:00 Level Function 0:36:49 Procedure genericPreflowPush 1:21:53

01:25:00

22: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2018/01/25

22 | 0:00:00 Starten 0:00:09 Algorithms 1956-now 0:00:47 Residual Graph 0:02:25 A Bad Example for Ford Fulkerson 0:03:19 Blocking Flows 0:04:57 Dinitz Algorithm 0:06:11 Blocking Flows Analysis 0:07:39 Dinitz Analysis 0:17:14 Matching 0:20:28 Maximum Cardinality Bipartite Matching 0:23:44 Disadvantage of augmenting paths algorithms 0:45:52 Übung 11 0:46:25 Kürzeste-Wege-Suche 0:48:11 Suche in Graphen 0:51:22 Dijikstras Algorithmus 0:53:19 Bidirectionale Suche 1:00:03 A*-Suche

01:03:41

21: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2018/01/18

21 | 0:00:00 Starten 0:00:18 Maximum Flows and Matchings 0:00:37 Definitions: Network 0:02:23 Flows 0:06:45 Applications 0:07:19 Applications in our Group 0:14:39 Option 1: linear programming 0:16:09 Algorithms 1956-now 0:19:49 Example 0:24:55 Residual Graph 0:31:33 Ford Fulkerson Algorithm 0:43:36 Übung 0:44:35 SCC 0:55:06 Floyd Warshall: SCC als Speedup Technik

01:15:57

20: Algorithmen 2, Vorlesung, WS 2017/18, 15.01.2018

Algorithmen 2, Vorlesung, WS17/18 ·

2018/01/15

0 | 0:00:00 Starten 0:00:18 Anwendungen von DFS 0:05:13 Tiefensuchschema für G= (V,E) 0:09:29 Starke Zusammenhangskomponenten 0:12:53 SCCs generischer Algorithmus 0:20:12 Ziel: Effizienter Algorithmus 0:27:20 Invarianten 0:39:53 Invarianten von Gc 0:53:47 traverseNonTreeEdge(v,w) 0:56:47 Backtrack(u, v) 1:01:52 Beispiel 1:11:28 Zusammenfassung: SCC Berechnung 1:14:09 Mehr DFS-basierte Linearzeitalgorithmen

01:27:43

19: Algorithmen 2, Vorlesung, WS 2017/18, 08.01.2018

Algorithmen 2, Vorlesung, WS17/18 ·

2018/01/11

19 | 0:00:00 Starten 0:00:09 Erinnerung 0:21:19 Radix-Heaps 0:35:25 Radix-Heap-Invariante 0:40:45 Radix Heap: deleteMin 0:45:28 Kosten der deleteMin-Operationen 1:07:04 all-pair-shortest-path (APSP) 1:23:03 Definition der Potentiale

01:04:07

18: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2017/12/22

18 | 0:00:00 Starten 0:00:09 Fortgeschrittene Graphenalgorithmen 0:04:34 Allgemeine Definition 0:06:17 Kante relaxieren 0:07:11 Dijkstra's Agorithmus 0:08:40 Beispiel 0:09:00 Laufzeit 0:14:55 Lineare Laufzeit für dichte Graphen 0:26:30 Präfixminima einer Zufallsfolge 0:27:32 Monotone ganzzahlige Prioritätslisten 0:31:28 Bucket-Queue 0:34:22 Operation 0:35:17 Laufzeit Dijkstra mit Bucket-Queues 0:36:35 Übung8 0:36:41 Amortisierte Analyse 0:39:57 Legende 0:41:59 Fibonacci Heaps - Insert 0:44:09

01:27:13

17: Algorithmen 2, Vorlesung, WS 2017/18, 18.12.2017

Algorithmen 2, Vorlesung, WS17/18 ·

2017/12/19

17 | 0:00:00 Starten 0:00:46 Aufgabenvarianten 0:01:16 Verteilte Eigenschaften 0:01:30 Theoretiker-Quicksort 0:06:08 Fortgeschrittene Datenstrukturen 0:10:27 Adressierbare Prioritätslisten 0:34:55 Adressierbare Prioritätslisten: Anwendungen 0:38:27 Grundlegende Datenstruktur 0:39:29 Wälder bearbeiten 0:40:59 Pairing Heaps (Paarungs-Haufen??) 0:46:39 Pairing Heaps - Repräsentationen 0:48:35 Pairing Heaps - Analyse 0:49:51 Fibonacci Heaps 0:53:27 Repräsentation 0:54:09 deleteMin mit

01:23:18

16: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2017/12/14

16 | 0:00:00 Starten 0:00:09 Parallele Reduktion: Algorithmus 0:05:38 Analyse paralleler Programme 0:14:10 Parallele Präfixsummen 0:44:36 Übung 7 0:45:28 Expertenauswahl 0:49:41 Parallelverarbeitung 0:52:09 PRAM 0:54:56 Verbindungsnetzwerke 1:01:33 Nachrichtenaustausch: Pipelining 1:06:31 Anwendungen 1:20:13 Parallele Programmierung

01:24:59

15: Algorithmen 2, Vorlesung, WS 2017/18, 11.12.2017

Algorithmen 2, Vorlesung, WS17/18 ·

2017/12/11

15 | 0:00:00 Starten 0:00:33 Überblick 0:01:07 Problemstellung 0:04:06 Auswahl von Experten 0:05:07 Auswahl von Experten: der deterministische Weighted Majority Algorithm (wma) 0:07:49 Qualität von WMA 0:09:31 Beweis 0:16:48 Verallgemeinerte Problemstellung 0:18:17 Randomisiert: randWMA 0:21:13 Qualität von randWMA 0:23:06 Beweis 0:31:57 Warum Parallelverarbeitung? 0:42:17 Verschiede Modelle für Parallelverarbeitung 0:43:44 Nachrichtengekoppelter Parallelrechner 0:45:29 Parallelrechner mit

01:30:21

14: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2017/12/07

14 | 0:00:00 Starten 0:01:57 LRU - Beispiel 0:05:27 LRU ist K- Kompetitiv 0:06:22 LRU ist K-Kompetitive – Beweisskizze 0:15:44 Resource Augmentation: (h,k)-Seitenwechsel 0:24:12 Randomisiert 0:25:14 Randomisierte Onlinealgorithmen 0:26:09 Widersacher: verschieden miese Typen 0:30:04 Wettbewerbsfaktor 0:31:52 RANDMARK Algorithmus 0:35:50 Beweis 0:55:17 Übung 6 0:55:45 Online Algorithmen

01:23:45

13: Algorithmen 2, Vorlesung, WS 2017/18, 04.12.2017

Algorithmen 2, Vorlesung, WS17/18 ·

2017/12/05

13 | 0:00:00 Starten 0:02:50 Eine Reihe von Beispiele 0:05:39 Beispiel Job-Scheduling 0:07:07 Beispiel Skiausleihe 0:09:30 Speicherverwaltung 0:12:04 Auswahl von Experten 0:14:23 Beispiel Selbstorganisierende Datenstrukturen 0:15:12 Online-Algorithmus 0:19:55 Competitive Analysis 0:24:45 Wettbewerbsfaktor 0:27:53 Strikte c-Kompetitivität 0:30:07 Wettbewerbsfaktor und strikte Kompetitivität 0:37:13 Nicht-strikte c-Kompetitivität 0:43:36 ListScheduling ist (fast) ein Onlinealgorithmus 0:46:48

01:23:38

12: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2017/11/30

12 | 0:00:00 Starten 0:00:09 Orthogonal range searching 0:01:01 Orthogonal range searching - 1D 0:07:03 Orthogonal range searching - 2D 0:17:40 Wavelet Tree Dominance Reporting Query 0:17:54 Reduktion auf 1..n x 1..n 0:18:18 Beispiel 0:19:54 Wavelet Tree 0:22:18 Beispiel 0:24:30 Wavelet Tree Counting Query 0:27:01 Wavelet Tree Dominance Counting Query 0:32:57 Beispiel 0:34:15 Analyse 0:34:57 Wavelet Tree Dominance Reporting Query 0:40:43 Analyse 0:42:29 Allgemeine Reporting Query 0:44:54 Übung

01:28:23

11: Algorithmen 2, Vorlesung, WS 2017/18, 27.11.2017

Algorithmen 2, Vorlesung, WS17/18 ·

2017/11/30

11 | 0:00:00 Starten 0:06:23 Typische Fragestellungen 0:15:56 Streckenschnitt: Naiver Algorithmus 0:19:04 Idee: Plane-Sweep-Algorithmus 0:24:57 Plane-Sweep für orth. Streckenschnitt 0:29:03 Verallgemeinerung - Grundidee 0:40:56 Verallgemeinerung - Beispiel 0:49:50 Überlappungen finden 0:52:30 2D Konvexe Hülle 0:56:53 Graham's Scan 1:02:07 Kleinste einschließende Kugel 1:19:40 2D Bereichssuche (range research) 1:25:45 Reduktion auf 1..n x 1..n

01:16:51

10: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2017/11/28

10 | 0:00:00 Starten 0:00:21 Wavelet Tree Example: Calculate Rank 0:09:48 Huffman-shaped Wavelet Tree 0:12:42 Practical Performance of FM-Index 0:14:54 Succinct Data Structures 0:17:09 Succinct representation of trees 0:19:34 Child operation in detail 0:22:09 Succinct representation of trees (2) 0:29:34 LOUDS-level order unary degree sequence 0:44:15 Anfang der Übung 0:44:30 Today topics 0:44:59 Select in constant time: Step 1 0:47:49 Select in constant time: Step 2 0:49:33 Select in constant

01:29:31

09: Algorithmen 2, Vorlesung, WS 2017/18, 20.11.2017

Algorithmen 2, Vorlesung, WS17/18 ·

2017/11/21

09 | 0:00:00 Starten 0:00:18 Range minimum queries (RMQs) 0:00:43 Overview 0:01:05 O(n), Olog(n)-solution 1 0:01:18 O(nlogn), O solution 2 0:01:38 O(nlog(logn)), O(1) solution 0:02:17 O(n),O(1) solution 0:02:33 LCA & +1RMQ 0:02:51 O(n),O(1) solution 0:08:08 LCA& +1RQM 0: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:12 Burrows-Wheeler-Transformation: Einführung 0:48:52 Wiederholung: Suffix-Array 0:49:24 Transformation 0:52:22

01:18:27

08: Algorithmen 2, Vorlesung und Übung, WS 2017/18,...

Algorithmen 2, Vorlesung, WS17/18 ·

2017/11/20

08 | 0:00:00 Starten 0:00:34 Verlustfreie Textkompression 0:01:25 Theorie verlustfreier Textkompression 0:10:57 Wörterbuchbasierte Textkompression 0:12:58 Lempel-Ziv Kompresssion (LZ) 0:17:44 Naive LZ Dekompression 0:20:15 LZ- Verfeinerungen 0:21:39 LCP zwischen beliebigen Suffixen 0:23:44 Range minimum queries (RMQs) 0:25:17 Overview 0:26:08 O(n), Olog(n)- solution 0:30:13 O(nlog(n)), O(1) solution 2 0:40:07 Themenübersicht 0:40:31 In-place Multikey Quicksort 0:50:59 Suche mit

01:25:01

07: Algorithmen 2, Vorlesung, WS 2017/18, 13.11.2017

Algorithmen 2, Vorlesung, WS17/18 ·

2017/11/16

07 | 0:00:00 Starten 0:00:22 Suffix-Baum 0:01:20 Alphabet-Modell 0:02:41 Geordnetes ganzzahliges Alphabet 0:04:39 Verallgemeinerung: Lexikographische Namen 0:05:31 Ein erster Teile-und-Herrsche-Ansatz 0:13:30 Asymmetrisches Divide-and-Conquer 0:18:09 Rekursion, Beispiel 0:25:39 Least Significant Digit First Radix Sort 0:28:03 Stabiles Ganzzahliges Sortieren 0:32:09 Rekursions-Beispiel: Einfacher Fall 0:33:53 Sortieren der mod 0 Suffixe 0:39:37 Analyse 0:41:58 Implementierung:

26 results

Algorithmen 2, Vorlesung, WS17/18

All Episodes

Similar Podcasts

Science Talk

Albert Einstein College of Medicine

五分钟心理学

柠檬心理

Daily Facts

Amalia Dupray and Montgomery Jones.

Les dents et dodo

BFMTV

Veterinary Clinical Podcasts

The Royal Veterinary College