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