Algorithmen 2, Vorlesung, WS19/20

08 |

0:00:00 Start

0:00:05 Maximum Flows and Matchings

0:06:49 Computer Blocking Flows

0:21:08 Dinitz Analysis

0:30:00 Übung 3

0:31:22 Kürzeste-Wege-Suche

0:37:28 Dijkstras Algorithmus

0:40:20 Bidirektionale Suche

0:46:21 A*-Suche

1:01:34 Starke Zusammenhangskomponenten

1:10:16 Floys Warshall: SCC als Speedup Technik

07 |

0:00:00 Start

0:02:01 Maximum Flows and Matchings

0:05:38 Network

0:07:41 Flows

0:12:54 s-t Cuts

0:14:33 Anwendung

0:31:49 Lösungsmöglichkeiten

0:45:39 Beispiel

0:49:42 Residual Graph

0:51:51 Augmenting Paths

0:53:19 Ford Fulkerson Algorithm

0:54:44 Ford Fulkerson - Correctness

1:04:19 Max-Flow-Min-Cut theorem

1:13:34 Blocking Flows

1:16:04 Dinitz Algorithm

1:18:45 Dinitz - Correctness

1:19:32 Beispiel

06 |

0:00:00 Start

0:00:05 Rückblick

0:07:15 Invarianten von Gc

0:12:59 Repräsentation offener Komponenten

0:27:34 Beispiel

0:37:43 2-zusammenhängende Komponenten

0:40:35 Übung

0:41:17 Spezielle Priority Queues

0:52:56 Radix Heaps

Wegen technischer Probleme konnten die letzten 45 Minuten der Vorlesung nicht aufgezeichnet werden.

05|

0:00:00 Start

0:00:05 Definition msd(a,b)

0:00:07 Lineare Laufzeit für zufällige Kantengewichte

0:00:39 All-Pairs Shortest Paths

0:05:32 Knotenpotentiale

0:09:18 Hilfsknoten

0:10:58 Definition der Potentiale

0:13:29 Algorithmus

0:14:47 Laufzeit

0:16:45 Distanz zu einem Zielknoten

0:21:11 Ideen für Routenplanung

0:27:24 Bidirektionale Suche

0:30:21 A*-Suche

0:35:29 Benötigte Eigenschaften von f(v)

04 |

0:00:00 Start

0:01:28 Binomialbäume

0:02:14 Kaskadierende Schnitte

0:02:39 Kürzeste Wege

0:04:43 Monotone

0:06:51 Bucket-Queue

0:07:18 Operationen

0:11:06 Radix-Heaps

0:13:56 Definition msd(a,b)

0:16:13 Radix-Heap-Invariante

0:18:44 Vergleich: Buckets-Queues und Radix-Heaps

0:19:33 Radix Heap: deleteMin

0:22:56 Buckets bei Änderung von d*

0:26:15 Kosten der deleteMin-Operationen

0:26:42 Laufzeit Dijkstra mit Radix-Heaps

0:27:23 Lineare Laufzeit für zufällige Kantengewichte

0:29:04 Änderung im Algorithmus für zufällige Kantengewichte

0:32:19 Analyse

03 |

0:00:00 Start

0:00:05 2 Fortgeschrittene Datenstrukturen

0:00:27 2.1 Adressierbare Prioritätslisten

0:01:45 Wälder Bearbeiten

0:02:10 Pairing Heaps

0:03:06 Fibonacci Heaps

0:05:01 Amortisierte Analyse von deleteMin

0:08:48 Warum ist maxRank logarithmisch? – Binomialbäume

0:11:41 Kaskadierende Schnitte

0:17:29 Auftritt Herr Fibonacci

0:18:57 Beweis:

0:23:56 Addressable Priority Queues: Mehr

0:27:47 Fortgeschrittene Graphenalgorithmen; 3 Kürzeste Wege

0:29:56 Allgemeine Definitionen

0:33:14 Dijkstra's Algorithmus: Pseudocode

0:35:35 Beispiel

0:37:04 Laufzeit

0:41:31 Laufzeit im Durchschnitt

0:49:55 Lineare Laufzeit für dichte Graphen

0:59:50 Präfixminima einer Zufallsfolge

1:02:15 Monotone ganzzahlige Prioritätslisten

1:08:41 Bucket-Queue

1:10:47 Operationen

1:13:53 Laufzeit Dijkstra mit Bucket-Queues

01 |

0:00:00 Start

0:00:10 Materialen

0:06:14 Inhaltsübersicht

0:11:21 Zusammenfassung – Rolle der Algorithmik

0:12:21 ""Machine Learning macht das von selbst?""

0:15:19 1 Algorithm Engineering

0:23:46 Gaps between Theory & Practice

0:28:21 Algorithmics as Algorithm Engineering

0:34:02 Bits of History

0:40:56 Realistic Models

0:45:06 Design

0:47:53 Analysis

0:50:01 Implementation

0:53:38 Experiments

0:57:04 Algorithm Libraries – Challenges

1:03:03 Problem Instances

1:06:58 Example: Sorting Benchmark

1:11:57 JouleSort

1:13:11 Applications that ""Change the World""

1:18:45 Conclusion

02 |

0:00:00 Start

0:00:55 Experimental Methodology

0:07:03 Quality Criteria

0:16:12 Not Here but Important

0:22:41 The Starting Point

0:24:01 The Process

0:29:36 Of Risks and Opportunities

0:34:03 Fortgeschrittene Datenstrukturen

0:36:16 Adressierbare Prioritätenlisten

0:44:00 Grundlegende Datenstruktur

0:48:01 Pairing Heaps

1:06:25 Fibonacci Heaps