26 episodes
Algorithmen 2, WS2016/17, Vorlesung 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
Algorithmen II, Vorlesung, WS 2016/17, 07.02.2017, 26
26 |
0:00:00 Starten
0:01:13 Fortgeschrittene Graphenalgorithmen: 2 Kürzeste Wege
0:02:31 Monotone ganzzahlige Prioritätslisten
0:03:05 Radix-Heaps
0:04:38 All-Pairs Shortest Paths
0:06:18 3 Anwendungen von DFS
0:08:27 Algorithms 1956-now
0:11:39 Preflow-Push Algorithms
0:13:38 5 Externe Algorithmen
0:15:04 6 Fixed-Parameter-Algorithmen
0:16:16 Fixed parameter tractable
0:16:49 Beispiel: VERTEX COVER
0:17:46 Naive tiefenbeschränkte Suche
0:18:38 7 Parallele Algorithmen
0:18:41 Warum Parallelverarbeitung
0:19:30 Kostenmodell für Nachrichtenaustausch
0:20:12 7.2 Beispiel: Assoziative Operationen (=Reduktion)
0:21:17 7.3 Sortieren
0:21:59 8 Stringology (Zeichenkettenalgorithmen)
0:22:25 Knuth-Morris-Pratt (1977)
0:27:42 9 Geometrische Algorithmen
0:27:54 9.1 Streckenschnitt (line segment intersection)
0:28:42 Verallgemeinerung
0:29:38 9.3 Kleinste einschließende Kugel
0:30:08 9.4 2D Bereichssuche (range search)
0:32:55 10 Onlinealgorithmen
0:33:33 Competitive analysis -
- video
Algorithmen II, Vorlesung und Übung, WS 2016/17, 31.01.2017, 25
25 |
0:00:00 Starten
0:00:24 Wavlet Tree
0:08:46 Allgemeine Reporting Query
0:09:02 Bitvektoren
0:15:34 Suffix Array
0:15:45 Backward Search
0:20:37 Wavelet Tree Example: Calculate Rank
0:24:21 Index size comparison
0:26:55 Beginn Übung 13
0:27:01 Themenübersicht
0:28:27 Geometrische Algorithmen
0:32:55 Geometrische Methoden
0:35:13 Sweep-Line
0:39:04 One-Dimensional Problem
0:39:26 Skyline
0:56:58 Linienschnitt
1:02:03 Punktorientierung -
- video
Algorithmen II, Vorlesung, WS 2016/17, 25.01.2017, 24
24 |
0:00:00 Starten
0:00:14 Verallgemeinerung
0:10:21 Überlappungen finden
0:11:52 Platzverbrauch
0:12:45 Mehr Linienschnitt
0:13:34 9.2 2D Konvexe Hülle
0:17:35 Graham's Scan
0:23:22 3D Konvexe Hülle
0:25:05 9.3 Kleinste einschließende Kugel
0:31:29 Kleinste einschließende Kugel - Korrektheitm
0:35:57 Kleinste einschließende Kugel - Analyse
0:49:17 9.4 2D Bereichssuche
0:52:14 1D Bereichssuche
0:58:43 Reduktion auf 1...n x 1...n
1:01:19 Beispiel
1:02:05 Walvelet Tree -
- video
Algorithmen II, Übung und Vorlesung, WS 2016/17, 24.01.2017, 23
23 |
0:00:00 Starten
0:00:07 Übung 12 - Online Algorithmen
0:02:44 Grundlagen
0:04:19 Gütemaß
0:05:21 Ski Rental Problem
0:06:46 Randomisierte Ski Rental Strategie
0:18:02 Doubling Strategie
0:18:52 Online Bidding
0:40:30 Zusammenfassung
0:41:39 Vorlesung: Kapitel 9 - Geometrische Algorithmen
0:45:17 Elementare Geometrische Objekte
0:49:22 Typische Fragestellungen
0:53:29 Verweissensitive Grafik (Wikipedia)
0:54:30 Datenstrukturen für Punktemengen
0:54:42 Mehr Fragestellungen
0:59:47 9.1 Streckenschnitt (line segment intersection)
1:01:02 Streckenschnitt: Anwendungen
1:01:44 Streckenschnitt: Naiver Algorithmus
1:02:18 Streckenschnitt: Untere Schranke
1:04:17 Idee: Plane-Sweep-Algorithmen
1:04:54 Plane-Sweep für orth. Streckenschnitt
1:10:02 Analyse orth. Streckenschnitt
1:12:03 Verallgemeinerung - aber erstmal ""nicht ganz""
1:12:55 Verallgemeinerung - Grundidee
1:16:48 Verallgemeinerung - Korrektheit
1:17:46 Verallgemeinerung - Implementierung
1:23:05 Verallgemeinerung - Beispiel
1:24:05 Verallgemeinerung - Analyse -
- video
Algorithmen II, Vorlesung, WS 2016/17, 18.01.2017, 22
22 |
0:00:00 Starten
0:00:42 13 Onlinealgorithmen
0:05:35 Examples
0:08:09 Competitive analysis
0:09:19 A typical online problem: ski rental
0:11:31 Upper bound for ski rental
0:14:33 Lower bound for ski rental
0:18:07 Paging
0:20:16 Definitions
0:21:49 Paging algorithms
0:25:11 Longest Forward Distance is optimal
0:27:34 Using the claim
0:29:01 Proof the claim
0:29:44 Comparison of algorithms
0:34:33 A general lower bound
0:38:53 Resource augmentation
0:40:14 Conservative algorithms
0:43:26 Competitive ratio
0:46:50 Counting the faults of OPT
0:47:32 Conclusion
0:48:30 Competitive analysis
0:49:57 Notes
0:51:02 New results
0:54:25 Randomized algorithms
0:55:38 Three types of adversaries
1:00:46 Markig Algorithm
1:04:28 Analysis of REMARk
1:06:21 Lower bound for OPT
1:07:42 Discussion
1:08:50 Why competitive analysis?
1:16:24 Disadvantages of competetive analysis -
- video
Algorithmen II, Vorlesung und Übung, WS 2016/17, 11.01.2017, 21
21 |
0:00:00 Starten
0:00:07 Burrows-Wheeler-Transformation
0:12:23 Datenkompression
0:18:42 Verlustfreie Textkompression
0:30:39 Wörterbuchbasierte Textkompression
0:33:02 Lempel-Ziv Kompression
0:33:45 Naive Lempel-Ziv Kompression
0:43:15 Naive LZ Dekompression
0:45:08 LZ Beispiel
0:45:16 LZ-Verfeinerung
0:46:37 Begin Übung 11
0:48:29 Suche mit Suffix-Arrays (1)
0:56:41 LCP-Array
1:03:46 Schnelle Suche mit Suffix-Arrays
1:10:29 Suche mit Suffix-Arrays (2)
Top Podcasts In Education
More by Karlsruher Institut für Technologie