26 Folgen
Algorithmen 2, Vorlesung, WS17/18 Karlsruher Institut für Technologie (KIT)
-
- Bildung
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.
Literaturhinweise:
- K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox
- K. Mehlhorn, S. Naeher: The LEDA Platform of Combinatorial and Geometric Computing Topic: Algorithm Engineering, Flows, Geometrie
- R. K. Ahuja, T. L. Magnanti, J.B. Orlin: Network Flows
- M. de Berg, M. van Kreveld, M. Overmars, O. C. Schwarzkopf: Computational Geometry: Algorithms and Applications
- G. Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press
- R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.
Dozenten: Prof. Dr. Peter Sanders, Dr. Christian Schulz, Dr. Simon Gog, M.Sc. Michael Axtmann | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik
Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu
-
- video
26: Algorithmen 2, Vorlesung, WS 2017/18, 06.02.2018
26 |
0:00:00 Starten
0:00:09 Seminar: Proofs from the book
0:04:48 Theses 2018: External, Parallel, and Distributed Sorting
0:11:12 Graph Generators
0:17:23 High Quality Hypergraph Partitioning
0:23:59 Kernbildung in der Praxis
0:38:53 Start Vorlesung
0:40:33 Randomisierte Algorithmen
0:43:44 Approximationsalgorithmen
0:49:41 Online Algorithmen -
- video
24: Algorithmen 2, Vorlesung, WS 2017/18, 30.01.2018
24 |
0:00:00 Starten
0:00:09 highest level preflow push
0:06:51 Example
0:13:50 Proof of Lemma 12
0:17:30 Claims
0:28:47 Heuristic Improvements
0:33:32 Experimental results
0:33:39 Timings: Random Graphs
0:36:16 Timings
0:36:40 Asymptotics
0:36:43 Zusammenfassung Flows und Matchings
0:49:53 Sortieren durch Mehrwege-Mischen
0:50:00 Das Sekundärspeichermodell
0:51:59 Externe Stapel
1:08:30 Externes (binäres) Mischen
1:08:56 Run Formation
1:10:11 Sortieren durch Externes Binäres Mischen
1:12:01 Zahlenbeispiel
1:14:11 Mehrwegmischen
1:20:53 Mehr zu externem Sortieren
1:21:31 Externe Prioritätslisten
1:21:57 Minimale Spannbäume
1:23:36 Externe MST-Berechnung
1:24:14 Beispiel, Sibeyn's algorithm
1:24:19 Mehr zu externen Algorithmen - Basic Toolbox -
- video
25: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.02.2018
25 |
0:00:00 Starten
0:00:15 Highest Level Preflow Push
0:00:55 Claims
0:01:07 Proof of Lemma 12
0:02:32 Claims
0:12:13 Anfang der Übung
0:12:27 Themenübersicht
0:13:08 Preflow-push Algorithmus
0:20:44 FIFO preflow-push Algorithmus
0:42:37 Matching
0:44:31 Bipartite-Matching
0:46:40 Speichermodell
0:48:26 Latenzen
0:49:47 I/O-efffizientes Design
0:51:12 Blockgrößen
0:55:33 Externes Sortieren
1:02:00 Strings Sortieren
1:02:56 Stringology (Zeichenkettenalgorithmen)
1:05:15 Suche in Suffix Arrays
1:05:21 LCP-Array: Berechnung
1:06:18 Datenkompression
1:06:23 Verlustfreie Textkompression
1:06:34 Lempel-Ziv Kompression (LZ)
1:07:33 Range minimum queries (RMQs)
1:07:44 Overview
1:09:43 Burrows-Wheeler-Transformation
1:10:36 Wavelet Tree Example: Calculate Rank
1:12:39 O(n) space /constant query time
1:13:19 Typische Fragenstellungen
1:14:28 Datenstrukturen für Punktmengen
1:14:40 Plane-Sweep-Algorithmen
1:15:57 Konvexe Hülle
1:16:04 Kleinste einschließende Kugel
1:16:37 2D Bereichssuche
1:16:48 Reduktion
1:17:10 Wavelet Tree Dominance Counting Query
1:18:08 Orthogonal range searching
1:18:44 Adressierbare Prioritätslisten
1:18:56 Grundlegende Datenstrukturen
1:19:27 Pairing Heaps
1:19:52 Binomialbäume
1:20:13 Kaskadierende Schnitte
1:20:27 Fortgeschrittene Graphenalgorithmen
1:20:42 Allgemeine Definition
1:21:25 Monotone ganzzahlige Prioritätslisten
1:21:59 Bucket-Queue
1:22:20 Operationen
1:23:25 All-Pairs Shortest Paths
1:23:49 Knotenpotentiale
1:24:23 Ideen für Routenplanung
1:24:42 Distanz zu einem Zielknoten t
1:25:15 Starke Zusammenhangskomponenten
1:26:52 Maximum Flows and Matchings -
- video
23: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 29.01.2018
23 |
0:00:00 Starten
0:07:03 Flüsse und Ford Fulkerson
0:08:39 Max Flow - Min Cut
0:12:42 Dinitz: Distanz Label
0:14:37 Dinitz: Schichtgraph
0:15:45 Dinitz: Blockierender Fluss
0:17:21 Dinitz: Blockierender Fluss Operationen
0:20:36 Dinitz: Kosten pro Blockierender Fluss
0:24:14 Dinitz: Laufzeit
0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network
0:30:24 Maximum Cardinality Bipartite Matching
0:31:35 Preflow-Push Algorithms
0:34:00 Level Function
0:36:49 Procedure genericPreflowPush
1:21:53 Searching for Eligible Edges
1:23:50 Satz 11. Arbitrary Preflow Push finds a maximum flow in time O (n²m) -
- video
22: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 23.01.2018
22 |
0:00:00 Starten
0:00:09 Algorithms 1956-now
0:00:47 Residual Graph
0:02:25 A Bad Example for Ford Fulkerson
0:03:19 Blocking Flows
0:04:57 Dinitz Algorithm
0:06:11 Blocking Flows Analysis
0:07:39 Dinitz Analysis
0:17:14 Matching
0:20:28 Maximum Cardinality Bipartite Matching
0:23:44 Disadvantage of augmenting paths algorithms
0:45:52 Übung 11
0:46:25 Kürzeste-Wege-Suche
0:48:11 Suche in Graphen
0:51:22 Dijikstras Algorithmus
0:53:19 Bidirectionale Suche
1:00:03 A*-Suche -
- video
21: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 16.01.2018
21 |
0:00:00 Starten
0:00:18 Maximum Flows and Matchings
0:00:37 Definitions: Network
0:02:23 Flows
0:06:45 Applications
0:07:19 Applications in our Group
0:14:39 Option 1: linear programming
0:16:09 Algorithms 1956-now
0:19:49 Example
0:24:55 Residual Graph
0:31:33 Ford Fulkerson Algorithm
0:43:36 Übung
0:44:35 SCC
0:55:06 Floyd Warshall: SCC als Speedup Technik
Top‑Podcasts in Bildung
Mehr von Karlsruher Institut für Technologie