show episodes
Loading …
show series
 
23 | 0:00:00 Start0:00:52 Heutige Vorlesung0:01:52 Zusammenfassung0:08:58 Propositional Logic0:13:39 Staisfiability0:16:08 Satisfiabilty - Example0:19:27 Satisfiability - A Practical Example0:27:15 Satisfiability - Hardness0:35:41 Satisfiability - History0:39:37 Applications of SAT solving0:42:50 SAT Solving in the news0:44:28 Pythadorean Triples0:…
 
22 | 0:00:00 Start0:00:28 Rückblick Vorlesung 09.07.0:03:19 Dynamische Programmierung – Aufbau aus Bausteinen0:09:15 Dynamische Programmierung0:16:46 Rekonstruktion der Lösung0:19:07 Algorithmenentwurf mittels dynamischer Programmierung0:23:33 Anwendungen dynamischer Programmierung0:28:33 Gegenbeispiel: Teilproblemeigenschaft0:34:30 Gegenbeispiel: …
 
18 | 0:00:00 Starten0:00:32 Rückblich Vorlesung 18.060:02:48 Kürzeste Wege: Definition0:04:13 Dijkstras Algorithmus0:08:01 Dijkstra: Negative Kantengewichte0:21:54 Negative Zyklen0:28:26 Zurück zu Basiskonzepten0:31:34 Mehr Basiskonzepte0:33:21 Allgemeines Korrektheitskriterium0:33:52 Bellman-Ford-Algorithmus0:40:31 Negative Kreise0:53:56 Azyklisch…
 
19 | 0:00:00 Start0:02:10 Rückblick Vorlesung 25.06.0:05:34 Minimale Spannbäume0:11:04 Minimale aufspannende Wälder0:17:03 MST-Kanten auswählen und verwerfen0:33:48 Der Jarnik-Prim-Algorithmus0:47:00 Analyse0:48:53 Kruskals Algorithmus1:01:44 Kruskals Algorithmus – Korrektheit1:04:35 Union-Find Datenstruktur1:19:03 Pfadkompression1:22:33 Union by R…
 
20 | 0:00:00 Start0:00:12 Rückblick0:19:10 heutige Vorlesung0:19:43 Analyse – Pfadkompression und Union by Rank0:28:50 Ackermannfunktion – Beispiele0:30:58 Kruskal mit Union-Find0:39:37 Vergleich mit Jarnik-Prim vs. Kruskal0:42:42 Mehr MST-Algorithmen0:48:16 Zusammenfassung0:51:08 Generische Optimierungsprobleme0:53:39 Durchgehendes Beispiel: Rucks…
 
17 | 0:00:00 Starten0:00:11 Rückblick Vorlesung 11.060:02:13 BFS vs. DFS0:04:05 Begriff ""Zusammenhang""0:11:16 Überblick heutige Vorlesung0:12:03 Kürzeste Wege0:15:11 Definition0:24:05 Grundlagen0:28:02 Dijkstra Algorithmus0:32:10 Edsger Wybe Dijkstra0:42:03 Allgemeine Definition0:45:37 Kante relaxieren0:49:42 Pseudocode1:08:15 Implementierung1:18…
 
16 | 0:00:00 Starten0:00:05 Roadmap0:00:25 Übungsklausur0:02:58 Graphen und Relationen0:04:22 Knotengrad0:05:04 Beispiele0:08:26 Handshaking Lemma0:11:58 Adjazenz- und Inzidenzmatrix0:20:29 Grpahen als Matrizen0:25:17 Pfade und Kreise0:26:13 Eulersche und Hamiltonsche Kreise0:28:11 Satz von Euler0:36:05 Breitensuche0:47:48 Tiefensuche…
 
15 | 0:00:00 Starten0:00:09 Organisatorisches0:03:12 Randbemerkung zu WWDC 20180:05:32 Rückblick Vorlesung 06.06.0:07:56 Überblick heutige Vorlesung0:08:18 Adjazenz-Matrix0:08:52 Pfade zählen mittels LA0:09:38 Graphentheorie und LA0:15:39 Zusammenhangstest für Intervallgraphen0:18:18 Beispiel0:19:52 Graphenpräsentation: Zusammenfassung0:21:30 Graph…
 
14 | 0:00:00 Starten0:00:16 Rückblick 04.06.0:02:56 Graphen0:05:51 Königesberger Brückenproblem0:10:00 Graphen Anwendung0:13:43 Repräsentation von Graphen0:19:19 Notation und Konvention0:22:01 Ungerichtete vs gerichtete Graphen0:23:01 Operationen0:27:17 Kantenfolgenrepräsentation0:30:53 Repräsentation von Graphen0:31:35 Adjazenzfelder0:40:55 Beispi…
 
13 | 0:00:00 Start0:00:30 Überblick heutige Vorlesung0:00:51 Sortierte Folgen0:05:42 Binäre Baumsuche0:10:05 Varianten, Bemerkungen0:12:19 locate(k)0:15:58 Invariante von locate(k)0:17:58 Ergebnisberechnung von locate(k)0:18:45 Laufzeit von locate(k)0:20:30 Naives Einfügen0:25:12 Beispiel0:27:02 Suchbäume balancieren0:30:11 (a,b)-Bäume0:32:29 Items…
 
12 | 0:00:00 Start0:00:05 Rückblick Vorlesung 28.050:01:33 Überblick heutige Vorlesung0:02:30 Sortierte Folgen0:09:22 Statisch: Sortiertes Feld mit binärer Suche0:16:26 Binäre Suche: Beispiel k=150:19:15 Dynamisch sortierte Folgen - Grundoperationen0:22:51 Mehr Operationen0:26:32 Noch mehr Operationen0:30:24 Abgrenzung0:34:50 Sortierte Folgen - Anw…
 
11 | 0:00:00 Start0:00:05 Einfügen0:05:32 Funktion deleteMin0:17:09 deleteMin: Beispiel0:18:43 Binärer Heap - Analyse0:20:27 Binärer Heap - Konstruktion0:31:26 Ein nützlicher Rechentrick0:36:58 Heapsort0:43:07 Heapsort: Beispiel0:44:22 Heapsort vs. Quicksort vs. Mergesort0:48:19 Adressierbare Prioritätslisten0:51:26 Adressierbare Prioritätslisten: …
 
0:00:00 Start0:00:40 Rückblick Vorlesung 16.050:01:07 Überblick heutige Vorlesung0:03:48 Auswahl (Selection)0:06:36 Beispiel0:08:29 Auswahl: Anwendungen0:10:08 Quickselect0:14:16 Beispiel0:17:01 Quickselect: Analyse0:18:03 Mehr zum Auswahlproblem0:21:41 Durchbrechen der unten Schranke - Ganzzahliges Sortieren0:25:17 Schlüssel 0....k-1: Bucket Sort0…
 
09 | 0:00:00 Starten0:00:13 Rückblick 14.05.0:04:16 Überblicke aktuelle Vorlesung0:05:46 Erinnerung: Mergesort0:06:53 Quicksort0:09:32 Quicksort: Analyse im schlechtesten Fall0:15:21 Quicksort: Analyse im besten Fall0:19:16 Quicksort: Zufälliger Pivot0:20:26 Quicksort: Laufzeit0:26:46 Beweise0:51:15 Quicksort: Effiziente Implementierung1:03:03 Beis…
 
08 | 0:00:00 Start0:00:12 Rückblick Vorlesung 07.05.0:03:57 Analyse für zufällige Hash-Funktionen0:10:12 Universelles Hashing0:13:50 Eine einfache universelle Familie0:22:36 Beispiele für H0:25:13 Beweis Theorem0:33:14 Sortieren & Co0:36:47 Lochkartensortierer0:41:28 Grundproblem Sortieren0:45:33 Anwendungsbeispiele0:47:49 Einfache Sortieralgorithm…
 
06 | 0:00:00 Start0:00:13 Rückblick Vorlesung 02.050:02:40 Überblick heutige Vorlesung0:03:36 Hashing0:03:58 Hashtabellen0:09:48 Ein (Über-)optimistischer Ansatz0:15:00 Kollisionen0:19:53 Kollisionsauflösung0:21:13 Hashing mit verketteten Listen0:26:12 Hashing mit verketteten Listen: Beispiel0:31:30 Hashing mit verketteten Listen: Analyse0:33:08 Et…
 
05 | 0:00:00 Start0:00:17 Rückblick0:03:35 Felder (Arrays)0:09:16 Unbeschränkte Felder0:20:49 Unbeschränkte Felder mit teilweise ungenutztem Speicher0:25:26 Unbeschränkte Felder: Vergrößern0:30:50 Unbeschränkte Felder: Verkleinern0:34:46 Amprtisierte Komplexität für unbeschränkte Felder0:38:34 Beweis: Account-Methode (Konto-Methode)0:43:14 Amortisi…
 
04 | 0:00:00 Start0:00:05 P und NP0:02:43 Folgen als Felder und Listen0:06:11 Ausblick: Komplexität typischer Operationen0:13:27 Listenglieder (Items)0:21:00 Trick: Dummy Header0:24:18 Die Listenklasse0:27:12 Splice-Operation0:35:09 Weitere Operationen: Einfach mit splice0:37:32 Doch nicht so einfach? Speicherverwaltung !0:43:08 Items löschen0:45:1…
 
03 | 0:00:00 Start0:00:17 Roadmap0:01:27 Tutorien0:04:20 Effizienz von Algorithmen0:09:09 Generelles Beispiel0:10:38 Eingabegröße und Laufzeit0:12:12 Genauer: Laufzeit0:13:48 O - Notation0:19:59 Omega Notation0:20:16 Asymptotische Notationen0:21:14 Nochmal anschaulich0:21:18 Betrachtung über Grenzwerte0:23:57 Ein Kniffligeres Beispiel0:26:22 Basis …
 
02 | 0:00:00 Start0:00:18 Rückblick Vorlesung 18.040:01:15 RAM vs. Compiler-Zwischensprache LLVM0:05:03 Überblick heutige Vorlesung0:06:16 Pseudocode0:09:01 Design by Contract0:16:14 Schleifeninvarianten0:18:39 Beispiel0:25:34 Rechenbeispiel0:34:43 Zum power Algorithmus0:37:32 Laufzeitanalyse / Rekurrenzen0:42:10 Eine Rekurrenz für Teile und Herrsc…
 
01 | 0:00:00 Starten0:00:10 Ankündigung0:01:02 Rückblick - Vorlesung 16.04.20180:03:37 Hintergrund rekursiver Algorithmus0:07:28 Ein rekursiver Algorithmus0:10:35 Analyse0:19:54 Karatsuba-Ofman-Multiplikation [1962]0:23:44 Karatsuba-Ofman-Algorithmus0:26:10 Beispiel0:26:53 Analyse0:29:22 Geht es noch besser?0:36:02 Algorithm Engineering - Was hat d…
 
0:00:00 Starten0:00:15 Einführung in das Thema selbsorganisiertes Lernen 0:05:59 Selbstorganisiertes Lernen in der Arbeitstätigkeit0:11:57 Lernanlässe in der Arbeit 0:19:58 Beispiel: Lernen in einer Kfz.-Werkstatt 0:28:01 Dienstleistungen für das Lernen in der Arbeit 0:38:58 Prüfungen als Thema didaktischer Gestaltung0:48:00 Beispiel: Fortbildung z…
 
26 | 0:00:00 Starten0:00:09 Seminar: Proofs from the book0:04:48 Theses 2018: External, Parallel, and Distributed Sorting0:11:12 Graph Generators0:17:23 High Quality Hypergraph Partitioning0:23:59 Kernbildung in der Praxis0:38:53 Start Vorlesung0:40:33 Randomisierte Algorithmen0:43:44 Approximationsalgorithmen0:49:41 Online Algorithmen…
 
24 | 0:00:00 Starten0:00:09 highest level preflow push0:06:51 Example0:13:50 Proof of Lemma 120:17:30 Claims0:28:47 Heuristic Improvements0:33:32 Experimental results0:33:39 Timings: Random Graphs0:36:16 Timings0:36:40 Asymptotics0:36:43 Zusammenfassung Flows und Matchings0:49:53 Sortieren durch Mehrwege-Mischen0:50:00 Das Sekundärspeichermodell0:5…
 
25 | 0:00:00 Starten0:00:15 Highest Level Preflow Push 0:00:55 Claims0: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 Algorithmus0:20:44 FIFO preflow-push Algorithmus 0:42:37 Matching0:44:31 Bipartite-Matching 0:46:40 Speichermodell 0:48:26 Latenzen0:49:47 I/O-efffizientes Design0:51:12 …
 
23 | 0:00:00 Starten0:07:03 Flüsse und Ford Fulkerson0:08:39 Max Flow - Min Cut0:12:42 Dinitz: Distanz Label0:14:37 Dinitz: Schichtgraph0:15:45 Dinitz: Blockierender Fluss0:17:21 Dinitz: Blockierender Fluss Operationen0:20:36 Dinitz: Kosten pro Blockierender Fluss0:24:14 Dinitz: Laufzeit0:25:37 Dinitz: Kosten pro Phase, Unit Capacity Network0:30:24…
 
22 | 0:00:00 Starten0:00:09 Algorithms 1956-now0:00:47 Residual Graph0:02:25 A Bad Example for Ford Fulkerson0:03:19 Blocking Flows0:04:57 Dinitz Algorithm0:06:11 Blocking Flows Analysis 0:07:39 Dinitz Analysis0:17:14 Matching0:20:28 Maximum Cardinality Bipartite Matching0:23:44 Disadvantage of augmenting paths algorithms0:45:52 Übung 110:46:25 Kür…
 
21 | 0:00:00 Starten0:00:18 Maximum Flows and Matchings0:00:37 Definitions: Network0:02:23 Flows0:06:45 Applications0:07:19 Applications in our Group0:14:39 Option 1: linear programming0:16:09 Algorithms 1956-now0:19:49 Example0:24:55 Residual Graph0:31:33 Ford Fulkerson Algorithm0:43:36 Übung0:44:35 SCC0:55:06 Floyd Warshall: SCC als Speedup Techn…
 
0 | 0:00:00 Starten0:00:18 Anwendungen von DFS0:05:13 Tiefensuchschema für G= (V,E)0:09:29 Starke Zusammenhangskomponenten0:12:53 SCCs generischer Algorithmus0:20:12 Ziel: Effizienter Algorithmus0:27:20 Invarianten0:39:53 Invarianten von Gc0:53:47 traverseNonTreeEdge(v,w)0:56:47 Backtrack(u, v)1:01:52 Beispiel1:11:28 Zusammenfassung: SCC Berechnung…
 
18 | 0:00:00 Starten0:00:09 Fortgeschrittene Graphenalgorithmen0:04:34 Allgemeine Definition0:06:17 Kante relaxieren0:07:11 Dijkstra's Agorithmus0:08:40 Beispiel0:09:00 Laufzeit0:14:55 Lineare Laufzeit für dichte Graphen0:26:30 Präfixminima einer Zufallsfolge0:27:32 Monotone ganzzahlige Prioritätslisten0:31:28 Bucket-Queue0:34:22 Operation0:35:17 L…
 
17 | 0:00:00 Starten0:00:46 Aufgabenvarianten0:01:16 Verteilte Eigenschaften0:01:30 Theoretiker-Quicksort0:06:08 Fortgeschrittene Datenstrukturen0:10:27 Adressierbare Prioritätslisten0:34:55 Adressierbare Prioritätslisten: Anwendungen0:38:27 Grundlegende Datenstruktur 0:39:29 Wälder bearbeiten0:40:59 Pairing Heaps (Paarungs-Haufen??)0:46:39 Pairing…
 
16 | 0:00:00 Starten0:00:09 Parallele Reduktion: Algorithmus0:05:38 Analyse paralleler Programme0:14:10 Parallele Präfixsummen0:44:36 Übung 70:45:28 Expertenauswahl0:49:41 Parallelverarbeitung0:52:09 PRAM0:54:56 Verbindungsnetzwerke1:01:33 Nachrichtenaustausch: Pipelining1:06:31 Anwendungen1:20:13 Parallele Programmierung…
 
15 | 0:00:00 Starten0:00:33 Überblick0:01:07 Problemstellung0:04:06 Auswahl von Experten0:05:07 Auswahl von Experten: der deterministische Weighted Majority Algorithm (wma)0:07:49 Qualität von WMA 0:09:31 Beweis0:16:48 Verallgemeinerte Problemstellung0:18:17 Randomisiert: randWMA0:21:13 Qualität von randWMA0:23:06 Beweis0:31:57 Warum Parallelverarb…
 
14 | 0:00:00 Starten0:01:57 LRU - Beispiel0:05:27 LRU ist K- Kompetitiv0:06:22 LRU ist K-Kompetitive – Beweisskizze0:15:44 Resource Augmentation: (h,k)-Seitenwechsel0:24:12 Randomisiert0:25:14 Randomisierte Onlinealgorithmen0:26:09 Widersacher: verschieden miese Typen0:30:04 Wettbewerbsfaktor0:31:52 RANDMARK Algorithmus0:35:50 Beweis0:55:17 Übung 6…
 
13 | 0:00:00 Starten0:02:50 Eine Reihe von Beispiele0:05:39 Beispiel Job-Scheduling0:07:07 Beispiel Skiausleihe0:09:30 Speicherverwaltung 0:12:04 Auswahl von Experten0:14:23 Beispiel Selbstorganisierende Datenstrukturen0:15:12 Online-Algorithmus0:19:55 Competitive Analysis0:24:45 Wettbewerbsfaktor0:27:53 Strikte c-Kompetitivität 0:30:07 Wettbewerbs…
 
12 | 0:00:00 Starten0:00:09 Orthogonal range searching0:01:01 Orthogonal range searching - 1D0:07:03 Orthogonal range searching - 2D0:17:40 Wavelet Tree Dominance Reporting Query0:17:54 Reduktion auf 1..n x 1..n0:18:18 Beispiel0:19:54 Wavelet Tree0:22:18 Beispiel0:24:30 Wavelet Tree Counting Query0:27:01 Wavelet Tree Dominance Counting Query0:32:57…
 
11 | 0:00:00 Starten0:06:23 Typische Fragestellungen0:15:56 Streckenschnitt: Naiver Algorithmus0:19:04 Idee: Plane-Sweep-Algorithmus0:24:57 Plane-Sweep für orth. Streckenschnitt0:29:03 Verallgemeinerung - Grundidee0:40:56 Verallgemeinerung - Beispiel0:49:50 Überlappungen finden0:52:30 2D Konvexe Hülle0:56:53 Graham's Scan1:02:07 Kleinste einschließ…
 
10 | 0:00:00 Starten0:00:21 Wavelet Tree Example: Calculate Rank0:09:48 Huffman-shaped Wavelet Tree0:12:42 Practical Performance of FM-Index0:14:54 Succinct Data Structures0:17:09 Succinct representation of trees0:19:34 Child operation in detail0:22:09 Succinct representation of trees (2)0:29:34 LOUDS-level order unary degree sequence0:44:15 Anfang…
 
09 | 0:00:00 Starten0:00:18 Range minimum queries (RMQs)0:00:43 Overview0:01:05 O(n), Olog(n)-solution 10:01:18 O(nlogn), O solution 20:01:38 O(nlog(logn)), O(1) solution0:02:17 O(n),O(1) solution0:02:33 LCA & +1RMQ0:02:51 O(n),O(1) solution0:08:08 LCA& +1RQM0: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…
 
08 | 0:00:00 Starten0:00:34 Verlustfreie Textkompression0:01:25 Theorie verlustfreier Textkompression0:10:57 Wörterbuchbasierte Textkompression0:12:58 Lempel-Ziv Kompresssion (LZ)0:17:44 Naive LZ Dekompression0:20:15 LZ- Verfeinerungen0:21:39 LCP zwischen beliebigen Suffixen0:23:44 Range minimum queries (RMQs)0:25:17 Overview0:26:08 O(n), Olog(n)- …
 
07 | 0:00:00 Starten0:00:22 Suffix-Baum0:01:20 Alphabet-Modell0:02:41 Geordnetes ganzzahliges Alphabet0:04:39 Verallgemeinerung: Lexikographische Namen0:05:31 Ein erster Teile-und-Herrsche-Ansatz0:13:30 Asymmetrisches Divide-and-Conquer0:18:09 Rekursion, Beispiel0:25:39 Least Significant Digit First Radix Sort0:28:03 Stabiles Ganzzahliges Sortieren…
 
06 | 0:00:00 Starten0:00:32 4 Stringology (Zeichenkettenalgorithmen)0:04:16 Strings Sortieren0:15:40 Strings Sortieren - Laufzeitanalyse0:18:27 Naives Pattern Matching0:55:49 Volltextsuche von langsam bis Superschnell1:04:37 Suffixtabellen1:05:37 Etwas ""Stringology""-Notation1:07:03 Suffixe Sortieren1:14:18 Volltextsuche1:14:38 Suffix-Baum…
 
05 | 0:00:00 Starten0:00:34 Turing-Reduzierbarkeit0:02:47 Pseudopolynomielle Laufzeit0:05:58 Zwei kleine Warnungen0:07:55 KNAPSACK Suchproblem0:10:22 KNAPSACK: Codierungen der Eingabe0:11:47 Schwere des KNAPSACK Suchproblems0:12:41 KNAPSACK: pseudopolynomielle Laufzeit0:22:08 Polynomielle Approximationsschema0:25:56 PTAS versus FPTAS0:26:34 Von pse…
 
04 | 0:00:00 Starten0:01:07 Suchprobleme0:04:15 Approximation bei Suchprobleme0:07:10 Approximation bei Zählprobleme0:08:51 Job Scheduling: Aufgabenstellung0:13:14 Naheliegender Algorithmus: listScheduling0:20:19 Eigenschaften des Algorithmus0:26:55 Approxiamtionsfaktor0:28:43 Eigenschaften des Algoritmus (2)0:34:43 Erinnerung: TSP-Suchproblem0:37:…
 
03 | 0:00:00 Starten0:00:10 Kapitel: Randomisierte Algorithmen0:00:45 Überblick0:02:44 Erdos-Renyi-Zufallsgraphen0:04:59 ER-Graphen: einfache Beobachtungen0:11:05 Manchmal interessieren sehr große n und asymptotische Eigenschaften0:15:21 ER-Graphen:Durschmesser <=20:21:51 Zusammenhangskomponenten0:23:15 Erwartet konstanter Knotengrad0:24:21 Andere …
 
02 | 0:00:00 Starten0:01:08 Erinnerung an W-Theorie0:02:22 Randomisierter Quicksort0:04:34 randQS: Anzahl Vergleiche0:11:40 randQS: Anzahl Vergleiche mit hoher Wkt.0:28:25 Chernoff-Schranken0:29:04 Einfache Schranken0:32:19 Chernoff-Schranken0:38:03 Chernoff-Schranken: Beweis von Teil 10:44:26 Chernoff-Schranken: Verienfachungen0:45:47 Chernoff-Sch…
 
01 | 0:00:00 Starten0:00:10 Kapitel: Randomisierte Algorithmen0:01:10 Überblick0:01:38 Sichtweisen für randomisierte Algorithmen0:03:33 Fundamentale Änderung0:04:03 Beispiel: Randomisierter Quicksort0:05:32 Zufallsvariablen überall0:05:49 Errinerung an W-Theorie0:09:32 Standardbeispiel: Würfeln0:15:26 Algorithmen mit unbekannter Laufzeit0:16:25 Alg…
 
Loading …

Kurzanleitung

Google login Twitter login Classic login