Algorithmen 2, Vorlesung, WS17/18
by Karlsruher Institut für Technologie (KIT)
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
Episodes
-
26: Algorithmen 2, Vorlesung, WS 2017/18, 06.02.2018
26 | 0:00:00 Starten 0:00:09 Seminar: Proofs from the book 0:04:48 Theses 2018: External, Parallel, and Distributed Sorting 0:11:12 Graph Generators 0:17:23 High Quality Hypergraph Partitioning 0:23:59 Kernbildung in der Praxis 0:38:53 Start Vorlesung 0:40:33 Randomisierte Algorithmen 0:43:44...
-
24: Algorithmen 2, Vorlesung, WS 2017/18, 30.01.2018
24 | 0:00:00 Starten 0:00:09 highest level preflow push 0:06:51 Example 0:13:50 Proof of Lemma 12 0:17:30 Claims 0:28:47 Heuristic Improvements 0:33:32 Experimental results 0:33:39 Timings: Random Graphs 0:36:16 Timings 0:36:40 Asymptotics 0:36:43 Zusammenfassung Flows und Matchings 0:49:53...
-
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…
more -
23: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 29.01.2018
23 | 0:00:00 Starten 0:07:03 Flüsse und Ford Fulkerson 0:08:39 Max Flow - Min Cut 0:12:42 Dinitz: Distanz Label 0:14:37 Dinitz: Schichtgraph 0:15:45 Dinitz: Blockierender Fluss 0:17:21 Dinitz: Blockierender Fluss Operationen 0:20:36 Dinitz: Kosten pro Blockierender Fluss 0:24:14 Dinitz: Laufzeit...
-
22: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 23.01.2018
22 | 0:00:00 Starten 0:00:09 Algorithms 1956-now 0:00:47 Residual Graph 0:02:25 A Bad Example for Ford Fulkerson 0:03:19 Blocking Flows 0:04:57 Dinitz Algorithm 0:06:11 Blocking Flows Analysis 0:07:39 Dinitz Analysis 0:17:14 Matching 0:20:28 Maximum Cardinality Bipartite Matching 0:23:44...
-
21: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 16.01.2018
21 | 0:00:00 Starten 0:00:18 Maximum Flows and Matchings 0:00:37 Definitions: Network 0:02:23 Flows 0:06:45 Applications 0:07:19 Applications in our Group 0:14:39 Option 1: linear programming 0:16:09 Algorithms 1956-now 0:19:49 Example 0:24:55 Residual Graph 0:31:33 Ford Fulkerson Algorithm…
more -
20: Algorithmen 2, Vorlesung, WS 2017/18, 15.01.2018
0 | 0:00:00 Starten 0:00:18 Anwendungen von DFS 0:05:13 Tiefensuchschema für G= (V,E) 0:09:29 Starke Zusammenhangskomponenten 0:12:53 SCCs generischer Algorithmus 0:20:12 Ziel: Effizienter Algorithmus 0:27:20 Invarianten 0:39:53 Invarianten von Gc 0:53:47 traverseNonTreeEdge(v,w) 0:56:47...
-
19: Algorithmen 2, Vorlesung, WS 2017/18, 08.01.2018
19 | 0:00:00 Starten 0:00:09 Erinnerung 0:21:19 Radix-Heaps 0:35:25 Radix-Heap-Invariante 0:40:45 Radix Heap: deleteMin 0:45:28 Kosten der deleteMin-Operationen 1:07:04 all-pair-shortest-path (APSP) 1:23:03 Definition der Potentiale
-
18: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 19.12.2017
18 | 0:00:00 Starten 0:00:09 Fortgeschrittene Graphenalgorithmen 0:04:34 Allgemeine Definition 0:06:17 Kante relaxieren 0:07:11 Dijkstra's Agorithmus 0:08:40 Beispiel 0:09:00 Laufzeit 0:14:55 Lineare Laufzeit für dichte Graphen 0:26:30 Präfixminima einer Zufallsfolge 0:27:32 Monotone ganzzahlige...
-
17: Algorithmen 2, Vorlesung, WS 2017/18, 18.12.2017
17 | 0:00:00 Starten 0:00:46 Aufgabenvarianten 0:01:16 Verteilte Eigenschaften 0:01:30 Theoretiker-Quicksort 0:06:08 Fortgeschrittene Datenstrukturen 0:10:27 Adressierbare Prioritätslisten 0:34:55 Adressierbare Prioritätslisten: Anwendungen 0:38:27 Grundlegende Datenstruktur 0:39:29 Wälder...
-
16: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 12.12.2017
16 | 0:00:00 Starten 0:00:09 Parallele Reduktion: Algorithmus 0:05:38 Analyse paralleler Programme 0:14:10 Parallele Präfixsummen 0:44:36 Übung 7 0:45:28 Expertenauswahl 0:49:41 Parallelverarbeitung 0:52:09 PRAM 0:54:56 Verbindungsnetzwerke 1:01:33 Nachrichtenaustausch: Pipelining 1:06:31...
-
15: Algorithmen 2, Vorlesung, WS 2017/18, 11.12.2017
15 | 0:00:00 Starten 0:00:33 Überblick 0:01:07 Problemstellung 0:04:06 Auswahl von Experten 0:05:07 Auswahl von Experten: der deterministische Weighted Majority Algorithm (wma) 0:07:49 Qualität von WMA 0:09:31 Beweis 0:16:48 Verallgemeinerte Problemstellung 0:18:17 Randomisiert: randWMA 0:21:13...
-
14: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 05.12.2017
14 | 0:00:00 Starten 0:01:57 LRU - Beispiel 0:05:27 LRU ist K- Kompetitiv 0:06:22 LRU ist K-Kompetitive – Beweisskizze 0:15:44 Resource Augmentation: (h,k)-Seitenwechsel 0:24:12 Randomisiert 0:25:14 Randomisierte Onlinealgorithmen 0:26:09 Widersacher: verschieden miese Typen 0:30:04...
-
13: Algorithmen 2, Vorlesung, WS 2017/18, 04.12.2017
13 | 0:00:00 Starten 0:02:50 Eine Reihe von Beispiele 0:05:39 Beispiel Job-Scheduling 0:07:07 Beispiel Skiausleihe 0:09:30 Speicherverwaltung 0:12:04 Auswahl von Experten 0:14:23 Beispiel Selbstorganisierende Datenstrukturen 0:15:12 Online-Algorithmus 0:19:55 Competitive Analysis 0:24:45...
-
12: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 28.11.2017
12 | 0:00:00 Starten 0:00:09 Orthogonal range searching 0:01:01 Orthogonal range searching - 1D 0:07:03 Orthogonal range searching - 2D 0:17:40 Wavelet Tree Dominance Reporting Query 0:17:54 Reduktion auf 1..n x 1..n 0:18:18 Beispiel 0:19:54 Wavelet Tree 0:22:18 Beispiel 0:24:30 Wavelet Tree...
-
11: Algorithmen 2, Vorlesung, WS 2017/18, 27.11.2017
11 | 0:00:00 Starten 0:06:23 Typische Fragestellungen 0:15:56 Streckenschnitt: Naiver Algorithmus 0:19:04 Idee: Plane-Sweep-Algorithmus 0:24:57 Plane-Sweep für orth. Streckenschnitt 0:29:03 Verallgemeinerung - Grundidee 0:40:56 Verallgemeinerung - Beispiel 0:49:50 Überlappungen finden 0:52:30 2D...
-
10: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 21.11.2017
10 | 0:00:00 Starten 0:00:21 Wavelet Tree Example: Calculate Rank 0:09:48 Huffman-shaped Wavelet Tree 0:12:42 Practical Performance of FM-Index 0:14:54 Succinct Data Structures 0:17:09 Succinct representation of trees 0:19:34 Child operation in detail 0:22:09 Succinct representation of trees (2)...
-
09: Algorithmen 2, Vorlesung, WS 2017/18, 20.11.2017
09 | 0:00:00 Starten 0:00:18 Range minimum queries (RMQs) 0:00:43 Overview 0:01:05 O(n), Olog(n)-solution 1 0:01:18 O(nlogn), O solution 2 0:01:38 O(nlog(logn)), O(1) solution 0:02:17 O(n),O(1) solution 0:02:33 LCA & +1RMQ 0:02:51 O(n),O(1) solution 0:08:08 LCA& +1RQM 0:16:49 (O(n),O(1)) solution...
-
08: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 14.11.2017
08 | 0:00:00 Starten 0:00:34 Verlustfreie Textkompression 0:01:25 Theorie verlustfreier Textkompression 0:10:57 Wörterbuchbasierte Textkompression 0:12:58 Lempel-Ziv Kompresssion (LZ) 0:17:44 Naive LZ Dekompression 0:20:15 LZ- Verfeinerungen 0:21:39 LCP zwischen beliebigen Suffixen 0:23:44 Range...
-
07: Algorithmen 2, Vorlesung, WS 2017/18, 13.11.2017
07 | 0:00:00 Starten 0:00:22 Suffix-Baum 0:01:20 Alphabet-Modell 0:02:41 Geordnetes ganzzahliges Alphabet 0:04:39 Verallgemeinerung: Lexikographische Namen 0:05:31 Ein erster Teile-und-Herrsche-Ansatz 0:13:30 Asymmetrisches Divide-and-Conquer 0:18:09 Rekursion, Beispiel 0:25:39 Least Significant...
-
06: Algorithmen 2, Vorlesung, WS 2017/18, 07.11.2017
06 | 0:00:00 Starten 0:00:32 4 Stringology (Zeichenkettenalgorithmen) 0:04:16 Strings Sortieren 0:15:40 Strings Sortieren - Laufzeitanalyse 0:18:27 Naives Pattern Matching 0:55:49 Volltextsuche von langsam bis Superschnell 1:04:37 Suffixtabellen 1:05:37 Etwas ""Stringology""-Notation 1:07:03...
-
05: Algorithmen 2, Vorlesung und Übung, WS 2017/18, 06.11.2017
05 | 0:00:00 Starten 0:00:34 Turing-Reduzierbarkeit 0:02:47 Pseudopolynomielle Laufzeit 0:05:58 Zwei kleine Warnungen 0:07:55 KNAPSACK Suchproblem 0:10:22 KNAPSACK: Codierungen der Eingabe 0:11:47 Schwere des KNAPSACK Suchproblems 0:12:41 KNAPSACK: pseudopolynomielle Laufzeit 0:22:08 Polynomielle...
-
04: Algorithmen 2, Vorlesung, WS 2017/18, 30.10.2017
04 | 0:00:00 Starten 0:01:07 Suchprobleme 0:04:15 Approximation bei Suchprobleme 0:07:10 Approximation bei Zählprobleme 0:08:51 Job Scheduling: Aufgabenstellung 0:13:14 Naheliegender Algorithmus: listScheduling 0:20:19 Eigenschaften des Algorithmus 0:26:55 Approxiamtionsfaktor 0:28:43…
more -
03: Algorithmen 2, Vorlesung, WS 2017/18, 24.10.2017
03 | 0:00:00 Starten 0:00:10 Kapitel: Randomisierte Algorithmen 0:00:45 Überblick 0:02:44 Erdos-Renyi-Zufallsgraphen 0:04:59 ER-Graphen: einfache Beobachtungen 0:11:05 Manchmal interessieren sehr große n und asymptotische Eigenschaften 0:15:21 ER-Graphen:Durschmesser <=2 0:21:51...
-
02: Algorithmen 2, Vorlesung, WS 2017/18, 23.10.2017
02 | 0:00:00 Starten 0:01:08 Erinnerung an W-Theorie 0:02:22 Randomisierter Quicksort 0:04:34 randQS: Anzahl Vergleiche 0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt. 0:28:25 Chernoff-Schranken 0:29:04 Einfache Schranken 0:32:19 Chernoff-Schranken 0:38:03 Chernoff-Schranken: Beweis von Teil 1...
-
01: Algorithmen 2, Vorlesung, WS 2017/18, 17.10.2017
01 | 0:00:00 Starten 0:00:10 Kapitel: Randomisierte Algorithmen 0:01:10 Überblick 0:01:38 Sichtweisen für randomisierte Algorithmen 0:03:33 Fundamentale Änderung 0:04:03 Beispiel: Randomisierter Quicksort 0:05:32 Zufallsvariablen überall 0:05:49 Errinerung an W-Theorie 0:09:32 Standardbeispiel:...
About this show
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
Hosted by
Karlsruher Institut für Technologie (KIT)
Categories