Algorithmen 2, Vorlesung, WS17/18

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 Suffixe Sortieren 1:14:18 Volltextsuche 1:14:38 Suffix-Baum

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 Approximationsschema 0:25:56 PTAS versus FPTAS 0:26:34 Von pseudopolynomieller zu polynomieller Laufzeit 0:28:12 FPTAS für KNAPSACK 0:32:14 epsApproxKnapsack ist FPTAS 0:32:46 epsApproxKnapsack ist FPTAS:

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 Eigenschaften des Algorithmus (2) 0:34:43 Erinnerung: TSP-Suchproblem 0:37:41 TSP-alpha-Approximations-Suchproblem 0:40:06 Erinnerung: Hamiltonkreis (Entscheidungdproblem) 0:41:02 Schwere Approximierbarkeit des

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 Zusammenhangskomponenten 0:23:15 Erwartet konstanter Knotengrad 0:24:21 Andere Anforderungen? 0:24:58 Barabasi-Albert Modell

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 0:44:26 Chernoff-Schranken: Verienfachungen 0:45:47 Chernoff-Schranken: Korollare 0:47:14 Auswertung von Und-Oder-Bäume 0:51:13 Satz 0:53:50 Beweis 1:00:35 Zwischenüberlegung 1:04:58 Algorithmus:

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: Würfeln 0:15:26 Algorithmen mit unbekannter Laufzeit 0:16:25 Algorithmen, die ""variierende Ausgaben"" liefern 0:21:05 Vorteile randomisierter Algorithmen 0:23:28 Motivation 0:25:14