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, WS18/19 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
29: Algorithmen II, Vorlesung, WS 2018/19, 04.02.2019
Algorithmen 2, Vorlesung, WS18/19
1 hour 22 minutes 51 seconds
6 years ago
29: Algorithmen II, Vorlesung, WS 2018/19, 04.02.2019
29 |
0:00:00 Starten
0:00:10 Inhaltsübersicht
0:03:02 Rolle der Algorithmik
0:03:43 Machine Learning macht das von selbst
0:17:02 Algorithm Theory
0:21:47 Graphenalgorithmen
0:22:20 Laufzeit
0:26:50 Satz 1
0:29:13 Monotone ganzzahlige Prioritätslisten
0:30:15 Bucket Queue
0:33:27 Analyse
0:34:30 All-Pair Shortest Paths
0:35:09 Knotenpotentiale
0:36:07 Algorithmus
0:37:46 Landmarks
0:38:33 Zusammenfassung Kürzeste Wege
0:39:47 Fortgeschrittene Datenstrukturen
0:40:21 Adressierbare Prioritätslisten
0:41:04 Grundlegende Datenstruktur
0:42:44 Pairing Heaps
0:47:06 Union by Rank
0:49:25 Zusammenfassung Datenstrukturen
0:50:45 Anwendung von DFS
0:51:16 Starke Zusammenhangskomponenten
0:54:00 Repräsentation offener Komponenten
0:57:08 Zusammenfassung SCC Berechnung
0:57:34 2 zusammenhängende Komponenten
0:57:47 Mehr DFS basierte Linearzeitalgorithmen
0:58:25 Maximum Flows and Matchings
0:58:31 Definitions: Network
0:59:24 Duality between Flows and Cuts
1:00:01 Applications
1:00:27 Algorithms 1956-now
1:04:27 Residual Graph
1:06:27 Ford Fulkerson Algorithm
1:07:34 Max Flow Min Gut theorem
1:07:41 Bad Example for Ford Fulkerson
1:08:35 Blocking Flows
1:08:58 Dinitz Algorithm
1:09:52 Blocking Flow Analysis
1:11:20 Maximum Cardinality Bipartite Matching
1:13:09 Preflow Push Algorithms
1:14:45 Level Function
1:16:04 FIFO Preflow push
1:17:17 Timings
1:17:24 Zusammenfassung Flows and Matchings
1:17:57 Randomisierte Algorithmen
1:18:11 Here Fast SOace Efficient Hashing
1:18:50 Externe Algorithmen
Algorithmen 2, Vorlesung, WS18/19
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
