Algorithmen 1, SS2018, Vorlesung

23 | 0:00:00 Start 0:00:52 Heutige Vorlesung 0:01:52 Zusammenfassung 0:08:58 Propositional Logic 0:13:39 Staisfiability 0:16:08 Satisfiabilty - Example 0:19:27 Satisfiability - A Practical Example 0:27:15 Satisfiability - Hardness 0:35:41 Satisfiability - History 0:39:37 Applications of SAT solving 0:42:50 SAT Solving in the news 0:44:28 Pythadorean Triples 0:53:13 Arithmetic Progressions 0:56:39 Background: Van der Eaerden Numbers 1:00:11 Graph Coloring 1:02:10 Graph Coloring: Encoding in SAT 1:03:57 Graph Coloring: Example 1:04:00 Graph Coloring: Input 1:05:16 Graph Coloring: Output 1:06:44 Klausur 1:11:26 Klausurbonus

22 | 0:00:00 Start 0:00:28 Rückblick Vorlesung 09.07. 0:03:19 Dynamische Programmierung – Aufbau aus Bausteinen 0:09:15 Dynamische Programmierung 0:16:46 Rekonstruktion der Lösung 0:19:07 Algorithmenentwurf mittels dynamischer Programmierung 0:23:33 Anwendungen dynamischer Programmierung 0:28:33 Gegenbeispiel: Teilproblemeigenschaft 0:34:30 Gegenbeispiel: Austauschbarkeit 0:43:54 Systematische Suche 0:51:25 Beispiel: Branch-and-Bound für das Rucksackproblem 1:03:34 Branch-and-Bound allgemein 1:06:20 Lokale Suche – global denken, lokal handeln 1:10:17 Hill Climbing 1:15:15 Problem: Lokale Optima 1:18:14 Jenseits von Hill-Climbing 1:21:27 Evolutionäre Algorithmen

21 | 0:00:00 Start 0:02:30 Dijkstras Algorithmus 0:10:26 Bellman Ford Algorithmus 0:22:16 Minimale Spannbäume 0:27:49 Steinerbäume 0:35:38 Problem des Handlungsreisenden (TSP)

18 | 0:00:00 Starten 0:00:32 Rückblich Vorlesung 18.06 0:02:48 Kürzeste Wege: Definition 0:04:13 Dijkstras Algorithmus 0:08:01 Dijkstra: Negative Kantengewichte 0:21:54 Negative Zyklen 0:28:26 Zurück zu Basiskonzepten 0:31:34 Mehr Basiskonzepte 0:33:21 Allgemeines Korrektheitskriterium 0:33:52 Bellman-Ford-Algorithmus 0:40:31 Negative Kreise 0:53:56 Azyklische Graphen 0:58:07 Kürzeste Wege: Zusammenfassung 1:03:52 Exkurs: Routing in Straßennetzwerken 1:10:33 Distanz zu einem Zielknoten 1:11:56 Ideen für Routenplanung 1:13:54 Transit Node Routing

19 | 0:00:00 Start 0:02:10 Rückblick Vorlesung 25.06. 0:05:34 Minimale Spannbäume 0:11:04 Minimale aufspannende Wälder 0:17:03 MST-Kanten auswählen und verwerfen 0:33:48 Der Jarnik-Prim-Algorithmus 0:47:00 Analyse 0:48:53 Kruskals Algorithmus 1:01:44 Kruskals Algorithmus – Korrektheit 1:04:35 Union-Find Datenstruktur 1:19:03 Pfadkompression 1:22:33 Union by Rank

20 | 0:00:00 Start 0:00:12 Rückblick 0:19:10 heutige Vorlesung 0:19:43 Analyse – Pfadkompression und Union by Rank 0:28:50 Ackermannfunktion – Beispiele 0:30:58 Kruskal mit Union-Find 0:39:37 Vergleich mit Jarnik-Prim vs. Kruskal 0:42:42 Mehr MST-Algorithmen 0:48:16 Zusammenfassung 0:51:08 Generische Optimierungsprobleme 0:53:39 Durchgehendes Beispiel: Rucksackproblem 0:56:52 Allgemein: Maximierungsproblem 1:00:36 Black-Box-Löser 1:02:10 Lineare Programmierung 1:10:08 Ein einfaches Beispiel 1:15:08 Eine Anwendung: Tierfutter

17 | 0:00:00 Starten 0:00:11 Rückblick Vorlesung 11.06 0:02:13 BFS vs. DFS 0:04:05 Begriff ""Zusammenhang"" 0:11:16 Überblick heutige Vorlesung 0:12:03 Kürzeste Wege 0:15:11 Definition 0:24:05 Grundlagen 0:28:02 Dijkstra Algorithmus 0:32:10 Edsger Wybe Dijkstra 0:42:03 Allgemeine Definition 0:45:37 Kante relaxieren 0:49:42 Pseudocode 1:08:15 Implementierung 1:18:38 Laufzeit

16 | 0:00:00 Starten 0:00:05 Roadmap 0:00:25 Übungsklausur 0:02:58 Graphen und Relationen 0:04:22 Knotengrad 0:05:04 Beispiele 0:08:26 Handshaking Lemma 0:11:58 Adjazenz- und Inzidenzmatrix 0:20:29 Grpahen als Matrizen 0:25:17 Pfade und Kreise 0:26:13 Eulersche und Hamiltonsche Kreise 0:28:11 Satz von Euler 0:36:05 Breitensuche 0:47:48 Tiefensuche

15 | 0:00:00 Starten 0:00:09 Organisatorisches 0:03:12 Randbemerkung zu WWDC 2018 0:05:32 Rückblick Vorlesung 06.06. 0:07:56 Überblick heutige Vorlesung 0:08:18 Adjazenz-Matrix 0:08:52 Pfade zählen mittels LA 0:09:38 Graphentheorie und LA 0:15:39 Zusammenhangstest für Intervallgraphen 0:18:18 Beispiel 0:19:52 Graphenpräsentation: Zusammenfassung 0:21:30 Graph-Traversierung 0:23:14 Graphtraversierung als Kantenklassifizierung 0:26:23 Breitensuche 0:31:57 Repräsentation des Baumes 0:41:59 Repräsentation von Q und Q' mittels FIFO 0:45:45 Tiefensuche 0:47:04 Tiefensuchschema für G=(V,E) 0:52:43 DFS-Baum 1:00:08 DFS-Nummerierung 1:03:55 Fertigstellungszeit 1:06:03 Kantenklassifizierung bei DFS 1:07:47 Fertigstellungszeit 1:08:58 Topologishce Sortierung 1:13:38 Topologisches Sortieren mittels DFS 1:16:50 Starke Zusammenhangskomponenten 1:21:17 MehrDFS-basierte Linearzeitalgorithmen 1:22:37 BFS vs. DFS

14 | 0:00:00 Starten 0:00:16 Rückblick 04.06. 0:02:56 Graphen 0:05:51 Königesberger Brückenproblem 0:10:00 Graphen Anwendung 0:13:43 Repräsentation von Graphen 0:19:19 Notation und Konvention 0:22:01 Ungerichtete vs gerichtete Graphen 0:23:01 Operationen 0:27:17 Kantenfolgenrepräsentation 0:30:53 Repräsentation von Graphen 0:31:35 Adjazenzfelder 0:40:55 Beispiel 0:47:58 Kantenanfragen 0:48:56 Adjazenzlisten 0:52:17 Adjazenzlisten Aufrüsten 0:55:18 Customisation 0:57:31 Beispiel: DAG-Erkennung 1:10:55 Adjazenz Matrix

13 | 0:00:00 Start 0:00:30 Überblick heutige Vorlesung 0:00:51 Sortierte Folgen 0:05:42 Binäre Baumsuche 0:10:05 Varianten, Bemerkungen 0: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ügen 0:25:12 Beispiel 0:27:02 Suchbäume balancieren 0:30:11 (a,b)-Bäume 0:32:29 Items 0:37:10 Initialisierung 0:39:02 Locate 0:43:44 Locate - Laufzeit 0:48:03 Einfügen - Algorithmenskizze 0:51:20 EInfügen - Beispiel 0:58:10 Einfügen - Korrektheit 1:01:50 Einfügen - Implementierungsdetails 1:03:57 EInfügen - Pseudocode 1:13:31 Entfernen - Algorithmenskizze 1:19:54 Entfernen - Beispiel 1:21:52 Entfernen - Korrektheit 1:23:44 Einfügen und Entfernen - Laufzeit 1:25:02 Mehr Operationen 1:26:40 Zusammenfassung

12 | 0:00:00 Start 0:00:05 Rückblick Vorlesung 28.05 0:01:33 Überblick heutige Vorlesung 0:02:30 Sortierte Folgen 0:09:22 Statisch: Sortiertes Feld mit binärer Suche 0:16:26 Binäre Suche: Beispiel k=15 0:19:15 Dynamisch sortierte Folgen - Grundoperationen 0:22:51 Mehr Operationen 0:26:32 Noch mehr Operationen 0:30:24 Abgrenzung 0:34:50 Sortierte Folgen - Anwendungen 0:35:56 Anwendungsbeispiel: Best Fit Bin Packing 0:41:18 Binäre Baumsuche 0:42:52 3. Übung Algorithmen I 0:44:16 Roadmap 0:45:04 Erinnerung: Bucketsort 0:46:03 Bucket Sort Spezial 0:54:52 Priority Queues 0:57:02 Spezielle Priority Queues 0:58:36 Bucket Queue 1:01:41 Binary Radix Heap 1:08:58 Binary Radix Heap: deleteMin 1:11:34 Möglichkeit Ternärer Radix Heaps 1:13:12 Schnelle Heaps: Zusammenfassung

11 | 0:00:00 Start 0:00:05 Einfügen 0:05:32 Funktion deleteMin 0:17:09 deleteMin: Beispiel 0:18:43 Binärer Heap - Analyse 0:20:27 Binärer Heap - Konstruktion 0:31:26 Ein nützlicher Rechentrick 0:36:58 Heapsort 0:43:07 Heapsort: Beispiel 0:44:22 Heapsort vs. Quicksort vs. Mergesort 0:48:19 Adressierbare Prioritätslisten 0:51:26 Adressierbare Prioritätslisten: Anwendungen 0:53:23 Adressierbare Binäre Heaps 0:55:39 Adressierbare Prioritätslisten - Laufzeiten 0:56:43 Prioritätslisten: Mehr 0:57:18 Prioritätslisten: Zusammenfassung

0:00:00 Start 0:00:40 Rückblick Vorlesung 16.05 0:01:07 Überblick heutige Vorlesung 0:03:48 Auswahl (Selection) 0:06:36 Beispiel 0:08:29 Auswahl: Anwendungen 0:10:08 Quickselect 0:14:16 Beispiel 0:17:01 Quickselect: Analyse 0:18:03 Mehr zum Auswahlproblem 0:21:41 Durchbrechen der unten Schranke - Ganzzahliges Sortieren 0:25:17 Schlüssel 0....k-1: Bucket Sort 0:28:49 Beispiel: k=4 0:30:46 Array-Implementierung 0:31:13 Beispiel 0:35:37 K^d Schlüssel 0:41:49 LSD-Radix-Sort: Beispiel 0:41:56 Mehr zu ganzzahligem Sortieren 0:42:10 Sortieren: vergleichsbasiert vs. ganzzahlig 0:43:48 Was haben wir jeneseits von Sortieren gelernt? 0:45:52 Übung 0:46:19 Roadmap 0:47:23 Rückblick 0:49:00 Sortieren durch Einfügen: In-Place 0:50:11 Sortieren durch Einfügen: Sentinel 0:51:52 Sound 0:55:34 Quantifiziertes Chaos: Inversionen 0:58:22 Quantifiziertes Chaos: Runs 0:59:42 Quantifiziertes Chaos: Removal 1:00:26 Adaptives Sortieren 1:01:21 Insertion Sort: Adaptiv? 1:02:12 Insertion Sort: Erwartete Laufzeit 1:06:36 Natural Merge Sort 1:07:58 Erwartete Anzahl von Runs 1:16:55 Split Sort 1:18:49 Split Sort: Beispiel 1:22:09 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen 1:23:18 C++ 1:24:23 Java

09 | 0:00:00 Starten 0:00:13 Rückblick 14.05. 0:04:16 Überblicke aktuelle Vorlesung 0:05:46 Erinnerung: Mergesort 0:06:53 Quicksort 0:09:32 Quicksort: Analyse im schlechtesten Fall 0:15:21 Quicksort: Analyse im besten Fall 0:19:16 Quicksort: Zufälliger Pivot 0:20:26 Quicksort: Laufzeit 0:26:46 Beweise 0:51:15 Quicksort: Effiziente Implementierung 1:03:03 Beispiel: Partitionierung 1:06:23 Beispiel: Rekursion 1:06:49 Größerer Basisfall 1:15:40 Halbrekursive Implementierung 1:18:44 Quadratische Komplexität bei gleichen Elementen und Drei-Wege-Partitionierung 1:22:12 Vergleich Quicksort und Mergesort mit Benchmark

08 | 0:00:00 Start 0:00:12 Rückblick Vorlesung 07.05. 0:03:57 Analyse für zufällige Hash-Funktionen 0:10:12 Universelles Hashing 0:13:50 Eine einfache universelle Familie 0:22:36 Beispiele für H 0:25:13 Beweis Theorem 0:33:14 Sortieren & Co 0:36:47 Lochkartensortierer 0:41:28 Grundproblem Sortieren 0:45:33 Anwendungsbeispiele 0:47:49 Einfache Sortieralgorithmen 0:51:17 Sentinels am Beispiel Sortieren durch Einfügen 0:57:07 Analyse 1:00:25 Sortieren durch Mischen 1:03:33 Beispiel 1:05:00 Mischen 1:07:27 Analyse 1:11:24 Untere Schranken 1:13:49 Eine Vergleichsbasierte untere Schranke 1:16:51 Baumbasierte Sortierdarstellung 1:19:03 Beweis 1:22:16 Randomisierung, Mittlere Ausführungszeit 1:22:58 Quicksort – erster Versuch

07 | 0:00:00 Start 0:00:39 Verkettete Listen 0:01:43 Skip Lists 0:06:10 Amortisierte Analyse 0:11:59 Hotlists 0:19:28 Hashtabelle mit einfach verketteten Listen 0:21:00 Duplikaterkennung 0:25:39 Bloom Filter

06 | 0:00:00 Start 0:00:13 Rückblick Vorlesung 02.05 0:02:40 Überblick heutige Vorlesung 0:03:36 Hashing 0:03:58 Hashtabellen 0:09:48 Ein (Über-)optimistischer Ansatz 0:15:00 Kollisionen 0:19:53 Kollisionsauflösung 0:21:13 Hashing mit verketteten Listen 0:26:12 Hashing mit verketteten Listen: Beispiel 0:31:30 Hashing mit verketteten Listen: Analyse 0:33:08 Etwas Wahrscheinlichkeitstheorie 0:46:18 Beispiel: Variante des Geburtstagsparadoxon 0:55:09 Mehr zum Geburtstagsparadoxon 0:56:50 Analyse für zufällige Hash-Funktionen 0:58:18 Zufällige Hash-Funktionen? 0:59:34 Universelles Hashing 0:59:40 Hashing mit linearer Suche 1:03:04 Der einfache Teil 1:08:10 Remove 1:16:07 Verketten vs. Lineare Suche 1:19:33 Hashtabellen für assoziative Arrays 1:22:29 Kryptographische Hashfunktionen

05 | 0:00:00 Start 0:00:17 Rückblick 0:03:35 Felder (Arrays) 0:09:16 Unbeschränkte Felder 0:20:49 Unbeschränkte Felder mit teilweise ungenutztem Speicher 0:25:26 Unbeschränkte Felder: Vergrößern 0:30:50 Unbeschränkte Felder: Verkleinern 0:34:46 Amprtisierte Komplexität für unbeschränkte Felder 0:38:34 Beweis: Account-Methode (Konto-Methode) 0:43:14 Amortisierte Analyse: verallgemeinert 0:45:56 Amortisierte Analyse: Diskussion 0:48:47 Stapel und Schlange 0:52:30 Stapel: Operationen 0:53:08 Stapel: Implementierungsvarianten 0:55:42 Stapel: Anwendungen 0:56:50 Warteschlangen / FIFO 0:57:34 FIFO: Implementierungsvarianten 0:59:00 Bounded FIFO 1:03:27 Warteschlangen: Anwendungen 1:04:17 Deque: Double-Ended Queues 1:05:42 Deque: Anwendungen 1:06:03 Vergleich: Listen - Felder 1:08:15 Vergleich Operationen 1:10:07 Ausblick: Weitere Repräsentationen von Folgen 1:10:50 Hashing (streuspeicherung) 1:11:50 Hashtabellen 1:17:52 Exkurs: Konventionen für Elemente 1:19:02 Hashing: Anwendung 1:20:15 Erste Ideen zu Implementierungen 1:21:23 Ein (über-)optimistischer Ansatz 1:25:17 Kollisionen

04 | 0:00:00 Start 0:00:05 P und NP 0:02:43 Folgen als Felder und Listen 0:06:11 Ausblick: Komplexität typischer Operationen 0:13:27 Listenglieder (Items) 0:21:00 Trick: Dummy Header 0:24:18 Die Listenklasse 0:27:12 Splice-Operation 0:35:09 Weitere Operationen: Einfach mit splice 0:37:32 Doch nicht so einfach? Speicherverwaltung ! 0:43:08 Items löschen 0:45:11 Elemente einfügen 0:47:59 Ganze Listen manipulieren 0:53:33 Suchen 0:57:14 Funktionalität vs. Effizienz 0:58:50 Einfach verkettete Listen 1:03:45 Listen: Zusammenfassung 1:05:48 Felder (Arrays)

03 | 0:00:00 Start 0:00:17 Roadmap 0:01:27 Tutorien 0:04:20 Effizienz von Algorithmen 0:09:09 Generelles Beispiel 0:10:38 Eingabegröße und Laufzeit 0:12:12 Genauer: Laufzeit 0:13:48 O - Notation 0:19:59 Omega Notation 0:20:16 Asymptotische Notationen 0:21:14 Nochmal anschaulich 0:21:18 Betrachtung über Grenzwerte 0:23:57 Ein Kniffligeres Beispiel 0:26:22 Basis des Logarithmus 0:27:21 Korrektheit von Algorithmen 0:28:19 Invarianten 0:40:50 Teile und Herrsche Paradigma 0:41:42 Rekursion: Laufzeit 0:43:35 Karatsuba-Ofman Multiplikation 0:45:12 Mastertheorem 0:48:11 Abschätzung von Rekurrenzen

02 | 0:00:00 Start 0:00:18 Rückblick Vorlesung 18.04 0:01:15 RAM vs. Compiler-Zwischensprache LLVM 0:05:03 Überblick heutige Vorlesung 0:06:16 Pseudocode 0:09:01 Design by Contract 0:16:14 Schleifeninvarianten 0:18:39 Beispiel 0:25:34 Rechenbeispiel 0:34:43 Zum power Algorithmus 0:37:32 Laufzeitanalyse / Rekurrenzen 0:42:10 Eine Rekurrenz für Teile und Herrsche 0:49:45 Master Theorem (einfache Form) 0:53:52 Beweisskizze: Allgemeines 0:59:37 Beweisskizze Fall d<b 1:02:24 Beweisskizze Fall d=b 1:05:09 Beweisskizze Fall d>b 1:07:27 Master Theorem Beispiele 1:08:56 Graphen 1:11:45 Bäume 1:13:18 Ein erster Graphalgorithmus 1:18:28 Beispiel 1:20:51 P und NP

01 | 0:00:00 Starten 0:00:10 Ankündigung 0:01:02 Rückblick - Vorlesung 16.04.2018 0:03:37 Hintergrund rekursiver Algorithmus 0:07:28 Ein rekursiver Algorithmus 0:10:35 Analyse 0:19:54 Karatsuba-Ofman-Multiplikation [1962] 0:23:44 Karatsuba-Ofman-Algorithmus 0:26:10 Beispiel 0:26:53 Analyse 0:29:22 Geht es noch besser? 0:36:02 Algorithm Engineering - Was hat das mit der Praxis zu tun? 0:39:35 Algorithmentheorie 0:40:27 Algorithmik als Algorithm Engineering 0:41:12 Zurück zur Langzahlmultiplikation 0:46:26 Skalierung 0:47:35 Einführendes und Überblick 0:49:07 (Asymptotische) Algorithmenanalyse 0:54:09 Zweite Vereinfachung: Asymptotik 1:07:05 O-Kalkül Rechenregeln 1:12:15 Maschinenmodell RAM (Random Access Machine) 1:21:01 Register 1:21:26 Hauptspeicher 1:21:53 Speicherzugriff 1:22:19 Rechnen 1:22:42 Bedingte Sprünge 1:23:35 ""Kleine"" ganze Zahlen? 1:24:06 Algorithmenanalyse im RAM-Modell 1:25:32 Mehr Maschinenmodell