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

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