Algorithmen 2, Vorlesung, WS17/18

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 Anwendungen

1:20:13 Parallele Programmierung

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 Qualität von randWMA

0:23:06 Beweis

0:31:57 Warum Parallelverarbeitung?

0:42:17 Verschiede Modelle für Parallelverarbeitung

0:43:44 Nachrichtengekoppelter Parallelrechner

0:45:29 Parallelrechner mit globalem Speicher

0:46:50 Nachrichtenkopplung versus Speicherkopplung

0:52:19 Parallele Beispielalgorithmen

0:52:59 Überblick

0:54:08 Modell für Nachrichtenaustausch

0:58:14 Kostenmodell für Nachrichtenaustausch

1:01:24 Programmiermodell

1:05:54 Reduktion

1:09:50 Parallele Reduktion: Algorithmusidee

1:13:57 Parallele Reduktion: Algorithmus

1:20:10 Parallele Reduktion: Analyse

1:21:45 Parallele Reduktion mit p

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 Wettbewerbsfaktor

0:31:52 RANDMARK Algorithmus

0:35:50 Beweis

0:55:17 Übung 6

0:55:45 Online Algorithmen

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 Wettbewerbsfaktor

0:27:53 Strikte c-Kompetitivität

0:30:07 Wettbewerbsfaktor und strikte Kompetitivität

0:37:13 Nicht-strikte c-Kompetitivität

0:43:36 ListScheduling ist (fast) ein Onlinealgorithmus

0:46:48 Skiausleihe

0:47:19 Optimale Kosten

0:49:27 Deterministische Entscheidung für Skilauf

0:52:03 Speicherverwaltung

0:54:28 Plan für diesen Abschnitt

0:56:17 Longest Forward Distance (LFD)

0:59:14 Optimalität von LFD

0:59:41 Optimalität von LFD-Beweisskizze

1:05:38 Deterministische Onlinealgorithmen

1:15:10 Untere Schranke für den Wettbewerbsfaktor

1:15:39 Untere Schranke für den Wettbewerbsfaktor-Beweisskizze

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 Counting Query

0:27:01 Wavelet Tree Dominance Counting Query

0:32:57 Beispiel

0:34:15 Analyse

0:34:57 Wavelet Tree Dominance Reporting Query

0:40:43 Analyse

0:42:29 Allgemeine Reporting Query

0:44:54 Übung 5

0:45:58 Lempel-Ziv 78 decompression

1:00:07 Geometrische Algorithmen

1:01:36 Geometrische Methoden

1:03:18 Sweep-Line

1:06:59 One-Dimensional Problem

1:07:24 Skyline

1:08:31 Interval Search Trees

1:18:06 Rectangle Intersection Problem

1:21:39 Punktorientierung

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 Konvexe Hülle

0:56:53 Graham's Scan

1:02:07 Kleinste einschließende Kugel

1:19:40 2D Bereichssuche (range research)

1:25:45 Reduktion auf 1..n x 1..n

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)

0:29:34 LOUDS-level order unary degree sequence

0:44:15 Anfang der Übung

0:44:30 Today topics

0:44:59 Select in constant time: Step 1

0:47:49 Select in constant time: Step 2

0:49:33 Select in constant time: Step 3

0:56:54 Select in constant time: Query

1:01:17 Lempel-Ziv: Overview

1:02:06 Sliding Window Lempel-Ziv 77

1:08:01 Lempel-Ziv 78

1:16:08 Sliding Window Lempel-Ziv 77

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 (4n+o(n) bits)

0:34:19 (O(n),O(1)) solution (2n+0(n) bits )

0:47:12 Burrows-Wheeler-Transformation: Einführung

0:48:52 Wiederholung: Suffix-Array

0:49:24 Transformation

0:52:22 Burrows-Wheeler-Transformation: Eigenschaften

0:53:52 Rücktrnasformation

1:05:34 Berechnung von LF

1:08:02 Ablauf der Berechnung von LF

1:10:34 Was bringt die BWT?

1:11:41 Kompression

1:12:03 Kompression: Move-To-Front (MTF) Kodierung

1:13:38 Kompression: Huffmann Kodierung

1:14:37 Suche in der Burrowa-Wheeler Transformation

1:15:35 Backward Search

1:21:55 Backward Search: Summary

1:22:37 Wavelet Tree Example: Calculate Rank

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 minimum queries (RMQs)

0:25:17 Overview

0:26:08 O(n), Olog(n)- solution

0:30:13 O(nlog(n)), O(1) solution 2

0:40:07 Themenübersicht

0:40:31 In-place Multikey Quicksort

0:50:59 Suche mit Border-Array

1:02:52 Suche mit Suffix-Array

1:10:06 LCP-Array

1:11:24 Schnelle Suche mit Suffix-Array

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 Digit First Radix Sort

0:28:03 Stabiles Ganzzahliges Sortieren

0:32:09 Rekursions-Beispiel: Einfacher Fall

0:33:53 Sortieren der mod 0 Suffixe

0:39:37 Analyse

0:41:58 Implementierung: Vergleichs-Operatoren

0:42:35 Implementierung: Radix-Sortieren

0:42:50 Implementierung: Tripel Sortieren

0:43:24 Implementierung: Lexikographisches Benennen

0:43:47 Verallgemeinerung: Differenzüberdeckungen

0:48:00 Verbesserungen/ Verallgemeinerungen

0:48:54 Suffixtabellenkonstruktion: Zusammenfassung

0:49:29 Suche in Suffix Arrays

0:53:50 LCP-Array

1:08:43 LCP-Array: Berechnung

1:13:28 Suffix-Baum aus SA und LCP

1:21:07 Suche in Suffix-Bäumen

1:22:01 Datenkompression