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