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 (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
    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 Bildung

Eine Stunde History - Deutschlandfunk Nova
Eine Stunde History - Deutschlandfunk Nova
Deutschlandfunk Nova
Gehirn gehört - Prof. Dr. Volker Busch
Gehirn gehört - Prof. Dr. Volker Busch
Prof. Dr. Volker Busch
Easy German: Learn German with native speakers | Deutsch lernen mit Muttersprachlern
Easy German: Learn German with native speakers | Deutsch lernen mit Muttersprachlern
Cari, Manuel und das Team von Easy German
Quarks Science Cops
Quarks Science Cops
Quarks
G Spot - mit Stefanie Giesinger
G Spot - mit Stefanie Giesinger
Stefanie Giesinger & Studio Bummens
ZEIT Sprachen – English, please!
ZEIT Sprachen – English, please!
ZEIT ONLINE

Mehr von Karlsruher Institut für Technologie

Grundbegriffe der Informatik, Vorlesung, WS18/19
Grundbegriffe der Informatik, Vorlesung, WS18/19
Karlsruher Institut für Technologie (KIT)
Forschungspodcast »Selbstbewusste KI«
Forschungspodcast »Selbstbewusste KI«
Karlsruher Institut für Technologie (KIT)
Theoretische Grundlagen der Informatik, Vorlesung, WS19/20
Theoretische Grundlagen der Informatik, Vorlesung, WS19/20
Karlsruher Institut für Technologie (KIT)
Algorithmen 1, SS2019, Vorlesung
Algorithmen 1, SS2019, Vorlesung
Karlsruher Institut für Technologie (KIT)
Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019
Numerische Mathematik für die Fachrichtungen Informatik und Ingenieurwesen, Vorlesung, SS2019
Karlsruher Institut für Technologie (KIT)
Ethik heute. Fehlt uns ein Wertekompass?
Ethik heute. Fehlt uns ein Wertekompass?
Karlsruher Institut für Technologie (KIT)