Algorithmen 1, SS2016, Vorlesung Karlsruher Institut für Technologie (KIT)

25 |
0:00:00 Starten
0:00:06 Prioritätslisten
0:03:14 Binäre Heaps
0:07:39 Adressierbare Prioritätslisten
0:08:26 Adressierbare Binäre Heaps
0:09:05 Sortierte Folgen
0:10:42 Binäre Suchbäume
0:16:08 Repräsentation von Graphen
0:23:11 Graphentraversierung
0:30:07 Kürzeste Wege
0:41:22 Minimale Spannbäume
0:46:37 Generische Optimierungsansätze
0:57:13 Zusammenfassung

24 |
0:00:00 Starten
0:00:06 Kap. 13: Zusammenfassung
0:03:32 Zusammenfassung - Datenstrukturen
0:06:22 Zusammenfassung - Algorithmen
0:09:41 Zusammenfassung - Entwurfstechniken I
0:12:53 Zusammenfassung - Entwurfstechniken II
0:14:53 Zusammenfassung - Analysetechniken
0:18:06 Zusammenfassung - weitere Techniken
0:18:50 Schnelldurchlauf
0:19:32 Amuse Geule
0:20:05 Exkurs: Pseudocode
0:21:47 Exkurs O-Kalkül, die Erste
0:24:04 Algorithmentheorie
0:25:44 Invarianten
0:26:03 Master Theorem
0:29:27 Form Follows Function
0:30:56 Felder (Arrays)
0:31:46 Amortisierte Komplexität unbeschr. Felder
0:32:39 Beweis: Konto-Methode (oder Versicherung)
0:34:35 Hashing (Streuspeicherung)
0:39:27 Sortieren & Co

Die Vorlesung (23, 11.07.16, SS2016) konnte wegen technischer Probleme nicht aufgezeichnet werden. Der Vorlesungsinhalt ist aber identisch mit der Aufzeichnung vom 06.07.2015 (SS2015)

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

22 |
0:00:00 Starten
0:00:10 Erinnerung VL 04.07.2016
0:04:13 Wiederholung Beispiel: Rucksackproblem
0:05:15 Nie zurückschauen - Greedy-Algorithmen
0:08:50 Beispiel: Rucksackproblem (1)
0:17:16 Dynamische Programmierung - Aufbau aus Bausteinen
0:18:29 Beispiel: Rucksackproblem (2)
0:21:09 Dynamische Programmierung
0:22:37 Beweis des Lemmas
0:29:10 Berechnung von P(i,C) elementweise
0:33:21 Rekonstruktion des Lösung
0:34:54 Beispiel
0:40:36 Beginn Übung 11
0:40:41 Roadmap
0:41:22 Schwierige Probleme
0:46:15 Erinnerung: Lineare Programme
0:47:48 LP graphisch
0:52:37 Erinnerung: Travelling Salesman Problem
0:53:59 Ein ILP für TSP
0:59:25 Heuristiken
1:01:14 Ameisen Algorithmen
1:04:50 Vertex Cover
1:06:25 Approximation
1:07:21 Eine Approximation für Vertex Cover
1:10:53 Metaheuristiken und Nachbarschaften
1:12:22 Nachbarschaftsheuristiken
1:19:10 Lokale Suche für Vertex Cover
1:20:13 Tabu-Suche für Vertex Cover
1:22:29 Zusammenfassung

21 |
0:00:00 Starten
0:00:06 Erinnerung VL 29.06.2016
0:02:08 Kruskals Algorithmus
0:04:38 Union-Find Datenstruktur
0:18:24 Pfadkompression
0:20:57 Union by Rank
0:26:19 Analyse Union by Rank bzw. Pfadkompression
0:40:55 Kruskal mit Union-Find
0:45:05 Beispiel
0:49:09 Vergleich Jarník-Prim - Kruskal
0:50:55 Mehr MST-Algorithmen
0:54:03 Zusammenfassung
0:56:05 Kap. 12: Generische Optimierungsansätze
0:56:47 Durchgehendes Beispiel: Rucksackproblem
0:58:30 Allgemein: Maximierungsproblem
1:00:28 Black-Box-Löser
1:01:45 Lineare Programmierung
1:04:22 Ein einfaches Beispiel
1:07:13 Beispiel: Kürzester Weg
1:09:27 Eine Anwendung - Tierfutter
1:11:04 Verfeinerungen
1:12:48 Algorithmen und Implementierungen
1:14:14 Ganzzahlige Lineare Programmierung
1:15:09 Beispiel: Rucksackproblem
1:16:20 Umgang mit (M)ILPs

20 |
0:00:00 Starten
0:00:06 Erinnerung VL 27.06.2016
0:02:09 Kap. 11: Minimale Spannbäume
0:02:28 Minimale Spannbäume (MST)
0:03:22 Minimale aufspannende Wälder (MSF)
0:03:36 Anwendungen
0:04:57 MST-Kanten auswählen und verwerfen: Die Schnitteigenschaft (Cut Property)
0:12:19 MST-Kanten auswählen und verwerfen: Die Kreiseigenschaft (Cycle Property)
0:15:54 Der Jarník-Prim-Algorithmus
0:28:39 Analyse
0:32:00 Kruskals Algorithmus (1956)
0:37:47 Kruskals Algorithmus - Korrektheit
0:40:56 Union-Find Datenstruktur
0:44:15 Beginn Übung 10
0:44:15 Kürzeste Wege Algorithmen: Bellman-Ford
0:45:40 Bellman-Ford: Pseudo-Code
0:46:40 Bellman-Ford: Korrektheit (Beweis-Idee)
0:48:53 Bellman-Ford: Beispiel
0:53:03 Bellman-Ford: Bestimmung eines negativen Kreises
0:55:03 Minimale Spannbäume
0:57:00 Minimale Spannbäume: Jarník-Prim
0:58:37 Minimale Spannbäume: Kruskal
1:00:00 Steinerbäume
1:05:42 Steinerbaum: Was kann schief gehen?
1:10:09 Problem des Handlungsreisenden (TSP)