Algorithmen 2, Vorlesung, WS19/20

18 |

0:00:00 Start

0:00:05 12.1 Streckenschnitt

0:09:33 12.2 2D Konvexe Hülle

0:19:37 3D Konvexe Hülle

0:24:19 12.3 Kleinste einschließende Kugel

0:44:00 Ähnliche Randomisierte Linearzeitalgorithmen

0:48:41 12.4 2D Bereichssuche

1:02:45 Wavelet Tree

17 |

0:00:00 Start

0:00:05 12 Geometrische Algorithmen

0:37:19 Übung 7

0:38:00 Approximationsalgorithmen

0:38:05 Grundlagen

0:38:56 Gütemaß

0:39:32 Klassen

0:41:33 Minimum Metric TSP

0:52:13 Zusammenfassung

0:52:51 Parametrisierte Algorithmen: fixed parameter tractable (FPT)

0:54:57 Parametrisierte Algorithmen: Definition

0:55:56 Techniken

0:57:50 Schiebepuzzle

0:59:59 Parallelverarbeitung: Modelle

1:04:43 PRAM Speicherkonflikte

1:08:38 Verbindungsnetzwerke Struktur

1:11:45 Anwendungen: Präfixsumme - Hypercube

1:16:04 Anwendungen: Paralleler Quicksort

1:20:20 Parallele Programmierung: Ein Einstieg

16 |

0:00:00 Start

0:00:05 Vorlesungswiederholung

0:02:23 Sortieren

0:02:45 Paralleles Quicksort

0:04:09 Anfänger-Parallelisierung

0:05:26 Theoretiker-Parallelisierung

0:08:43 Beispiel

0:16:30 Analyse

0:20:27 Verallgemeinerung für n >> p nach Schema F?

0:30:40 Paralleles Sortieren durch Mehrwegmischen

0:34:12 Mehr zu parallelem Sortieren

0:36:22 Messergebnisse

0:42:28 Übung

0:44:07 Applications

0:46:30 Large real-world networks

0:52:31 Branch and Reduce

0:54:39 Reduction rules

0:58:27 And more reductions

1:00:59 Praxisanwendung

1:02:44 The power of simple reductions

1:04:19 Combining reductions and inexact algorithms

1:06:03 Evolutionary algorithm

1:08:47 ReduMIS

1:12:12 Iterated Local Search

1:13:49 Accelerating Local Search

1:16:28 Linear-time reductions

1:18:46 Scalable Reductions

1:22:51 PACE 2019 Competition

1:25:12 Conclusion

15 |

0:00:00 Start

0:00:05 9 Fixed-Parameter-Algorithmen

0:01:15 Naive tiefenbeschränkte Suche

0:07:03 Reduktionsregeln

0:10:20 Verbesserte tiefenbeschränkte Suche

0:21:00 Zusammenfassung

0:23:23 10 Parallele Algorithmen

0:24:02 Warum Parallelverarbeitung

0:32:43 10.1 Modell

0:36:17 Kostenmodell für Nachrichtenaustausch

0:39:52 Warum kein Multicore-Modell

0:43:55 Formulierung paralleler Algorithmen

0:46:33 Analyse paralleler Algorithmen

0:53:45 10.2 Beispiel: Assoziative Operationen

1:06:39 Analyse

1:11:36 Diskussion Reduktionsoperation

1:12:12 Hyperwürfel

1:15:57 Präfixsummen

1:18:02 Hyperwürfelalgorithmus

1:24:40 Analyse

13 |

0:00:00 Start

0:00:05 Rucksackproblem

0:01:00 Fully Polynomial Time Approximations Scheme

0:02:57 Lemma 6

0:10:57 Lemma 7

0:13:31 Das beste bekannte FPTAS

0:16:27 Optimale Algorithmen für das Rucksackproblem

0:20:44 Fixed-Parameter-Algorithmen

0:22:41 Beispiel: VERTEX COVER

0:25:56 Fixed parameter tractable

0:30:23 Naive tiefenbeschränkte Suche

0:34:04 Kernbildung für Vertex Cover

0:42:25 Übung 6

0:43:04 Randomisierte Algorithmen

0:44:06 Monte Carlo Simulation

0:44:47 Las Vegas zu Monte Carlo

0:48:06 Matrix-Matrix Multiplikation

0:53:39 Coupon Collector

0:56:29 Harmonische Zahlen

0:57:24 Speichermodell

1:00:49 Blockgrößen

1:01:52 I/O-effizientes Design

1:05:17 Externe Priority Queue

1:09:30 Externes Sortieren

13 |

0:00:00 Start

0:00:50 Approximationsalgorithmen

0:06:54 Scheduling unabhängiger gewichteter Jobs auf parallelen Maschinen

0:10:22 List Scheduling

0:19:27 Der Approximationsfaktor

0:34:27 Nichtapproximierbarkeit des Handlungsreisendenproblems (TSP)

0:37:04 Beweis

0:45:57 Euler-Touren/-Kreise

0:48:36 2-Approximation durch minimalen Spannbaum

0:51:56 Beispiel

0:54:47 Beweis

0:55:39 Zusatz: Mehr TSP

1:07:03 Pseudopolynomielle Algorithmen

1:09:07 Beispiel: Rucksackproblem

1:10:50 Dynamische Programmierung nach Profit

1:14:45 Fully Polynomial Time Approximation Scheme

1:16:27 Beispielschranken

1:18:17 FPTAS für Knapsack

12 |

0:00:00 Start

0:00:05 Externe Algorithmen

0:04:35 Externe Prioritätslisten

0:23:46 Experiments

0:29:19 Offenes Problem

0:44:50 Approximationsalgorithmen

0:45:37 Übung

0:46:51 Potentialmethode

0:50:01 preflow-push Algorithmus

0:56:31 FIFO preflow-push Algorithmus

1:10:36 Matching

11 |

0:00:00 Start

0:00:59 Randomisierte Algorithmen

0:01:39 Wichtigste Unterscheidung

0:02:43 Beispiel: Monte Carlo-Algorithmus

0:10:57 Sort Checking II

0:15:22 Hashing II

0:23:57 Cuckoo Hashing

0:35:49 Random Graph Theory

0:39:51 Space Efficient Cuckoo Hashing

0:45:22 Zusammenfassung: Randomisierte Algorithmen

0:47:33 Externe Algorithmen

0:47:37 Das Sekundärspeichermodell

0:51:08 Externe Stapel

0:54:29 Externes Sortieren

1:02:52 Zahlenbeispiel

1:04:17 Mehrwegmischen

10 |

0:00:00 Start

0:00:05 Zusammenfassung letzter Vorlesung

0:02:20 Highest Level Preflow Push

0:04:14 Proof of Lemma 12

0:07:03 Claims

0:20:04 MFIFO: Modified FIFO Selection Rule

0:21:04 Heuristic Improvements

0:28:20 Experimental Results

0:29:51 Timings: Random Graphs

0:33:04 Timings: CG1

0:34:10 Timings: CG2

0:35:07 Timings: AMO

0:36:36 Asymptotics

0:37:54 Recent AE Results on Max-Flow

0:40:04 Zusammenfassung Flows und Matchings

09 |

0:00:00 Start

0:00:05 Ford Fulkerson Algorithm

0:03:24 Matching

0:08:18 Maximum Cardinality Bipartite Matching

0:14:11 Similar Performance for Weighted Graphs

0:19:48 Disadvantage of augmenting paths algorithms

0:28:09 Level Function

0:48:19 Partial Correctness

1:09:34 Searching for Eligible Edges

1:14:36 FIFO Preflow push