28 episodes
Algorithmen 2, Vorlesung, WS19/20 Karlsruher Institut für Technologie (KIT)
-
- Education
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
28: Algorithmen II, Vorlesung, WS 2019/20, 04.02.2020
28|
0:00:00 Start
0:00:11 Externes binäres Mischen
0:13:06 8 Approximationsalgorithmen
0:26:45 9 Fixed-Parameter-Algorithmen
0:38:52 10 Parallele Algorithmen
0:52:22 11 Stringology
0:56:36 12 Geometrische Algorithmen
1:14:40 13 Onlinealgorithmen -
- video
27: Algorithmen II, Vorlesung, WS 2019/20, 03.02.2020
27|
0:00:00 Start
0:03:24 Fortgeschrittene Datenstrukturen
0:06:37 Pairing Heaps
0:15:49 Laufzeit im Durchschnitt
0:21:31 Bucket-Queue
0:37:07 Starke Zusammenhangskomponenten
0:44:05 Zusammenfassung: SCC Berechnung
0:53:28 Residual Graph
1:02:41 Randomisierte Algorithmen -
- video
26: Algorithmen II, Vorlesung, WS 2019/20, 28.01.2020
26|
0:00:00 Start
0:02:19 The Document Retrieval Problem
0:03:30 Top-k Document Retrieval
0:04:39 Important Query Types
0:05:51 Inverted Indexes
0:09:13 Suffix Arrays
0:11:10 Warmup: Document Listing
0:14:24 Top-k Retrieval
0:15:21 Example
0:21:58 Example Space Usage from [LG17]
0:24:29 Range Minimum Query
0:25:12 2D-Weighted Range Queries
0:34:43 Range Minimum Query Problem
0:49:25 Comparison with other Implementations
0:50:41 (Hyper)Graph Partitioning
0:51:25 Graphs and Hypergraphs
0:54:48 Applications
0:57:08 Successful Heuristic: Multilevel Paradigm
1:09:41 Fiduccia-Mattheyses Algorithm
1:12:28 Adaptive Flow Iterations
1:13:57 Hypergraph Flow Network
1:16:56 Optimized Flow Problem Modeling Approach
1:19:22 Most Balanced Minimum Cut
1:21:10 Experiments: Connectivity Optimization -
- video
25: Algorithmen II, Vorlesung, WS 2019/20, 27.01.2020
25|
0:00:00 Start
0:00:54 Datenkompression
0:01:52 Verlustfreie Textkompression
0:03:14 Wörterbuchbasierte Textkompression
0:05:11 Lempel-Ziv Kompression
0:06:22 Beispiel
0:21:16 Burrows Wheeler Transformation
0:47:23 Backward Search
0:57:44 Wavelet Tree Example: Calculate Rank -
- video
24: Algorithmen II, Vorlesung, WS 2019/20, 21.01.2020
23|
0:00:00 Start
0:00:09 Suffixtabellenkonstruktion: Zusammenfassung
0:01:49 Suche in Suffix Arrays
0:07:08 LCP-Array
0:27:51 Suffix-Baum aus SA und LCP
0:34:16 Datenkompression
0:36:49 Verlustfreie Textkompression
0:46:48 10.Übung
0:47:28 Themenübersicht
0:47:57 in-place Multikey Quicksort
0:58:11 Suche mit Suffix-Arrays
1:03:55 LCP-Array -
- video
23: Algorithmen II, Vorlesung, WS 2019/20, 20.01.2020
23 |
0:00:00 Start
0:00:05 Suffix Array Konstruktionsalgorithmen
0:00:51 SA mit Präfix Verdopplung
0:11:39 Linear Work Suffix Array Construction
0:13:50 SA berechnen
0:17:21 Asymmetrisches Divide-and-Conquer
0:18:38 Rekursion Beispiel
0:34:17 Least Significant Digit First Radix Sort
0:40:22 Implementierung
0:41:42 Verallgemeinerung: Differenzenüberdeckungen
0:46:09 COBS: A Compact Bit-Sliced Signature Index
0:47:28 Motivation / Applications
1:14:27 COBS: Disk Access Pattern
Top Podcasts In Education
More by Karlsruher Institut für Technologie