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
All content for Algorithmen 2, Vorlesung, WS17/18 is the property of Karlsruher Institut für Technologie (KIT) and is served directly from their servers
with no modification, redirects, or rehosting. The podcast is not affiliated with or endorsed by Podjoint in any way.
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
25: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.02.2018
Algorithmen 2, Vorlesung, WS17/18
1 hour 27 minutes 53 seconds
7 years ago
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
Algorithmen 2, Vorlesung, WS17/18
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
