Algorithmen 1, SS2018, Vorlesung

By Karlsruher Institut für Technologie (KIT)Education

Algorithmen 1, SS2018, Vorlesung episodes

July 19, 2018 23: Algorithmen 1, Vorlesung, SS 2018, 18.07.2018
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
1 hr 15 min
July 17, 2018 22: Algorithmen 1, Vorlesung, SS 2018, 16.07.2018
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
1 hr 27 min
July 09, 2018 21: Algorithmen 1, Übung, SS 2018, 04.07.2018
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)
42 min
July 06, 2018 18: Algorithmen 1, Vorlesung, SS 2018, 25.06.2018
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
1 hr 25 min
July 06, 2018 19: Algorithmen 1, Vorlesung, SS 2018, 27.06.2018
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
1 hr 30 min
July 06, 2018 20: Algorithmen 1, Vorlesung, SS 2018, 02.07.2018
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
1 hr 18 min
June 20, 2018 17: Algorithmen 1, Vorlesung, SS 2018, 18.06.2018
17 |
0:00:00 Starten
0:00:11 Rückblick Vorlesung 11.06
0:02:13 BFS vs. DFS
0:04:05 Begriff ""Zusammenhang""
0:11:16 Überblick heutige Vorlesung
0:12:03 Kürzeste Wege
0:15:11 Definition
0:24:05 Grundlagen
0:28:02 Dijkstra Algorithmus
0:32:10 Edsger Wybe Dijkstra
0:42:03 Allgemeine Definition
0:45:37 Kante relaxieren
0:49:42 Pseudocode
1:08:15 Implementierung
1:18:38 Laufzeit
1 hr 25 min
June 19, 2018 16: Algorithmen 1, Übung, SS 2018, 13.06.2018
16 |
0:00:00 Starten
0:00:05 Roadmap
0:00:25 Übungsklausur
0:02:58 Graphen und Relationen
0:04:22 Knotengrad
0:05:04 Beispiele
0:08:26 Handshaking Lemma
0:11:58 Adjazenz- und Inzidenzmatrix
0:20:29 Grpahen als Matrizen
0:25:17 Pfade und Kreise
0:26:13 Eulersche und Hamiltonsche Kreise
0:28:11 Satz von Euler
0:36:05 Breitensuche
0:47:48 Tiefensuche
58 min
June 18, 2018 15: Algorithmen 1, Vorlesung, SS 2018, 11.06.2018
15 |
0:00:00 Starten
0:00:09 Organisatorisches
0:03:12 Randbemerkung zu WWDC 2018
0:05:32 Rückblick Vorlesung 06.06.
0:07:56 Überblick heutige Vorlesung
0:08:18 Adjazenz-Matrix
0:08:52 Pfade zählen mittels LA
0:09:38 Graphentheorie und LA
0:15:39 Zusammenhangstest für Intervallgraphen
0:18:18 Beispiel
0:19:52 Graphenpräsentation: Zusammenfassung
0:21:30 Graph-Traversierung
0:23:14 Graphtraversierung als Kantenklassifizierung
0:26:23 Breitensuche
0:31:57 Repräsentation des Baumes
0:41:59 Repräsentation von Q und Q' mittels FIFO
0:45:45 Tiefensuche
0:47:04 Tiefensuchschema für G=(V,E)
0:52:43 DFS-Baum
1:00:08 DFS-Nummerierung
1:03:55 Fertigstellungszeit
1:06:03 Kantenklassifizierung bei DFS
1:07:47 Fertigstellungszeit
1:08:58 Topologishce Sortierung
1:13:38 Topologisches Sortieren mittels DFS
1:16:50 Starke Zusammenhangskomponenten
1:21:17 MehrDFS-basierte Linearzeitalgorithmen
1:22:37 BFS vs. DFS
1 hr 25 min
June 12, 2018 14: Algorithmen 1, Vorlesung, SS 2018, 06.06.2018
14 |
0:00:00 Starten
0:00:16 Rückblick 04.06.
0:02:56 Graphen
0:05:51 Königesberger Brückenproblem
0:10:00 Graphen Anwendung
0:13:43 Repräsentation von Graphen
0:19:19 Notation und Konvention
0:22:01 Ungerichtete vs gerichtete Graphen
0:23:01 Operationen
0:27:17 Kantenfolgenrepräsentation
0:30:53 Repräsentation von Graphen
0:31:35 Adjazenzfelder
0:40:55 Beispiel
0:47:58 Kantenanfragen
0:48:56 Adjazenzlisten
0:52:17 Adjazenzlisten Aufrüsten
0:55:18 Customisation
0:57:31 Beispiel: DAG-Erkennung
1:10:55 Adjazenz Matrix
1 hr 24 min