PODCAST

Algorithmen 2, WS2016/17, Vorlesung

Karlsruher Institut für Technologie (KIT)

lgorithmen 2, WS2016/17, Vorlesung

education higher education

All Episodes

00:37:01

Algorithmen II, Vorlesung, WS 2016/17, 07.02.2017, 26

Algorithmen 2, WS2016/17, Vorlesung ·

2017/02/16

26 | 0:00:00 Starten 0:01:13 Fortgeschrittene Graphenalgorithmen: 2 Kürzeste Wege 0:02:31 Monotone ganzzahlige Prioritätslisten 0:03:05 Radix-Heaps 0:04:38 All-Pairs Shortest Paths 0:06:18 3 Anwendungen von DFS 0:08:27 Algorithms 1956-now 0:11:39 Preflow-Push Algorithms 0:13:38 5 Externe Algorithmen 0:15:04 6 Fixed-Parameter-Algorithmen 0:16:16 Fixed parameter tractable 0:16:49 Beispiel: VERTEX COVER 0:17:46 Naive tiefenbeschränkte Suche 0:18:38 7 Parallele Algorithmen 0:18:41 Warum

01:11:59

Algorithmen II, Vorlesung und Übung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2017/02/03

25 | 0:00:00 Starten 0:00:24 Wavlet Tree 0:08:46 Allgemeine Reporting Query 0:09:02 Bitvektoren 0:15:34 Suffix Array 0:15:45 Backward Search 0:20:37 Wavelet Tree Example: Calculate Rank 0:24:21 Index size comparison 0:26:55 Beginn Übung 13 0:27:01 Themenübersicht 0:28:27 Geometrische Algorithmen 0:32:55 Geometrische Methoden 0:35:13 Sweep-Line 0:39:04 One-Dimensional Problem 0:39:26 Skyline 0:56:58 Linienschnitt 1:02:03 Punktorientierung

01:24:12

Algorithmen II, Vorlesung, WS 2016/17, 25.01.2017, 24

Algorithmen 2, WS2016/17, Vorlesung ·

2017/02/02

24 | 0:00:00 Starten 0:00:14 Verallgemeinerung 0:10:21 Überlappungen finden 0:11:52 Platzverbrauch 0:12:45 Mehr Linienschnitt 0:13:34 9.2 2D Konvexe Hülle 0:17:35 Graham's Scan 0:23:22 3D Konvexe Hülle 0:25:05 9.3 Kleinste einschließende Kugel 0:31:29 Kleinste einschließende Kugel - Korrektheitm 0:35:57 Kleinste einschließende Kugel - Analyse 0:49:17 9.4 2D Bereichssuche 0:52:14 1D Bereichssuche 0:58:43 Reduktion auf 1...n x 1...n 1:01:19 Beispiel 1:02:05 Walvelet Tree

01:25:15

Algorithmen II, Übung und Vorlesung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2017/02/02

23 | 0:00:00 Starten 0:00:07 Übung 12 - Online Algorithmen 0:02:44 Grundlagen 0:04:19 Gütemaß 0:05:21 Ski Rental Problem 0:06:46 Randomisierte Ski Rental Strategie 0:18:02 Doubling Strategie 0:18:52 Online Bidding 0:40:30 Zusammenfassung 0:41:39 Vorlesung: Kapitel 9 - Geometrische Algorithmen 0:45:17 Elementare Geometrische Objekte 0:49:22 Typische Fragestellungen 0:53:29 Verweissensitive Grafik (Wikipedia) 0:54:30 Datenstrukturen für Punktemengen 0:54:42 Mehr Fragestellungen 0:59:47 9.1

01:17:17

Algorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22

Algorithmen 2, WS2016/17, Vorlesung ·

2017/01/20

22 | 0:00:00 Starten 0:00:42 13 Onlinealgorithmen 0:05:35 Examples 0:08:09 Competitive analysis 0:09:19 A typical online problem: ski rental 0:11:31 Upper bound for ski rental 0:14:33 Lower bound for ski rental 0:18:07 Paging 0:20:16 Definitions 0:21:49 Paging algorithms 0:25:11 Longest Forward Distance is optimal 0:27:34 Using the claim 0:29:01 Proof the claim 0:29:44 Comparison of algorithms 0:34:33 A general lower bound 0:38:53 Resource augmentation 0:40:14 Conservative algorithms 0:43:26

01:27:55

Algorithmen II, Vorlesung und Übung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2017/01/19

21 | 0:00:00 Starten 0:00:07 Burrows-Wheeler-Transformation 0:12:23 Datenkompression 0:18:42 Verlustfreie Textkompression 0:30:39 Wörterbuchbasierte Textkompression 0:33:02 Lempel-Ziv Kompression 0:33:45 Naive Lempel-Ziv Kompression 0:43:15 Naive LZ Dekompression 0:45:08 LZ Beispiel 0:45:16 LZ-Verfeinerung 0:46:37 Begin Übung 11 0:48:29 Suche mit Suffix-Arrays (1) 0:56:41 LCP-Array 1:03:46 Schnelle Suche mit Suffix-Arrays 1:10:29 Suche mit Suffix-Arrays (2)

01:28:14

Algorithmen II, Vorlesung, WS 2016/17, 10.01.2017, 20

Algorithmen 2, WS2016/17, Vorlesung ·

2017/01/19

20 | 0:00:00 Starten 0:00:07 Wiederholung: Asymmetrisches Divide-and-Conquer 0:03:50 Implementierung 0:06:04 Verallgemeinerung: Differenzenüberdeckungen 0:10:34 Verbesserungen / Verallgemeinerungen 0:11:23 Suffixtabellenkonstruktion: Zusammenfassung 0:12:00 Suche in Suffix Arrays 0:14:13 LCP-Array 0:15:56 Beispiel 0:32:42 LCP-Array: Berechnung 0:39:53 Suffix-Baum aus SA und LCP 0:41:20 Beispiel 0:53:45 Suche in Suffix-Bäumen 0:55:41 Datenkompression 0:55:55 Burrows-Wheeler-Transformation

01:31:49

Algorithmen II, Vorlesung und Übung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2017/01/12

19 | 0:00:00 Starten 0:00:09 Wiederholung: Suffix Tree und Suffix Array 0:02:28 Kapitel 8 - Stringology (Zeichenkettenalgorithmen) 0:03:37 Etwas ""Stringology""-Notation 0:05:26 Suffixe Sortieren 0:05:59 Anwendungen 0:07:05 Volltextsuche 0:07:28 Suffix-Baum 0:08:33 Alphabet-Modell 0:09:24 Geordnetes --> ganzzahliges Alphabet 0:10:30 Verallgemeinerung: Lexikographische Namen 0:11:20 Ein erster Teile-und-Herrsche-Ansatz 0:15:17 SA1 berechnen 0:17:08 Berechne SA0 aus SA1 0:19:50

01:32:06

Algorithmen II, Vorlesung, WS 2016/17, 20.12.2016, 18

Algorithmen 2, WS2016/17, Vorlesung ·

2017/01/12

18 | 0:00:00 Starten 0:00:07 Stringology (Zeichenkettenalgorithmen) 0:00:59 Top 10 query completion (Suchvolumina) 0:04:18 Weitere Anwendungen 0:10:19 Naives Pattern Matching 0:17:29 Besserer Algorithmus 0:27:53 Fallanalyse Palindrome 0:41:09 Berechnung der Verschiebetabelle 1:00:26 Multi Key Quicksort for Strings 1:11:00 Matching von k pattern gegen einen Text der Länge n 1:12:46 Suffix Tree und Suffix Array

01:17:41

Algorithmen II, Übung, WS 2016/17, 14.12.2016, 17

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/20

17 | 0:00:00 Starten 0:00:07 Übung 9 – Algorithmen 2 0:00:27 Themenübersicht 0:02:21 Parallelverabeitung 0:06:11 PRAM 0:08:27 Verbindungsnetzwerke 0:14:26 Anwendungen 0:33:58 Parallele Programmierung 0:35:53 Übung 8 – Algorithmen 2 0:36:07 Anwendungen 0:38:33 Themenübersicht 0:40:20 Approximationsalgorithmen 1:06:46 Parametrisierte Algorithmen

01:18:37

Algorithmen II, Vorlesung, WS 2016/17, 13.12.2016, 16

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/20

16 | 0:00:00 Starten 0:00:09 Wiederholung 0:11:01 9 Fixed-Parameter-Algorithmen 0:30:14 10 Parallele Algorithmen 0:35:16 10.1 Modell Nachrichtengekoppelte Parallelrechner 0:46:53 10.2 Beispiel: Assoziative Operationen (=Reduktion) 0:59:16 Präfixsummen 1:04:46 10.3 Sortieren

01:09:47

Algorithmen II, Vorlesung, WS 2016/17, 07.12.2016, 15

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/20

15 | 0:00:00 Starten 0:00:09 Wiederholung: Job Scheduling 0:03:14 Wiederholung: List Scheduling 0:10:08 Wiederholung: TSP 0:13:43 Wiederholung: Metric TSP 0:19:21 Pseudopolynomielle Algorithmen 0:22:08 Rucksack Problem 0:25:21 Dynamic Programming 0:33:09 Fully Polynomial Time Approximation Scheme 0:34:50 Beispielschranken 0:36:22 FPTAS für Knapsack 0:47:18 Lemma 21 0:48:43 Das beste bekannte FPTAS 0:49:06 Optimale Algorithmen für das Rucksackproblem 0:49:37 9 Fixed-Parameter-Algorithmen 0:50:57

01:03:21

Algorithmen II, Vorlesung, WS 2016/17, 06.12.2016, 14

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/13

14 | 0:00:00 Starten 0:00:10 Wiederholung 0:09:49 8 Approximationsalgorithmen 0:12:39 Job Scheduling 0:26:47 Approximationsfaktor 0:38:22 Traveling Salesman Problem 0:51:22 Metric TSP 0:53:54 Euler-Tour/Kreis 0:59:01 Algorithmus

01:14:48

Algorithmen II, Vorlesung, WS 2016/17, 29.11.2016, 12

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/06

12 | 0:00:00 Starten 0:01:10 Wiederholung 0:17:28 Randomisierter Algorithmus 0:33:34 Barabasi Albert Graph Generation 0:52:54 7 Externe Algorithmen 0:53:01 7.1 Das Sekundärspeichermodell 1:07:02 7.2 Externe Stabel 1:11:38 Run Formation 1:13:03 Sortieren durch Externes Binäres Mischen

01:34:32

Algorithmen II, Vorlesung und Übung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/06

13 | 0:00:00 Starten 0:00:09 Wiederholung 0:10:06 Externe Algorithmen 0:13:21 7.2 Externe Stapel 0:15:56 Run Formation 0:16:33 Sortieren durch Externes Binäres Mischen 0:17:16 Zahlenbeispiel: PC 2010 0:18:01 Mehrwegmischen 0:22:06 Sortieren durch Mehrwege-Mischen 0:23:30 Mehr zu externem Sortieren 0:25:47 Mehrwegmischen – Analyse 0:26:16 Externe Prioritätsliste 0:27:28 Sequence Heaps 0:33:30 Analyse 0:35:03 Große Queues 0:35:47 Experiments 0:36:54 Minimale Spannbäume 0:38:04 Externe

01:30:52

Algorithmen II, Vorlesung und Übung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/01

11 | 0:00:00 Starten 0:01:51 Wiederholung 0:10:59 Example 0:23:53 Searching for Eligibla Edges 0:27:29 FIFO Preflow push 0:29:07 Highest Level Preflow Push 0:31:15 Proof of Lemma 13 0:33:26 Claims 0:44:27 Heuristic Improvements 0:47:01 Experimental results 0:50:36 Zusammenfassung Flows und Matchings 0:51:54 Übung 6 0:53:51 Potentialmethode 1:00:25 preflow-push Algorithmus 1:12:37 FIFO preflow-push Algorithmus

01:19:59

Algorithmen II, Übung, WS 2016/17, 22.11.2016, 10

Algorithmen 2, WS2016/17, Vorlesung ·

2016/12/01

10 | 0:00:00 Starten 0:00:09 Wiederholung L8 0:15:30 Dinics Alogorithmus 0:32:19 Matching 0:34:41 Maximum Cardinality Bipartite Matching 0:35:37 Similar Performance for Weighted Graphs? 0:36:51 Disadvantage of augmenting paths algorithms 0:39:10 Preflow-Push Algorithmen 0:42:47 Procedure Push 0:49:32 Procedure genericPreflowPush

01:19:27

Algorithmen II, Übung, WS 2016/17, 16.11.2016, 09

Algorithmen 2, WS2016/17, Vorlesung ·

2016/11/22

09 | 0:00:00 Starten 0:00:36 Themenübersicht 0:01:47 Nachklausur 0:02:16 Ford Fulkerson 0:02:20 Flüsse und Ford Fulkerson 0:07:45 Residualgraph 0:11:40 Flüsse und Ford Fulkerson 0:14:02 Max Flow - Min Cut 0:17:12 Dinitz Algorithmus 0:18:52 Dinitz - Distanz Label 0:22:38 Dinitz - Schichtgraph für Graph G = (V, E) 0:25:02 Dinitz - Blockierender Fluss 0:28:25 Dinitz - Blockierender Fluss: Operationen 0:33:25 Dinitz - Kosten pro Blockierender Fluss 0:38:12 Dinitz - Laufzeit 0:40:05 Dinitz - Kosten pro

01:24:52

Algorithmen II, Vorlesung, WS 2016/17, 15.11.2016, 08

Algorithmen 2, WS2016/17, Vorlesung ·

2016/11/22

08 | 0:00:00 Starten 0:00:18 Wiederholung Starke Zusammenhangskomponenten 0:05:26 Wiederholung Tiefensuchschema 0:13:12 5 Maximum Flows and Matchings 0:14:57 Definitions: Network 0:16:04 Definitions: Flows 0:18:46 Definitions: (Minimum) s-t Cuts 0:20:12 Duality Between Flows and Cuts 0:21:21 Applications 0:22:11 Applications in our Group 0:22:34 Exkurs: Balanced Bipartitioning 0:27:24 Example 0:28:58 Option 1: linear programming 0:32:33 Algorithms 1956-now 0:34:00 Augmenting Paths (Rough

01:31:44

Algorithmen II, Vorlesung und Übung, WS 2016/17,...

Algorithmen 2, WS2016/17, Vorlesung ·

2016/11/21

07 | 0:00:00 Starten 0:00:57 1 Algorithm Engineering 0:05:04 (Caricatured) Traditional View: Algorithm Theory 0:07:43 Gaps Between Theory & Practice 0:12:14 Algorithmics as Algorithm Engineering 0:18:43 Bits of History 0:25:30 Realistic Models 0:28:11 Design 0:30:03 Analysis 0:31:05 Implementation 0:33:47 Experiments 0:37:14 Algorithm Libraries - Challenges 0:42:58 Problem Instances 0:43:45 Example: Sorting Benchmark (Indy) 0:45:41 GraySort 0:45:41 JouleSort 0:46:46 Applications tha

26 results

Algorithmen 2, WS2016/17, Vorlesung

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