28 Folgen

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

Algorithmen 2, Vorlesung, WS19/20 Karlsruher Institut für Technologie

    • Kurse

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: 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

    • 1 Std. 20 Min.
    • video
    27: Algorithmen II, Vorlesung, WS 2019/20, 03.02.2020

    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

    • 1 Std. 7 Min.
    • video
    26: Algorithmen II, Vorlesung, WS 2019/20, 28.01.2020

    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

    • 1 Std. 23 Min.
    • video
    25: Algorithmen II, Vorlesung, WS 2019/20, 27.01.2020

    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

    • 1 Std. 12 Min.
    • video
    24: Algorithmen II, Vorlesung, WS 2019/20, 21.01.2020

    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

    • 1 Std. 14 Min.
    • video
    23: Algorithmen II, Vorlesung, WS 2019/20, 20.01.2020

    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

    • 1 Std. 20 Min.

Top‑Podcasts in Kurse

Mehr von Karlsruher Institut für Technologie