26: Übung | Vorbereitung für die Klausur

Algorithmen 1, SS2015, Vorlesung

Algorithmen I, SS 2015, gehalten am 15.07.2015, Vorlesung 26 (+ Übung)

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

Algorithmen I, SS 2015, gehalten am 13.07.2015, Vorlesung 25

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

Algorithmen I, SS 2015, gehalten am 08.07.2015, Vorlesung 24

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

Algorithmen I, SS 2015, gehalten am 06.07.2015, Vorlesung 23

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

Algorithmen I, SS 2015, gehalten am 01.07.2015, Vorlesung 22

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

Algorithmen I, SS 2015, gehalten am 29.06.2015, Vorlesung 21

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

Algorithmen I, SS 2015, gehalten am 24.06.2015, Vorlesung 20

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

Algorithmen I, SS 2015, gehalten am 15.06.2015, Vorlesung 17

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

Algorithmen I, SS 2015, gehalten am 22.06.2015, Vorlesung 19

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

Algorithmen I, SS 2015, gehalten am 17.06.2015, Vorlesung 18

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

Algorithmen I, SS 2015, gehalten am 10.06.2015, Vorlesung 16

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

Algorithmen I, SS 2015, gehalten am 29.04.2015, Vorlesung 06 (nur Übung)

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

Algorithmen I, SS 2015, gehalten am 06.05.2015, Vorlesung 08

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

Algorithmen I, SS 2015, gehalten am 11.05.2015, Vorlesung 09

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

hubhopper

Algorithmen 1, SS2015, Vorlesung

hubhopper