PODCAST

Algorithmen 2, Vorlesung, WS18/19

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

01:26:48

30: Algorithmen II, Vorlesung, WS 2018/19, 05.02.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/02/07

30 | 0:00:00 Start 0:00:20 Schrumpfgraph 0:02:39 Approximationsalgorithmen 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:03:57 Viele kleine Jobs 0:04:52 Untere Schranken 0:05:10 Der Approximationsfaktor 0:07:17 Diese Schranke ist bestmöglich 0:07:49 Mehr zu Scheduling 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems 0:08:33 Hamilton Cycle 0:10:07 TSP mit Dreiecksungleichung 0:10:38 2-Approximstion durch minimalen Spannbaum 0:11:16 Pseudopolynomielle

01:22:51

29: Algorithmen II, Vorlesung, WS 2018/19, 04.02.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/02/04

29 | 0:00:00 Starten 0:00:10 Inhaltsübersicht 0:03:02 Rolle der Algorithmik 0:03:43 Machine Learning macht das von selbst 0:17:02 Algorithm Theory 0:21:47 Graphenalgorithmen 0:22:20 Laufzeit 0:26:50 Satz 1 0:29:13 Monotone ganzzahlige Prioritätslisten 0:30:15 Bucket Queue 0:33:27 Analyse 0:34:30 All-Pair Shortest Paths 0:35:09 Knotenpotentiale 0:36:07 Algorithmus 0:37:46 Landmarks 0:38:33 Zusammenfassung Kürzeste Wege 0:39:47 Fortgeschrittene Datenstrukturen 0:40:21 Adressierbare

01:10:31

28: Algorithmen II, Übung, WS 2018/19, 29.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/31

28 | 0:00:00 Start 0:00:08 Übung 11 0:02:04 Themenübersicht 0:02:49 in-place Multikey Quicksort 0:08:18 Partitionierung 0:20:32 Suche mit Suffix-Arrays 0:34:34 Ablauf 0:40:40 Zusammenfassung 0:43:06 LCP-Array 0:52:10 Schnelle Suche mit Suffix-Arrays 0:55:58 Redundante Vergleiche

01:26:16

27: Algorithmen II, Vorlesung, WS 2018/19, 28.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/29

28 | 0:00:00 Start 0:00:05 Einleitung 0:00:28 Dominik Schreiber - SAT Solving and Automated Planning 0:00:41 Overview 0:01:51 The SAT Problem 0:03:39 SAT Solving 0:05:06 Parallel SAT Solving 0:09:30 Automated Planning 0:13:20 SAT-based Planning 0:17:44 Outlook: Future Research and Teaching 0:23:16 Sebastian Lamm - Distributed Connected Components 0:23:45 Connected Components and Applications 0:25:23 Sequential Algorithms 0:26:16 General Framework 0:29:04 All-Reduce (AR) - Algorithm 0:31:14

01:25:20

26: Algorithmen II, Vorlesung, WS 2018/19, 22.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/24

26 | 0:00:00 Start 0:00:05 LCP-Array 0:11:29 Textkompression 0:12:39 Lempel-Ziv Kompression (LZ) 0:30:17 Burrows-Wheeler-Transformation 0:35:48 Burrows-Wheeler-Transformation-- Rücktransformation 0:48:41 Was bringt die BWT? 0:50:52 BWT--Kompression 0:58:13 Suche in BWT 0:59:10 Backward Search 1:12:41 Wavelet Tree Example: Calculate Rank

01:25:34

25: Algorithmen II, Vorlesung, WS 2018/2019, 21.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/22

25 | 0:00:00 Start 0:00:05 Suffix Array Konstruktionsalgorithmen 0:01:30 SA mit Präfix Verdopplung 0:04:27 Suffixtabellen 0:05:56 Ein erster Teile-und-Herrsche-Ansatz 0:07:22 Asymmetrisches Divide-and-Conquer 0:14:36 Rekursion 0:27:05 Least Significant Digit First Radix Sort 0:28:40 Stabiles Ganzzahliges Sortieren 0:30:16 Sortieren: Most Significant Digit Radix Sort 0:33:16 Suffix-Baum 0:36:08 Implementierung: Vergleichs-Operatoren 0:37:40 Verallgemeinerung: Differenzenüberdeckungen 0:46:22 Suche

01:18:49

24: Algorithmen II, Vorlesung und Übung, WS 2018/19,...

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/17

24 | 0:00:00 Start 0:00:07 Stringology 0:02:36 Fragen zur letzten Vorlesung/ Wiederholung 0:08:51 Suffix-Baum 0:13:39 Alphabet-Modell 0:17:31 Suffix Array Konstruktionsalgorithmen 0:19:50 SA mit Präfix Verdopplung 0:36:14 Ein erster Teile-und-Herrsche-Ansatz 0:37:32 SA1 berechnen 0:39:42 Berechne SA0 aus SA1 0:41:12 Asymmetrisches Divide-and-Conquer 0:43:50 Übung 0:43:53 Online Algorithmen 0:46:32 kompetitiver Faktor 0:48:15 Ski Rental Problem 1:00:15 Doubling Strategie 1:01:09 Online Bidding

01:24:22

23: Algorithmen II, Vorlesung, WS 2018/19, 14.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/15

23 | 0:00:00 Start 0:00:05 Competitive analysis 0:01:19 Atypical online problem: ski rental 0:01:50 Paging 0:02:33 Longest Forward Distance is optimal 0:02:50 Comparison of algorithms 0:03:28 Resource augmentation 0:03:41 Competitive ratio 0:03:53 Counting the faults of OPT 0:03:55 Randomized algorithms 0:04:04 Marking Algorithms 0:04:58 Why competitive analysis 0:06:30 Disadvantages of competitive analysis 0:08:35 Stringology 0:10:08 Strings Sortieren 0:19:15 Multikey Quicksort 0:23:21 Ohne

01:21:21

22: Algorithmen II, Vorlesung, WS 2018/19, 08.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/10

22 | 0:00:00 Start 0:00:33 2D Bereichssuche 0:01:30 Wavelet Tree 0:10:21 Bitvektoren 0:12:16 Onlinealgorithmen 0:17:10 Competitive analysis 0:22:46 online problem: ski rental 0:31:16 Paging 0:42:50 Comparison of algorithms 0:48:43 A general lower bound 0:55:01 Resource augmentation 0:57:08 Conservative algorithms 1:05:36 New results 1:07:48 Radomized algorithms 1:09:04 Three types of adversaries 1:11:34 Marking Algorithm 1:13:52 Competetive ratio of RMARK

01:23:21

21: Algorithmen II, Vorlesung, WS 2018/19, 07.01.2019

Algorithmen 2, Vorlesung, WS18/19 ·

2019/01/09

21 | 0:00:00 Start 0:00:05 12.3 Kleinste einschließende Kugel 0:13:24 Ähnliche Randomisierte Linearzeitalgorithmen 0:18:20 12.4 2D Bereichssuche 0:23:00 1D Bereichssuche 0:34:42 Wavelet Tree 0:43:30 Wavelet Tree Counting Query 0:47:19 Wavelet Tree Dominance Counting Query 1:09:08 Allgemeine Reporting Query 1:16:12 Mehr zu Bitvektoren 1:19:06 13 Onlinealgorithmen

01:21:27

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

Algorithmen 2, Vorlesung, WS18/19 ·

2018/12/21

19 | 0:00:00 Start 0:00:05 Geometrische Algorithmen 0:02:41 Elementare geometrische Objekte 0:08:38 Typische Fragestellungen 0:13:23 Datenstrukturen für Punktmengen 0:19:51 Streckenschnitt (line segment intersection) 0:22:44 Streckenschnitt: Untere Schranke 0:26:40 Plane-Sweep für orth. Streckenschnitt 0:35:29 Verallgemeinerung – aber erstmal ""nicht ganz"" 0:38:46 Verallgemeinerung – Grundidee 0:45:00 Verallgemeinerung – Korrektheit 0:46:41 Verallgemeinerung –

01:26:48

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

Algorithmen 2, Vorlesung, WS18/19 ·

2018/12/20

20 | 0:00:00 Start 0:00:16 Streckenschnitt 0:08:45 2D Konvexe Hülle 0:11:12 Graham's Scan 0:19:43 3D Konvexe Hülle 0:25:50 Kleinste einschließende Kugel 0:50:26 Übung 9 0:51:44 Geometrische Algorithmen 0:54:56 Geometrische Methoden 0:59:46 Sweep-Line Beispiel: Skyline 1:22:03 Punktorientierung

01:28:33

18: Algorithmen II, Vorlesung und Übung, WS 2018/19,...

Algorithmen 2, Vorlesung, WS18/19 ·

2018/12/13

18 | 0:00:00 Start 0:00:16 Sortieren 0:00:33 Theoretiker-Parallelisierung 0:00:47 Analyse 0:01:06 Verallgemeinerung 0:02:49 Paralleles Sortieren durch Mehwegemischen 0:07:54 Messungen Spare T1 - 8 Kerne, 128 bit Elemente 0:10:53 Mehr zu parallelem sortieren 0:14:24 Experiments 0:25:29 Messungen 0:35:18 Mehr zu parallelem Algorithmen - Parallelisierung der Basic Toolbox 0:49:10 Übung 0:49:15 Themenübersicht 0:50:09 Parametrisierte Algorithmen 1:00:03 Parallelverarbeitung 1:04:16 PRAM 1:07:13

01:29:58

17: Algorithmen II, Vorlesung, WS 2018/19, 10.12.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/12/10

17 | 0:00:00 Starten 0:00:05 Nachrichtengekoppelte Parallelrechner 0:02:02 Analyse paraller Algorithmen 0:12:22 Beispiel: Assoziative Operationen (= Reduktion) 0:27:26 Diskussion Reduktionsoperation 0:28:36 Hyperwürfel 0:34:09 Hyperwürfelalgorithmus 0:46:14 Sortieren 0:47:12 Paralleles Quicksort 0:52:53 Beispiel 1:13:00 Analyse 1:21:01 Paralleles Sortieren durch Mehrwegemischen

01:23:41

16: Algorithmen II, Vorlesung und Übung, WS 2018/19,...

Algorithmen 2, Vorlesung, WS18/19 ·

2018/12/06

16 | 0:00:00 Start 0:00:57 Naive tiefenbeschränkte Suche 0:01:20 Naive tiefenbeschränkte Suche - Laufzeit 0:02:29 Kernbildung für Vertex Cover 0:03:01 Kernbildung für Vertex Cover - Korrektheit 0:03:47 Kernbildung für Vertex Cover - Laufzeit 0:05:05 Kernbildung für Vertex Cover - Beispiel 0:07:02 Reduktionsregeln 0:09:36 Verbesserte tiefenbeschränkte Suche 0:14:06 Weitere Verbesserungen 0:15:52 Zusammenfassung 0:19:41 Parallele Algorithmen 0:20:21 Warum Parallelverarbeitung 0:28:49 Modell -

01:27:08

15: Algorithmen II, Vorlesung, WS 2018/19, 03.12.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/12/04

15 | 0:00:00 Starten 0:00:05 8 Approximationsalgorithmen 0:00:23 Scheduling unabhängiger gewichteter Jobs auf parallelen Machinen 0:01:03 List Scheduling 0:01:27 Viele Kleine Jobs 0:04:13 Der Approximationsfaktor 0:08:23 Diese Schranke is bestmöglich 0:10:04 Mehr zu Scheduling 0:24:05 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP) 0:29:53 TSP mit Dreiecksungleichung 0:31:12 2-Approximation durch minimalen Spannbaum 0:35:57 Beispiel 0:40:12 Mehr TSP 0:51:39 Pseudopolynomielle

01:21:12

14: Algorithmen II, Vorlesung und Übung, WS 2018/19,...

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/29

14 | 0:00:00 Starten 0:05:55 Frage 0:07:29 Große Queues 0:08:34 Minimale Spannbäume 0:10:49 Mehr zu externen Algorithmen-Basic Toolbox 0:16:58 Approximationsalgorithmen 0:23:15 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschienen 0:28:52 List Scheduling 0:36:37 Untere Schranken 0:38:16 Übung 0:38:35 Matching 0:41:14 Bipartite-Matching 0:43:07 Matching Anwendungen 0:46:08 Randomisierte Algorithmen 0:48:48 Monte Carlo Simulation 0:51:33 Las Vegas --> Monte Carlo 0:55:38 Beispiel 1

01:27:27

13: Algorithmen II, Vorlesung, WS 2018/19, 26.11.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/27

13 | 0:00:00 Starten 0:00:05 Here: Fast Space Efficient Hashing 0:01:06 Cuckoo Hashing 0:01:57 Space Efficient Cuckoo Hashing 0:03:41 Random Graph Theory 0:05:52 Das Sekundärspeichermodell 0:09:50 Externe Stapel 0:15:00 Externes Sortieren 0:18:31 Externes binäres Mischen - I/O - Analyse 0:23:02 Run Formation 0:24:57 Sortieren durch Externes Binäres Mischen 0:27:07 Zahlenbeispiel: PC 2018 0:31:56 Mehrwegmischen 0:36:43 Sortieren durch Mehrweg-Mischen 0:50:13 Externe Prioritätslisten 0:54:17

01:22:09

12: Algorithmen II, Vorlesung und Übung, WS 2018/19,...

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/22

12 | 0:00:00 Start 0:00:05 Randomisierte Algorithmen 0:00:23 Sortieren - Ergebnisüberprüfung (cheking) 0:03:23 Sort Cheking 0:10:42 Hashing 0:13:55 Here: Fast Space Efficient Hashing 0:15:44 Related Work 0:21:27 Cuckoo Hashing 0:25:55 Cuckoo Hashing - Rebuilds 0:35:29 Cuckoo Hashing - How many Rebuilds? 0:37:45 Random Graph Theory 0:41:12 Space Efficient Cuckoo Hashing 0:45:21 Zusammenfassung: Randomisierte Algorithmen 0:46:00 Ausblick: Randomisierte Algorithmen 0:46:47 Übung 5 0:46:56

01:25:19

11: Algorithmen II, Vorlesung, WS 2018/19, 19.11.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/19

11 | 0:00:00 Start 0:00:05 Ford Fulkerson Algorithm 0:01:12 Blocking Flows 0:01:26 Dinitz Algorithm 0:02:02 Dinitz Analysis 0:03:10 Preflow-Push Algorithms 0:03:59 Level Function 0:09:26 FIFO Preflow push 0:10:00 Highest Level Preflow Push 0:11:13 Proof of Lemma 12 0:16:11 Claims 0:35:57 Heuristic Improvements 0:42:24 Experimental results 0:47:29 Trainings: Random Graphs 0:53:01 Training: CG1 0:56:33 Training: CG2 0:58:11 Training: AMO 1:03:46 Zusammenfassung Flows und Matchings 1:10:08 6

30 results

Algorithmen 2, Vorlesung, WS18/19

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