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

23 |
0:00:00 Start
0:00:52 Heutige Vorlesung
0:01:52 Zusammenfassung
0:08:58 Propositional Logic
0:13:39 Staisfiability
0:16:08 Satisfiabilty - Example
0:19:27 Satisfiability - A Practical Example
0:27:15 Satisfiability - Hardness
0:35:41 Satisfiability - History
0:39:37 Applications of SAT solving
0:42:50 SAT Solving in the news
0:44:28 Pythadorean Triples
0:53:13 Arithmetic Progressions
0:56:39 Background: Van der Eaerden Numbers
1:00:11 Graph Coloring
1:02:10 Graph Coloring: Encoding in SAT
1:03:57 Graph Coloring: Example
1:04:00 Graph Coloring: Input
1:05:16 Graph Coloring: Output
1:06:44 Klausur
1:11:26 Klausurbonus

22 |
0:00:00 Start
0:00:28 Rückblick Vorlesung 09.07.
0:03:19 Dynamische Programmierung – Aufbau aus Bausteinen
0:09:15 Dynamische Programmierung
0:16:46 Rekonstruktion der Lösung
0:19:07 Algorithmenentwurf mittels dynamischer Programmierung
0:23:33 Anwendungen dynamischer Programmierung
0:28:33 Gegenbeispiel: Teilproblemeigenschaft
0:34:30 Gegenbeispiel: Austauschbarkeit
0:43:54 Systematische Suche
0:51:25 Beispiel: Branch-and-Bound für das Rucksackproblem
1:03:34 Branch-and-Bound allgemein
1:06:20 Lokale Suche – global denken, lokal handeln
1:10:17 Hill Climbing
1:15:15 Problem: Lokale Optima
1:18:14 Jenseits von Hill-Climbing
1:21:27 Evolutionäre Algorithmen

21 |
0:00:00 Start
0:02:30 Dijkstras Algorithmus
0:10:26 Bellman Ford Algorithmus
0:22:16 Minimale Spannbäume
0:27:49 Steinerbäume
0:35:38 Problem des Handlungsreisenden (TSP)

18 |
0:00:00 Starten
0:00:32 Rückblich Vorlesung 18.06
0:02:48 Kürzeste Wege: Definition
0:04:13 Dijkstras Algorithmus
0:08:01 Dijkstra: Negative Kantengewichte
0:21:54 Negative Zyklen
0:28:26 Zurück zu Basiskonzepten
0:31:34 Mehr Basiskonzepte
0:33:21 Allgemeines Korrektheitskriterium
0:33:52 Bellman-Ford-Algorithmus
0:40:31 Negative Kreise
0:53:56 Azyklische Graphen
0:58:07 Kürzeste Wege: Zusammenfassung
1:03:52 Exkurs: Routing in Straßennetzwerken
1:10:33 Distanz zu einem Zielknoten
1:11:56 Ideen für Routenplanung
1:13:54 Transit Node Routing

19 |
0:00:00 Start
0:02:10 Rückblick Vorlesung 25.06.
0:05:34 Minimale Spannbäume
0:11:04 Minimale aufspannende Wälder
0:17:03 MST-Kanten auswählen und verwerfen
0:33:48 Der Jarnik-Prim-Algorithmus
0:47:00 Analyse
0:48:53 Kruskals Algorithmus
1:01:44 Kruskals Algorithmus – Korrektheit
1:04:35 Union-Find Datenstruktur
1:19:03 Pfadkompression
1:22:33 Union by Rank

20 |
0:00:00 Start
0:00:12 Rückblick
0:19:10 heutige Vorlesung
0:19:43 Analyse – Pfadkompression und Union by Rank
0:28:50 Ackermannfunktion – Beispiele
0:30:58 Kruskal mit Union-Find
0:39:37 Vergleich mit Jarnik-Prim vs. Kruskal
0:42:42 Mehr MST-Algorithmen
0:48:16 Zusammenfassung
0:51:08 Generische Optimierungsprobleme
0:53:39 Durchgehendes Beispiel: Rucksackproblem
0:56:52 Allgemein: Maximierungsproblem
1:00:36 Black-Box-Löser
1:02:10 Lineare Programmierung
1:10:08 Ein einfaches Beispiel
1:15:08 Eine Anwendung: Tierfutter