PODCAST

Algorithmen 2, Vorlesung, WS19/20

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

01:20:36

28: Algorithmen II, Vorlesung, WS 2019/20, 04.02.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/02/05

28| 0:00:00 Start 0:00:11 Externes binäres Mischen 0:13:06 8 Approximationsalgorithmen 0:26:45 9 Fixed-Parameter-Algorithmen 0:38:52 10 Parallele Algorithmen 0:52:22 11 Stringology 0:56:36 12 Geometrische Algorithmen 1:14:40 13 Onlinealgorithmen

01:07:08

27: Algorithmen II, Vorlesung, WS 2019/20, 03.02.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/02/03

27| 0:00:00 Start 0:03:24 Fortgeschrittene Datenstrukturen 0:06:37 Pairing Heaps 0:15:49 Laufzeit im Durchschnitt 0:21:31 Bucket-Queue 0:37:07 Starke Zusammenhangskomponenten 0:44:05 Zusammenfassung: SCC Berechnung 0:53:28 Residual Graph 1:02:41 Randomisierte Algorithmen

01:23:00

26: Algorithmen II, Vorlesung, WS 2019/20, 28.01.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/02/03

26| 0:00:00 Start 0:02:19 The Document Retrieval Problem 0:03:30 Top-k Document Retrieval 0:04:39 Important Query Types 0:05:51 Inverted Indexes 0:09:13 Suffix Arrays 0:11:10 Warmup: Document Listing 0:14:24 Top-k Retrieval 0:15:21 Example 0:21:58 Example Space Usage from [LG17] 0:24:29 Range Minimum Query 0:25:12 2D-Weighted Range Queries 0:34:43 Range Minimum Query Problem 0:49:25 Comparison with other Implementations 0:50:41 (Hyper)Graph Partitioning 0:51:25 Graphs and Hypergraphs 0:54:48

01:12:48

25: Algorithmen II, Vorlesung, WS 2019/20, 27.01.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/01/27

25| 0:00:00 Start 0:00:54 Datenkompression 0:01:52 Verlustfreie Textkompression 0:03:14 Wörterbuchbasierte Textkompression 0:05:11 Lempel-Ziv Kompression 0:06:22 Beispiel 0:21:16 Burrows Wheeler Transformation 0:47:23 Backward Search 0:57:44 Wavelet Tree Example: Calculate Rank

01:14:42

24: Algorithmen II, Vorlesung, WS 2019/20, 21.01.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/01/23

23| 0:00:00 Start 0:00:09 Suffixtabellenkonstruktion: Zusammenfassung 0:01:49 Suche in Suffix Arrays 0:07:08 LCP-Array 0:27:51 Suffix-Baum aus SA und LCP 0:34:16 Datenkompression 0:36:49 Verlustfreie Textkompression 0:46:48 10.Übung 0:47:28 Themenübersicht 0:47:57 in-place Multikey Quicksort 0:58:11 Suche mit Suffix-Arrays 1:03:55 LCP-Array

01:20:40

23: Algorithmen II, Vorlesung, WS 2019/20, 20.01.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/01/21

23 | 0:00:00 Start 0:00:05 Suffix Array Konstruktionsalgorithmen 0:00:51 SA mit Präfix Verdopplung 0:11:39 Linear Work Suffix Array Construction 0:13:50 SA berechnen 0:17:21 Asymmetrisches Divide-and-Conquer 0:18:38 Rekursion Beispiel 0:34:17 Least Significant Digit First Radix Sort 0:40:22 Implementierung 0:41:42 Verallgemeinerung: Differenzenüberdeckungen 0:46:09 COBS: A Compact Bit-Sliced Signature Index 0:47:28 Motivation / Applications 1:14:27 COBS: Disk Access Pattern

01:23:59

22: Algorithmen II, Vorlesung und Übung, WS 2019/20,...

Algorithmen 2, Vorlesung, WS19/20 ·

2020/01/16

22 | 0:00:00 Start 0:01:50 Volltextsuche von langsam bis schnell 0:03:43 Invertierter Index 0:09:34 Etwas ""Stringology""-Notation 0:11:16 Suffixe Sortieren 0:13:18 Volltextsuche 0:15:22 Suffix-Baum 0:25:08 Alphabet-Modell 0:28:50 Suffix Array Konstruktionsalgorithmen 0:32:47 SA mit Präfix Verdopplung 0:52:33 Beginn Übung 9 0:53:25 Online Algorithmen - Grundlagen 0:59:18 Online Algorithmen - Gütemaß 1:01:12 Beispiel: Ski Rental Problem 1:10:42 Online Algorithmen - Online

01:22:11

21: Algorithmen II, Vorlesung, WS 2019/20, 13.01.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/01/14

21 | 0:00:00 Start 0:01:49 Strings sortieren 0:22:18 Evaluation 0:27:18 Strings sortieren: Multikey Quicksort 0:39:16 Strings sortieren: Algorithmen-Übersicht 0:43:15 Vergleich sequentielle Algorithmen 0:44:51 Naives Pattern Matching 0:51:58 Knuth-Morris-Pratt 1:14:18 Berechnung des Border-Arrays 1:16:48 Volltextsuche von langsam bis superschnell 1:18:35 Invertierter Index

01:21:02

20: Algorithmen II, Vorlesung, WS 2019/20, 07.01.2020

Algorithmen 2, Vorlesung, WS19/20 ·

2020/01/13

20 | 0:00:00 Start 0:01:25 Onlinealgorithmen 0:05:59 Competitive analysis 0:07:29 A typical online problem: ski rental 0:08:55 Upper bound for ski rental 0:10:55 Lower bound for ski rental 0:16:04 Paging 0:19:44 Definitions 0:20:23 Paging algorithms 0:24:41 Longest Forward Distance 0:27:48 Using the claim 0:29:48 Comparison of algorithms 0:35:28 A general lower bound 0:41:28 Resource augmentation 0:42:53 Conservative algorithms 0:44:42 Competitive ratio 0:47:01 Counting the faults of OPT 0:48:57

01:20:25

19: Algorithmen II, Vorlesung und Übung, WS 2019/20,...

Algorithmen 2, Vorlesung, WS19/20 ·

2019/12/19

18 | 0:00:00 Start 0:00:05 Wiederholung 0:15:41 Wavelet Tree Dominance Reporting Query 0:20:49 Laufzeit Analyse 0:21:59 Allgemeine Reporting Query 0:26:51 Bitvektoren 0:31:43 Mehr zu Bitvektoren 0:34:08 Übung 8 0:34:14 Themenübersicht 0:35:11 Geometrische Algorithmen 0:38:01 Geometrische Methoden 0:42:44 Intervall Tree: Konstruktion 0:44:57 Intervall Tree: Schnitt mit Punkt 0:48:25 Bitvektoren: Rank und Select 0:50:27 Bitvektoren: Implementierung von Rank 0:56:09 2D Range Queries: Wavelet

01:19:13

18: Algorithmen II, Vorlesung, WS 2019/20, 16.12.2019

Algorithmen 2, Vorlesung, WS19/20 ·

2019/12/17

18 | 0:00:00 Start 0:00:05 12.1 Streckenschnitt 0:09:33 12.2 2D Konvexe Hülle 0:19:37 3D Konvexe Hülle 0:24:19 12.3 Kleinste einschließende Kugel 0:44:00 Ähnliche Randomisierte Linearzeitalgorithmen 0:48:41 12.4 2D Bereichssuche 1:02:45 Wavelet Tree

01:22:31

17: Algorithmen II, Vorlesung und Übung, WS 2019/20,...

Algorithmen 2, Vorlesung, WS19/20 ·

2019/12/12

17 | 0:00:00 Start 0:00:05 12 Geometrische Algorithmen 0:37:19 Übung 7 0:38:00 Approximationsalgorithmen 0:38:05 Grundlagen 0:38:56 Gütemaß 0:39:32 Klassen 0:41:33 Minimum Metric TSP 0:52:13 Zusammenfassung 0:52:51 Parametrisierte Algorithmen: fixed parameter tractable (FPT) 0:54:57 Parametrisierte Algorithmen: Definition 0:55:56 Techniken 0:57:50 Schiebepuzzle 0:59:59 Parallelverarbeitung: Modelle 1:04:43 PRAM Speicherkonflikte 1:08:38 Verbindungsnetzwerke Struktur 1:11:45 Anwendungen: Präfixsumme

01:26:31

16: Algorithmen II, Vorlesung und Übung, WS 2019/20,...

Algorithmen 2, Vorlesung, WS19/20 ·

2019/12/05

16 | 0:00:00 Start 0:00:05 Vorlesungswiederholung 0:02:23 Sortieren 0:02:45 Paralleles Quicksort 0:04:09 Anfänger-Parallelisierung 0:05:26 Theoretiker-Parallelisierung 0:08:43 Beispiel 0:16:30 Analyse 0:20:27 Verallgemeinerung für n >> p nach Schema F? 0:30:40 Paralleles Sortieren durch Mehrwegmischen 0:34:12 Mehr zu parallelem Sortieren 0:36:22 Messergebnisse 0:42:28 Übung 0:44:07 Applications 0:46:30 Large real-world networks 0:52:31 Branch and Reduce 0:54:39 Reduction rules 0:58:27 And

01:25:58

15: Algorithmen II, Vorlesung, WS 2019/20, 02.12.2019

Algorithmen 2, Vorlesung, WS19/20 ·

2019/12/03

15 | 0:00:00 Start 0:00:05 9 Fixed-Parameter-Algorithmen 0:01:15 Naive tiefenbeschränkte Suche 0:07:03 Reduktionsregeln 0:10:20 Verbesserte tiefenbeschränkte Suche 0:21:00 Zusammenfassung 0:23:23 10 Parallele Algorithmen 0:24:02 Warum Parallelverarbeitung 0:32:43 10.1 Modell 0:36:17 Kostenmodell für Nachrichtenaustausch 0:39:52 Warum kein Multicore-Modell 0:43:55 Formulierung paralleler Algorithmen 0:46:33 Analyse paralleler Algorithmen 0:53:45 10.2 Beispiel: Assoziative Operationen 1:06:39

01:14:07

14: Algorithmen II, Vorlesung und Übung, WS 2019/20,...

Algorithmen 2, Vorlesung, WS19/20 ·

2019/11/28

13 | 0:00:00 Start 0:00:05 Rucksackproblem 0:01:00 Fully Polynomial Time Approximations Scheme 0:02:57 Lemma 6 0:10:57 Lemma 7 0:13:31 Das beste bekannte FPTAS 0:16:27 Optimale Algorithmen für das Rucksackproblem 0:20:44 Fixed-Parameter-Algorithmen 0:22:41 Beispiel: VERTEX COVER 0:25:56 Fixed parameter tractable 0:30:23 Naive tiefenbeschränkte Suche 0:34:04 Kernbildung für Vertex Cover 0:42:25 Übung 6 0:43:04 Randomisierte Algorithmen 0:44:06 Monte Carlo Simulation 0:44:47 Las Vegas zu Monte

01:23:01

13: Algorithmen II, Vorlesung, WS 2019/20, 25.11.2019

Algorithmen 2, Vorlesung, WS19/20 ·

2019/11/26

13 | 0:00:00 Start 0:00:50 Approximationsalgorithmen 0:06:54 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:10:22 List Scheduling 0:19:27 Der Approximationsfaktor 0:34:27 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP) 0:37:04 Beweis 0:45:57 Euler-Touren/-Kreise 0:48:36 2-Approximation durch minimalen Spannbaum 0:51:56 Beispiel 0:54:47 Beweis 0:55:39 Zusatz: Mehr TSP 1:07:03 Pseudopolynomielle Algorithmen 1:09:07 Beispiel: Rucksackproblem 1:10:50 Dynamische

01:13:29

12: Algorithmen II, Vorlesung und Übung, WS 2019/20,...

Algorithmen 2, Vorlesung, WS19/20 ·

2019/11/21

12 | 0:00:00 Start 0:00:05 Externe Algorithmen 0:04:35 Externe Prioritätslisten 0:23:46 Experiments 0:29:19 Offenes Problem 0:44:50 Approximationsalgorithmen 0:45:37 Übung 0:46:51 Potentialmethode 0:50:01 preflow-push Algorithmus 0:56:31 FIFO preflow-push Algorithmus 1:10:36 Matching

01:20:55

11: Algorithmen II, Vorlesung, WS 2019/20, 18.11.2019

Algorithmen 2, Vorlesung, WS19/20 ·

2019/11/19

11 | 0:00:00 Start 0:00:59 Randomisierte Algorithmen 0:01:39 Wichtigste Unterscheidung 0:02:43 Beispiel: Monte Carlo-Algorithmus 0:10:57 Sort Checking II 0:15:22 Hashing II 0:23:57 Cuckoo Hashing 0:35:49 Random Graph Theory 0:39:51 Space Efficient Cuckoo Hashing 0:45:22 Zusammenfassung: Randomisierte Algorithmen 0:47:33 Externe Algorithmen 0:47:37 Das Sekundärspeichermodell 0:51:08 Externe Stapel 0:54:29 Externes Sortieren 1:02:52 Zahlenbeispiel 1:04:17 Mehrwegmischen

00:41:57

10: Algorithmen II, Vorlesung, WS 2019/20, 12.11.2019

Algorithmen 2, Vorlesung, WS19/20 ·

2019/11/14

10 | 0:00:00 Start 0:00:05 Zusammenfassung letzter Vorlesung 0:02:20 Highest Level Preflow Push 0:04:14 Proof of Lemma 12 0:07:03 Claims 0:20:04 MFIFO: Modified FIFO Selection Rule 0:21:04 Heuristic Improvements 0:28:20 Experimental Results 0:29:51 Timings: Random Graphs 0:33:04 Timings: CG1 0:34:10 Timings: CG2 0:35:07 Timings: AMO 0:36:36 Asymptotics 0:37:54 Recent AE Results on Max-Flow 0:40:04 Zusammenfassung Flows und Matchings

01:25:07

09: Algorithmen II, Vorlesung, WS 2019/20, 11.11.2019

Algorithmen 2, Vorlesung, WS19/20 ·

2019/11/12

09 | 0:00:00 Start 0:00:05 Ford Fulkerson Algorithm 0:03:24 Matching 0:08:18 Maximum Cardinality Bipartite Matching 0:14:11 Similar Performance for Weighted Graphs 0:19:48 Disadvantage of augmenting paths algorithms 0:28:09 Level Function 0:48:19 Partial Correctness 1:09:34 Searching for Eligible Edges 1:14:36 FIFO Preflow push

28 results

Algorithmen 2, Vorlesung, WS19/20

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