PODCAST

Algorithmen 2, Vorlesung, WS18/19

Karlsruher Institut für Technologie (KIT)

education higher education

All Episodes

01:19:36

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

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/15

10 | 0:00:00 Start 0:00:39 Preflow-Push Algorithms 0:02:02 Level Funktion 0:05:36 Example 0:06:50 Pratial Correctness 0:13:09 Lemma 4. 0:16:18 Lemma 5. 0:21:08 Lemma 6. 0:23:11 Lemma 7. 0:23:34 Lemma 8. 0:26:09 Lemma 9. 0:32:41 Searching for Eligable Edges 0:37:49 Satz 11. 0:40:06 FIFO Preflow push 0:41:52 Highest Level Preflow Push 0:45:18 Example 0:51:22 Übung 4 0:51:56 Flüsse und Ford Fulkerson 0:55:48 Residualgraph 1:02:15 Max Flow - Min Cut 1:04:59 Dinitz Algorithmus

01:20:12

09: Algorithmen II, Vorlesung, WS 2018/19, 12.11.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/13

09 | 0:00:00 Start 0:00:09 Ford Fulkerson - Correctness 0:00:46 Ford Fulkerson Algorithm 0:08:49 Max-Flow-Min-Cut theorem 0:11:18 A bad example for Ford Fulkerson 0:13:25 Dinitz Algorithm 0:18:35 Dinitz-Correctness 0:21:22 Computing blocking flows 0:27:46 Blocking flows analysis 0:33:40 Dinitz analysis 0:40:55 Matching 0:43:54 Maximum cardinality bipartite matching 0:46:31 Similar performance for weight graphs? 0:50:06 Disadvantage of augmenting paths algorithms 0:52:10 Pre-flow-push

01:07:18

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

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/08

08 | 0:00:00 Start 0:00:05 Augmenting Paths 0:01:56 Ford Fulkerson Algorithm 0:07:57 Some Basic Observations 0:14:57 Blocking Flows 0:16:44 Suche in Graphen 0:20:19 Dijkstras Algorithmus 0:28:30 A*-Suche 0:31:31 A*-Suche – Potentialfunktionen 0:37:23 A*-Suche – Landmarken 0:47:01 Starke Zusammenhangskomponenten 1:00:07 Floyd Warshall: SCC als Speedup Technik

01:26:23

07: Algorithmen II, Vorlesung, WS 2018/19, 05.11.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/06

07 | 0:00:00 Start 0:00:37 Tiefensuchschema 0:01:14 Starke Zusammenhangskomponenten 0:02:21 Schrumpfgraph 0:02:55 Konkreter: SCCs mittels DFS 0:04:04 Invarianten von G 0:05:58 Lemma: Abgeschlossene SCCs von G sind SCCs von G 0:06:14 Repräsentation offener Komponenten 0:13:24 Beispiel 0:24:48 Zusammenfassung: SCC Berechnung 0:26:22 2-zusammenhängende Komponenten 0:29:06 Mehr DFS-basierte Linearzeitalgorithmen 0:31:56 Maximum Flows and Matching 0:33:06 Definitions: Network 0:34:38

01:28:28

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

Algorithmen 2, Vorlesung, WS18/19 ·

2018/11/02

06 | 0:00:00 Start 0:02:23 Anwendungen von DFS 0:06:45 DFS Nummerierung 0:09:51 Starke Zusammenhangskomponenten 0:17:07 Abstrakter Algorithmus 0:21:45 Auswirkungen einer neuen Kante e auf Gc, (Gc)s 0:28:56 Invarianten von Gc 0:34:11 Repräsentation offener Komponenten 0:46:37 Spezielle Priority Queues 0:51:13 Bucket Queues 0:57:25 Radix Heaps 1:20:25 Average case Analyse für MST

01:29:53

05: Algorithmen II, Vorlesung, WS 2018/19, 29.10.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/10/30

05 | 0:00:00 Start 0:00:08 Kürzeste Wege 0:02:50 Allgemeine Definition 0:03:01 Monotone ganzzahlige Prioritätslisten 0:04:23 Laufzeit Dijkstra mit Bucket-Queues 0:05:13 Radix-Heaps 0:07:25 Radix Heap: deleteMin 0:09:39 Beispiel 0:14:16 Laufzeit Dijkstra mit Radix-Heaps 0:16:21 Lineare Laufzeit für zufällige Kantengewichte 0:18:53 Änderung im Algorithmus für zufällige Kantengewichte 0:22:24 Analyse 0:28:29 All-Pairs Shortest Paths 0:33:59 Knotenpotenziale 0:40:25 Hilfsknoten 0:42:04

01:15:32

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

Algorithmen 2, Vorlesung, WS18/19 ·

2018/10/26

04 | 0:00:00 Start 0:00:04 Dijkstra's Algorithmus: Pseudocode 0:00:39 Laufzeit 0:01:30 Laufzeit im Durchschnitt 0:02:05 Lineare Laufzeit für dichte Graphen 0:02:21 Satz 1 0:11:50 Präfixminima einer Zufallsfolge 0:14:11 Monotone ganzzahlige Prioritätslisten 0:17:38 Bucket-Queue 0:20:18 Operationen 0:24:46 Laufzeit Dijkstra mit Bucket-Queues 0:26:07 Radix-Heaps 0:29:28 Definition 0:32:05 Radix-Heap_invariante 0:36:38 Radix Heap: deleteMin 0:39:34 Buckets 0:41:40 Lufzwit Dijkstra mit

01:16:20

03: Algorithmen II, Vorlesung, WS 2018/19, 22.10.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/10/25

03 | 0:00:00 Start 0:00:10 Algorithmics as Algorithm Engineering 0:01:26 Problem Instances 0:02:50 Example: Sorting Benchmark (Indy) 0:09:34 GraySort: 0:11:27 JouleSort 0:13:39 Applications that ""Change the world"" 0:22:09 Conclusion 0:24:17 More on experimental Methodology 0:29:48 Quality Criteria 0:36:53 Not here but important 0:37:57 The starting point 0:40:08 The Process 0:45:06 Of Risks and Opportunities 0:47:19 Fortgeschrittene Datenstrukturen 0:47:35

01:17:07

01: Algorithmen II, Vorlesung, WS 2018/19, 15.10.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/10/19

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt.

00:54:40

02: Algorithmen II, Vorlesung, WS 2018/19, 16.10.2018

Algorithmen 2, Vorlesung, WS18/19 ·

2018/10/19

02 |0:00:00 Start 0:01:39 Fortgeschrittene Datenstrukturen 0:03:10 Adressierbare Prioritätslisten 0:07:41 Grundlegende Datenstruktur 0:11:23 Pairung Heaps 0:23:14 Fibonacci Heaps 0:25:26 Repräsentation 0:26:22 deleteMin mit Union-by-Rank 0:27:23 Schnelles Union-by-Rank 0:30:49 Amortisierte Analyse von deleteMin 0:36:19 Schnelles Union-by-Rank 0:38:10 Warum ist maxRank logarithmisch? 0:40:10 Kaskadierende Schnitte 0:45:36 Auftritt Herr Fibonacci 0:51:52 Addressable Priority Queues: Mehr

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