Algorithmen 1, SS2015, Vorlesung

26: Übung | Vorbereitung für die Klausur

25: Vorlesung | 00:00:12 Ziele von PRAM-Algorithmen 00:01:47 Summe auf der PRAM 00:02:06 Das Prinzip von Arbeit und Laufzeit 00:05:17 Diskussion 00:06:06 Konvexe Hülle 00:07:03 Obere konvexe Hülle 00:13:32 Obere gemeinsame Tangente 00:16:14 Algorithmus UCH 00:33:27 Zusammenfassung 00:36:16 Kap. 14: Zusammenfassung 00:37:33 Zusammenfassung-Datenstruktur 00:42:51 Zusammenfassung- Algorithmen 00:45:24 Zusammenfassung- Entwurfstechniken I 00:53:01 Zusammenfassung- Entwurfstechniken II 00:58:56 Zusammenfassung- Analysentechniken 01:01:59 Zusammenfassung- weitere Techniken 01:06:36 Themen zur Klausur

24: Vorlesung | 00:00:07 Systematische Suche 00:00:24 Beispiel: Branch-and-Bound für das Rucksackproblem 00:00:32 Beispielrechnung 00:00:37 Lokale Suche – global denken, lokal handeln 00:00:48 Hill Climbing 00:00:50 Warum die Nachbarschaft wichtig ist 00:00:54 Jenseits von Hill Climbing 00:01:19 Evolutionäre Algorithmen 00:01:23 Zusammenfassung 00:01:25 Kap. 13: Parallele Algorithmen 00:01:27 Werbeblock 00:02:07 Rechnertypen 00:02:16 Gemeinsamer Speicher (shared memory) 00:02:31 Rechenmodell 00:04:23 PRAM-Modelle 00:05:42 Ziele von PRAM-Algorithmen 00:08:13 Summe auf der PRAM 00:21:56 Bewertung paralleler Algorithmen 00:24:16 Das Prinzip von Arbeit und Laufzeit 00:26:17 Summe auf der PRAM 00:34:26 Das Prinzip von Arbeit und Laufzeit (Work-Time-Principle) 00:37:46 Optimalität 00:40:20 Diskussion

23: Vorlesung | 00:00:07 Dynamische Programmierung – Aufbau aus Bausteinen 00:02:12 Systematische Suche 00:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem 00:20:42 Beispielrechnung 00:33:16 Branch-and-Bound – allgemein 00:34:48 Beispielrechnung 00:42:53 Lokale Suche – global denken, lokal handeln 00:47:44 Hill Climbing 00:49:08 Problem: Lokale Optima 00:51:55 Warum die Nachbarschaft wichtig ist 00:53:41 Jenseits von Hill Climbing 01:00:35 Evolutionäre Algorithmen 01:03:40 Zusammenfassung 01:10:03 Werbeblock 01:10:48 Kap. 13: Parallele Algorithmen 01:20:51 Rechnertypen 01:24:10 Gemeinsamer Speicher (shared memory) 01:25:07 Rechenmodell

22: Vorlesung | 00:00:07 Kap. 12: Generische Optimierungsansätze 00:00:23 Durchgehendes Beispiel: Rucksackproblem 00:01:19 Allgemein: Maximierungsproblem (L,f) 00:02:03 Black-Box-Löser 00:02:05 Ein einfaches Beispiel 00:02:07 Beispiel: Kürzeste Wege 00:02:09 Eine Anwendung – Tierfutter 00:02:17 Verfeinerungen 00:02:21 Ganzzahlige Lineare Programmierung 00:02:25 Umgang mit (M)ILPs 00:03:19 Nie zurückschauen – Greedy-Algorithmen 00:03:31 Optimale Greedy-Algorithmen 00:03:35 Beispiel: Rucksackproblem 00:03:43 Dynamische Programmierung – Aufbau aus Bausteinen 00:04:50 Beispiel: Rucksackproblem 00:08:34 Dynamische Programmierung 00:09:57 Beweis des Lemmas 00:12:27 Berechnung von P(i,C) elementweise 00:20:55 Rekonstruktion der Lösung 00:25:20 Beispiel 00:34:20 Algorithmenentwurf mittels dynamischer Programmierung 00:38:49 Anwendung dynamischer Programmierung 00:44:55 Gegenbeispiel: Teilproblemeigenschaft 00:46:25 Gegenbeispiel: Austauschbarkeit

21: Vorlesung | 00:00:07 Der Jarnik-Prim-Algorithmus 00:04:27 Analyse 00:05:08 Kruskals Algorithmus (1956) 00:06:27 Kruskals Algorithmus – Korrektheit 00:07:14 Union-Find Datenstruktur 00:08:30 Union-Find Datenstruktur – Erste Vision 00:09:58 Pfadkompression 00:10:26 Union by Rank 00:10:58 Analyse – nur Union by rank 00:11:35 Analyse – nur Pfadkompression 00:12:04 Analyse – Pfadkompression + Union by rank 00:15:22 Ackermannfunktion – Beispiele 00:18:31 Kruskal mit Union-Find 00:21:15 Union-Find Datenstruktur 00:22:56 Beispiel 00:27:45 Vergleich Jarnik-Prim – Kruskal 00:28:55 Analyse 00:29:42 Mehr MST-Algorithmen 00:33:54 Messungen, Zufallsgraph 00:36:06 Zusammenfassung 00:38:21 Kap. 12: Generische Optimierungsansätze 00:39:27 Durchgehendes Beispiel: Rucksackproblem 00:42:08 Allgemein: Maximierungsproblem (L, f) 00:43:24 Black-Box-Löser 00:44:36 Lineare Programmierung 00:47:38 Ein einfaches Beispiel 00:50:16 Beispiel: Kürzeste Wege 00:53:59 Eine Anwendung – Tierfutter 00:56:08 Verfeinerungen 00:57:49 Algorithmen und Implementierungen 00:59:30 Ganzzahlige Lineare Programmierung 01:01:04 Beispiel: Rucksackproblem 01:02:04 Umgang mit (M)ILPs 01:03:45 Nie zurückschauen – Greedy-Algorithmen 01:04:38 Optimale Greedy-Algorithmen 01:05:16 Beispiel: Rucksackproblem

20: Vorlesung | 00:00:07 Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte 00:00:17 Allgemeines Korrektheitskriterium 00:00:49 Zyklische Graphen (10.2 im Buch) 00:01:01 Von überall nach überall 00:01:16 Kürzeste Wege: Zusammenfassung 00:01:20 Straßennetzwerke 00:01:21 Ideen für Routenplanung 00:02:01 Beispiel 00:02:06 Transit-Node Routing 00:02:40 Kap. 11: Minimale Spannbäume 00:03:01 Minimale Spannbäume (MST) 00:03:06 Minimale spannende Wälder (MSF) 00:03:07 Anwendungen 00:03:19 MST-Kanten auswählen und verwerfen 00:05:55 Der Jarnik-Prim-Algorithmus 00:18:18 Analyse 00:23:38 Kruskals Algorithmus (1956) 00:27:05 Kruskals Algorithmus – Korrektheit 00:28:08 Union-Find Datenstruktur 00:31:53 Union-Find Datenstruktur – Erste Version 00:36:33 Pfadkompression 00:39:00 Union by Rank 00:40:43 Analyse – nur Union by rank 00:45:11 Analyse – Pfadkompression + Union by rank

17: Vorlesung | 00:00:07 Kap. 9: Graphtraversierung 00:00:21 Graphtraversierung als Kantenklassifizierung 00:01:52 Breitensuche 00:06:16 Repräsentation des Baums 00:11:52 Repräsentation von Q und Q‘ mittels FIFO 00:13:22 Alternative Repräsentation von Q und Q‘ 00:14:43 Tiefensuche 00:15:55 Tiefensuchschema für G = (V,E) 00:21:14 DFS-Baum 00:28:47 DFS-Nummerierung 00:31:18 Fertigstellungszeit 00:33:33 Kantenklassifizierung bei DFS 00:42:34 Topologische Sortierung 00:45:36 Topologisches Sortieren mittels DFS 00:50:09 Starke Zusammenhangskomponenten 00:54:16 Mehr DFS-basierte Linearzeitalgorithmen 00:57:22 BFS – DFS 01:00:43 Kap. 10: Kürzeste Wege 01:05:08 Anwendungen 01:06:26 Grundlagen 01:07:59 Kantengewichte grösser gleich Null 01:08:50 Dijkstras Algorithmus 01:10:47 Korrektheit der Bindfäden 01:12:29 Edsger Wybe Dijkstra (1930-2002) 01:15:57 Allgemeine Definitionen 01:18:33 Kante (u,v) relaxieren 01:21:33 Dijkstras Algorithmus: Pseudocode 01:24:06 Beispiel

19: Vorlesung | 00:00:07 Dijkstra: Laufzeit 00:02:21 Laufzeit 00:03:55 Negative Kosten 00:04:43 Allgemeines Korrektheitskriterium 00:09:44 Algorithmen brutal – Bellmann-Ford-Algorithmus für beliebige Kantengewichte 00:11:00 Allgemeines Korrektheitskriterium 00:12:16 Negative Kreise finden 00:14:35 Beispiel 00:18:37 Bellmann-Ford – Laufzeit 00:18:57 Laufzeit 00:19:53 Zyklische Graphen (10.2 im Buch) 00:22:04 Von überall nach überall 00:24:40 Kürzeste Wege: Zusammenfassung 00:25:56 Mehr zu kürzesten Wegen 00:28:01 Exkurs: Routing in Straßennetzwerken 00:29:58 Straßennetzwerke 00:30:57 Distanz zu einem Zielknoten t 00:32:58 Ideen für Routenplanung 00:40:00 Straßennetzwerke 00:43:10 Approach: Transit-Node Routing 00:44:09 Beispiel 00:46:48 Erste Beobachtung 00:48:04 Zweite Beobachtung 00:48:25 Transit-Node Routing 00:52:41 Beispiel: Transitknoten 00:53:54 Experimente 00:58:20 Offene Fragen 00:58:58 Kap. 11: Minimale Spannbäume 01:00:18 Minimale Spannbäume (MST) 01:02:26 Minimale spannende Wälder (MSF) 01:03:11 Anwendungen 01:09:31 MST-Kanten auswählen und verwerfen 01:15:58 Der Jarnik-Prim-Algorithmus

18: Vorlesung | 00:00:07 Tiefensuche 00:00:27 Tiefensuchschema für G = (V,E) 00:01:21 DFS-Baum 00:01:22 Fertigstellungszeit 00:01:26 DFS-Nummerierung 00:01:43 Topologische Sortierung 00:01:50 Topologische Sortieren mittels DFS 00:01:58 Kap. 10: Kürzeste Wege 00:02:00 BFS – DFS 00:02:30 Anwendungen 00:02:42 Kantengewichte größer gleich Null 00:02:52 Dijkstras Algorithmus 00:02:57 Allgemeine Definitionen 00:03:07 Kante (u,v) relaxieren 00:03:53 Dijkstras Algorithmus: Pseudocode 00:05:04 Korrektheit 00:19:14 Implementierung? 00:20:34 Prioritätsliste 00:21:37 Implementierung BFS mit PQ statt FIFO 00:25:48 Beispiel 00:29:06 Dijkstra: Laufzeit 00:32:19 Laufzeit 00:38:41 Analyse im Mittel 00:39:30 Monotone ganzzahlige Prioritätslisten 00:40:41 Negative Kosten 00:41:51 Zurück zu Basiskonzepten (Abschnitt 10.1 im Buch) 00:44:40 Mehr Basiskonzepte

16: Vorlesung | 00:00:07 Kap. 8: Repräsentation von Graphen 00:00:49 Notation und Konvention 00:01:02 Ungerichtete – gerichtete Graphen 00:01:06 Operationen 00:01:28 Weitere Operationen 00:01:31 Kantenfolgenrepräsentation 00:02:20 Adjazenzfelder 00:02:25 Kantenliste – Adjazenzfeld 00:02:40 Beispiel 00:02:45 Operationen für Adjazenzfelder 00:02:49 Kantenanfragen 00:02:52 Adjazenzlisten 00:03:10 Adjazenzlisten aufrüsten 00:04:18 Customization (Zuschneiden) 00:08:43 Beispiel: DAG-Erkennung 00:15:55 Adjazenz-Matrix 00:22:41 Pfade zählen mittels LA 00:26:05 Beispiel, wo Graphentheorie bei LA hilft 00:28:47 Implizite Repräsentation 00:29:50 Beispiel 00:30:14 Zusammenhangstest für Intervallgraphen 00:34:29 Beispiel 00:36:37 Graphenrepräsentation: Zusammenfassung 00:37:15 Kapitel 9: Graphtraversierung 00:39:03 Graphtraversierung als Kantenklassifizierung 00:39:58 Breitensuche

06: Übung | - Kurze Wiederholung, Nachtrag zum O-Kalkül - Teile- und Herrsche-Paradigma, Karatsuba-Ofman - Rekurrenzen - Amortisierte Analyse - Unbounded Arrays

08: Vorlesung | 00:00:10 Erinnerung 00:07:08 Hashing mit Linearer Suche (Linear Probing) 00:10:34 Der einfache Teil 00:21:14 Remove 00:30:59 Verketten – Lineare Suche 00:36:48 Perfektes Hashing 00:37:03 Mehr Hashing 00:38:43 Hashtabellen für assoziative Arrays 00:44:43 Kryptographische Hashfunktionen

09: Vorlesung | 00:00:07 Sortieren & Co 00:00:07 Formaler 00:06:02 Anwendungsbeispiele 00:07:51 Beispiele aus Kurs/Buch 00:10:48 Überblick 00:12:09 Einfache Sortieralgorithmen 00:15:25 Sentinels am Beispiel Sortieren durch Einfügen 00:16:24 Einfache Sortieralgorithmen 00:18:51 Analyse 00:21:04 Sortieren durch Mischen 00:24:20 Beispiel 00:27:47 Mischen 00:33:29 Untere Schranken 00:35:15 Eine vergleichsbasierte untere Schranke 00:38:31 Baumbasierte Sortierer-Darstellung 00:45:29 Beweis 00:53:18 Randomisierung, Mittlere Ausführungszeit 00:54:02 Quicksort – erster Versuch 00:58:14 Quicksort – Analyse im schlechtesten Fall 01:00:14 Schlechtesten Fall: Beispiel 01:00:59 Quicksort – Analyse im besten Fall 01:03:27 Quicksort – zufälliger Pivot 01:04:51 Satz: Quicksort hat erwartete Laufzeit O(nlogn) 01:06:58 Beweissatz 1: Rekurrenzen 01:20:49 Exkurs: Harmonische Summe

10: Vorlesung | 00:00:10 Erinnerung: Sortieren 00:06:28 Erinnerung: Quicksort 00:07:52 Quicksort: Effiziente Implementierung 00:20:44 Beispiel: Partitionierung, k = 1 00:23:48 Beispiel: Rekursion 00:25:04 Größerer Basisfall 00:30:01 Halbrekursive Implementierung 00:33:26 Quadratische Komplexität bei gleichen Elementen? 00:34:10 Quicksort: Effiziente Implementierung 00:35:29 Quadratische Komplexität bei gleichen Elementen? 00:36:35 Halbrekursive Implementierung 00:39:44 Vergleich Quicksort und Mergesort 00:45:57 Benchmark 00:49:27 Übung 00:49:32 Roadmap 00:50:01 Organisation 00:51:15 Wiederholung: Wahrscheinlichkeitstheorie 00:53:26 Permutationen von 1, … 5 00:55:19 Sortieren – Intuition 00:56:27 Sortieren durch Auswählen, Selection Sort 01:02:11 Sortieren durch Einfügen, Insertion Sort 01:07:55 Permutationen – Inversionen 01:09:22 Insertion Sort – Average Case 01:16:09 Permutationen 01:18:10 Insertion Sort – Average Case

11: Vorlesung | 00:00:07 Erinnerung 00:01:57 Erinnerung Quicksort-Partitionierung 00:04:02 Auswahl (Selection) 00:06:16 Beispiel 00:07:38 Auswahl – Anwendungen 00:10:18 Quickselect 00:10:52 Auswahl (Selection) 00:12:27 Quickselect 00:18:23 Beispiel 00:20:26 Quickselect – Analyse 00:24:15 Mehr zum Auswahlproblem 00:30:49 Durchbrechen der unteren Schranke – Ganzzahliges Sortieren 00:33:20 Schlüssel 0..K-1 – Eimer-Sortieren (bucket sort) 00:36:33 Beispiel: K = 4 00:37:54 Array-Implementierung 00:43:01 Beispiel 00:44:35 K hoch d Schlüssel: Least-Significant-Digit Radix-Sortieren 00:49:35 LSD-Radix-Sort Beispiel 00:52:50 Mehr zu ganzzahligem Sortieren 00:56:02 Sortieren: vergleichsbasiert – ganzzahlig 00:58:48 Mehr zu Sortieren 01:02:43 Was haben wir jenseits von Sortieren gelernt? 01:05:43 Prioritätslisten (priority Queues) 01:07:03 Prioritätslisten – Anwendungen 01:09:54 Binäre Heaps 01:14:24 Implizite Baum-Repräsentation 01:15:31 Pseudocode 01:17:18 Einfügen

12: Vorlesung und Übung | 00:00:24 Prioritätslisten 00:00:48 Prioritätslisten (priority queues) 00:01:26 Prioritätslisten – Anwendungen 00:01:48 Binäre Heaps 00:03:33 Implizite Baum-Repräsentation 00:04:56 Pseudocode 00:06:07 Einfügen 00:21:01 deleteMin: Beispiel 00:23:49 Binärer Heap – Analyse 00:25:16 Binärer Heap – Konstruktion 00:29:12 Beispiel: Binärer Heap – Konstruktion 00:30:01 Binärer Heap – Konstruktion 00:34:46 Ein nützlicher Rechentrick 00:37:57 Heapsort 00:40:57 Heapsort: Beispiel 00:42:27 Heapsort – Quicksort – Mergesort 00:46:01 Adressierbare Prioritätslisten 00:48:09 Adressierbare Prioritätslisten: Anwendungen 00:49:50 Adressierbare Binäre Heaps 00:51:35 Adressierbare Prioritätslisten – Laufzeiten 00:52:16 Prioritätslisten: Mehr 00:55:32 Prioritätslisten: Zusammenfassung 00:55:50 Was haben wir jenseits von Prioritätslisten gelernt? Übung 00:56:17 Übung 00:56:31 Roadmap 00:56:50 Organisation 00:57:12 Sortieren durch Mischen 00:57:27 Merge Sort 00:58:46 Tatsächliche Laufzeit einer Implementierung 01:00:28 Quicksort – erster Versuch 01:01:16 Quicksort – Analyse im schlechtesten Fall 01:01:24 Schlechtester Fall: Beispiel 01:01:50 Einige Quicksort-Analysen 01:02:58 Vorgefertigte Sortieralgorithmen in aktuellen Programmiersprachen 01:03:54 C++ 01:04:20 Java 01:04:39 Dual Pivot Quicksort 01:07:32 Partitionierung mit 2 Pivot 01:12:21 Einige Quicksort-Analysen 01:14:13 Kennzahlen der Vorsortiertet und adaptive Sortierverfahren 01:14:17 Adaptives Sortieren 01:20:14 Runs 01:24:48 Adaptives Sortieren

13: Vorlesung und Übung | Vorlesung 00:00:08 Prioritätslisten 00:00:31 Prioritätslisten (priority Queues) 00:00:52 Prioritätslisten – Anwendungen 00:00:54 Binäre Heaps 00:01:54 Implizite Baum-Repräsentation 00:02:48 deletMin: Beispiel 00:02:54 Binärer Heap – Analyse 00:03:00 Beispiel: Binärer Heap – Konstruktion 00:03:01 Binärer Heap – Konstruktion 00:03:15 Ein nützlicher Rechentrick 00:03:18 Heapsort: Beispiel 00:03:22 Heapsort 00:04:03 Heapsort – Quicksort – Mergesort 00:04:28 Adressierbare Prioritätslisten 00:04:33 Adressierbare Prioritätslisten: Anwendungen 00:04:37 Adressierbare Binäre Heaps 00:05:15 Prioritätslisten: Zusammenfassung 00:05:48 Was haben wir jenseits von Prioritätslisten gelernt? 00:05:50 Sortierte Folgen 00:12:16 Statisch: Sortiertes Feld mit binärer Suche 00:17:26 Binäre Suche – Beispiel: k = 15 00:20:13 Dynamische Sortierte Folgen – Grundoperationen 00:21:13 Mehr Operationen 00:23:58 Noch mehr Operationen 00:25:43 Abgrenzung 00:28:52 Sortierte Folgen – Anwendungen 00:30:20 Anwendungsbeispiel: Best Fit Bin Packing 00:33:50 Binäre Suchbäume 00:36:54 Varianten, Bemerkungen 00:37:30 locate(k) 00:39:34 locate(k) – anderes Beispiel 00:40:00 Invariante von locate(k) 00:40:38 Ergebnisberechnung von locate(k) 00:41:25 Laufzeit von locate(k) 00:42:59 Naives Einfügen 00:44:45 Beispiel Übung 00:44:45 Roadmap 00:46:28 Perfekter Binärbaum 00:53:13 (Max)Heap und Suchbaum 00:53:17 Perfekter Binärbaum 00:53:42 (Max)Heap und Suchbaum 00:55:21 Heapsort mit Max-Heap 00:55:25 (Max)Heap und Suchbaum 00:56:04 Heapsort 00:57:53 Heapsort mit Max-Heap 01:05:30 Adressierbare binäre Heaps 01:05:42 Anwendungsbeispiel 01:08:06 Adressierbare binäre Heaps

14: Vorlesung | 00:00:11 Sortierte Folgen 00:01:26 Statisch: Sortiertes Feld mit binärer Suche 00:01:59 Dynamische Sortierte Folgen – Grundoperationen 00:02:52 Abgrenzung 00:03:26 Binäre Suchbäume 00:06:03 Suchbäume balancieren 00:09:36 items 00:12:59 Initialisierung 00:14:47 Locate 00:17:51 Lockte – Laufzeit 00:23:17 Einfügen – Algorithmenskizze 00:27:58 Einfügen – Beispiel 00:33:39 Einfügen – Korrektheit 00:36:05 Einfügen – Implementierungsdetails 00:39:42 Einfügen – Pseudocode 00:49:04 Entfernen – Algorithmenskizze 00:55:48 Entfernen – Beispiel 00:59:11 Entfernen – Korrektheit 01:02:59 Einfügen und Entfernen – Laufzeit 01:03:33 (a,b)-Bäume, Implementierungsdetails 01:09:06 Mehr Operationen 01:13:43 Amortisierte Analyse von Insert und remove 01:14:55 Erweiterte (augmentierte) Suchbäume 01:18:02 Elternzeiger 01:20:43 Teilbaumgrößen 01:24:05 Beispiel 01:25:28 Zusammenfassung 01:26:01 Mehr zu sortierte Folgen 01:28:05 Ein paar Zahlen 01:29:20 Was haben wir noch gelernt?

15: Vorlesung und Übung | 00:00:11 Wiederholung: Suchbäume balancieren 00:00:38 (a,b)-Bäume 00:01:20 Items 00:02:58 Initialisierung 00:03:02 Locate 00:03:04 Locate – Laufzeit 00:03:26 Einfügen – Algorithmenskizze 00:03:30 Einfügen – Beispiel 00:04:42 Entfernen – Beispiel 00:05:10 Einfügen und Entfernen – Laufzeit 00:05:27 Erweiterte (augmentierte) Suchbäume 00:05:47 Elternzeiger 00:06:10 Teilbaumgrößen 00:06:37 Zusammenfassung 00:06:46 Was haben wir noch gelernt? 00:07:58 Kap. 8: Repräsentation von Graphen (Einleitung) 00:14:55 Repräsentation von Graphen 00:16:20 Notation und Konventionen 00:18:00 Unterrichtete – gerichtete Graphen 00:18:58 Operationen 00:20:39 Weitere Operationen 00:22:19 Kantenfolgenrepräsentation 00:24:37 Adjazenzfelder 00:27:39 Kantenliste – Adjazenzfeld 00:34:14 Beispiel 00:35:49 Operationen für Adjazenzfelder 00:41:27 Kantenanfragen 00:43:09 Adjazenzlisten 00:45:22 Adjazenzlisten aufrüsten 00:47:53 Übung: Roadmap 00:48:13 (Weitere) Traversierungen von Binärbäumen 00:54:58 Die Anzahl binärer Suchbäume 00:59:50 Balancierte binäre Suchbäume: Rot-Schwarz-Bäume 01:15:22 Datenstrukturen in der Wirklichkeit