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/
Gesamtlänge aller Episoden: 1 day 16 hours 54 minutes
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...
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...
28: Algorithmen II, Übung, WS 2018/19, 29.01.2019
28 | 0:00:00 Start 0:00:08 Übung 11 0:02:04 Themenübersicht 0:02:49 in-place Multikey Quicksort 0:08:18 Partitionierung 0:20:32 Suche mit Suffix-Arrays 0:34:34 Ablauf 0:40:40 Zusammenfassung 0:43:06 LCP-Array 0:52:10 Schnelle Suche mit Suffix-Arrays 0:55:58 Redundante Vergleiche
27: Algorithmen II, Vorlesung, WS 2018/19, 28.01.2019
28 | 0:00:00 Start 0:00:05 Einleitung 0:00:28 Dominik Schreiber - SAT Solving and Automated Planning 0:00:41 Overview 0:01:51 The SAT Problem 0:03:39 SAT Solving 0:05:06 Parallel SAT Solving 0:09:30 Automated Planning 0:13:20 SAT-based Planning 0:17:44 Outlook: Future Research and Teaching 0:23:16 Sebastian Lamm - Distributed Connected Components 0:23:45 Connected Components and Applications 0:25:23 Sequential Algorithms 0:26:16 General Framework 0:29:04 All-Reduce (AR) - Algorithm 0:31:14...
26: Algorithmen II, Vorlesung, WS 2018/19, 22.01.2019
26 | 0:00:00 Start 0:00:05 LCP-Array 0:11:29 Textkompression 0:12:39 Lempel-Ziv Kompression (LZ) 0:30:17 Burrows-Wheeler-Transformation 0:35:48 Burrows-Wheeler-Transformation-- Rücktransformation 0:48:41 Was bringt die BWT? 0:50:52 BWT--Kompression 0:58:13 Suche in BWT 0:59:10 Backward Search 1:12:41 Wavelet Tree Example: Calculate Rank
25: Algorithmen II, Vorlesung, WS 2018/2019, 21.01.2019
25 | 0:00:00 Start 0:00:05 Suffix Array Konstruktionsalgorithmen 0:01:30 SA mit Präfix Verdopplung 0:04:27 Suffixtabellen 0:05:56 Ein erster Teile-und-Herrsche-Ansatz 0:07:22 Asymmetrisches Divide-and-Conquer 0:14:36 Rekursion 0:27:05 Least Significant Digit First Radix Sort 0:28:40 Stabiles Ganzzahliges Sortieren 0:30:16 Sortieren: Most Significant Digit Radix Sort 0:33:16 Suffix-Baum 0:36:08 Implementierung: Vergleichs-Operatoren 0:37:40 Verallgemeinerung: Differenzenüberdeckungen 0:46:22...
24: Algorithmen II, Vorlesung und Übung, WS 2018/19, 15.01.2019
24 | 0:00:00 Start 0:00:07 Stringology 0:02:36 Fragen zur letzten Vorlesung/ Wiederholung 0:08:51 Suffix-Baum 0:13:39 Alphabet-Modell 0:17:31 Suffix Array Konstruktionsalgorithmen 0:19:50 SA mit Präfix Verdopplung 0:36:14 Ein erster Teile-und-Herrsche-Ansatz 0:37:32 SA1 berechnen 0:39:42 Berechne SA0 aus SA1 0:41:12 Asymmetrisches Divide-and-Conquer 0:43:50 Übung 0:43:53 Online Algorithmen 0:46:32 kompetitiver Faktor 0:48:15 Ski Rental Problem 1:00:15 Doubling Strategie 1:01:09 Online Bidding
23: Algorithmen II, Vorlesung, WS 2018/19, 14.01.2019
23 | 0:00:00 Start 0:00:05 Competitive analysis 0:01:19 Atypical online problem: ski rental 0:01:50 Paging 0:02:33 Longest Forward Distance is optimal 0:02:50 Comparison of algorithms 0:03:28 Resource augmentation 0:03:41 Competitive ratio 0:03:53 Counting the faults of OPT 0:03:55 Randomized algorithms 0:04:04 Marking Algorithms 0:04:58 Why competitive analysis 0:06:30 Disadvantages of competitive analysis 0:08:35 Stringology 0:10:08 Strings Sortieren 0:19:15 Multikey Quicksort 0:23:21 Ohne...
22: Algorithmen II, Vorlesung, WS 2018/19, 08.01.2019
22 | 0:00:00 Start 0:00:33 2D Bereichssuche 0:01:30 Wavelet Tree 0:10:21 Bitvektoren 0:12:16 Onlinealgorithmen 0:17:10 Competitive analysis 0:22:46 online problem: ski rental 0:31:16 Paging 0:42:50 Comparison of algorithms 0:48:43 A general lower bound 0:55:01 Resource augmentation 0:57:08 Conservative algorithms 1:05:36 New results 1:07:48 Radomized algorithms 1:09:04 Three types of adversaries 1:11:34 Marking Algorithm 1:13:52 Competetive ratio of RMARK
21: Algorithmen II, Vorlesung, WS 2018/19, 07.01.2019
21 | 0:00:00 Start 0:00:05 12.3 Kleinste einschließende Kugel 0:13:24 Ähnliche Randomisierte Linearzeitalgorithmen 0:18:20 12.4 2D Bereichssuche 0:23:00 1D Bereichssuche 0:34:42 Wavelet Tree 0:43:30 Wavelet Tree Counting Query 0:47:19 Wavelet Tree Dominance Counting Query 1:09:08 Allgemeine Reporting Query 1:16:12 Mehr zu Bitvektoren 1:19:06 13 Onlinealgorithmen