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...
http://www.kit.edu/
30: Algorithmen II, Vorlesung, WS 2018/19, 05.02.2019
30 | 0:00:00 Start 0:00:20 Schrumpfgraph 0:02:39 Approximationsalgorithmen 0:03:29 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen 0:03:57 Viele kleine Jobs 0:04:52 Untere Schranken 0:05:10 Der Approximationsfaktor 0:07:17 Diese Schranke ist bestmöglich 0:07:49 Mehr zu Scheduling 0:07:58 Nichtapproximierbarkeit des Handlungsreisendenproblems 0:08:33 Hamilton Cycle 0:10:07 TSP mit Dreiecksungleichung 0:10:38 2-Approximstion durch minimalen Spannbaum 0:11:16 Pseudopolynomielle Algorithmen 0:12:26 Fully Polynomial Time Approximation Scheme 0:13:31 Fixed Parameter Algorithmen 0:14:49 VERTEX Cover 0:15:05 Fixed parameter tractable 0:16:32 Naive tiefenbeschränkte Suche 0:19:19 Kernbildung für Vertex Cover 0:21:45 Warum Parallelverarbeitung 0:22:58 Modell Nachrichtengekoppelte Parallelrechner 0:23:30 Kostenmodell für Nachrichtenaustausch 0:24:56 Warum kein Multicore-Modell? 0:26:18 Analyse paralleler Algorithmen 0:26:49 Pseudocode 0:27:41 Weniger ist mehr 0:28:10 Hyperwürfel 0:28:56 Hyperwürfelaulgorithmus 0:31:31 Paralleles Quicksort 0:32:00 Theoretiker-Parallelisierung 0:34:01 Onlinealgorithmen 0:34:29 Competitive analysis 0:35:19 A typical online problem: Ski rental 0:36:32 Paging 0:37:48 Comparison of algorithms 0:39:57 Discussion 0:42:00 Stringology 0:43:29 Strings Sortieren 0:47:55 Naives Pattern Matching 0:48:29 Knuth-Morris-Pratt 0:50:27 Volltextsuche von Langsam bis Superschnell 0:51:18 Invertierter Index 0:52:13 Etwas ""Stringology""-Notation 0:53:14 Suffixe Sortieren 0:53:56 Volltextsuche 0:54:45 Suffix-Baum 0:56:22 SA mit Präfix Verdopplung 0:58:05 Ein erster Teile-und-Herrsche-Ansatz 0:58:52 SA berechnen 1:00:42 Rekursion 1:03:52 LCP-Array 1:07:13 Datenkompression 1:08:51 Wörterbasierte Textkompression 1:09:59 Lempel-Ziv Kompression 1:11:29 Burrows Wheeler Transformation 1:14:47 Geometrische Algorithmen 1:15:37 Plane-Sweep-Algorithmen 1:18:08 Verallgemeinerung 1:21:33 Mehr Linienschnitt 1:22:51 Kleine einschließende Kugel