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

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

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

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

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