Algorithmen 1, SS2018, Vorlesung

Algorithmen 1, SS2018, Vorlesung

By Karlsruher Institut für Technologie (KIT)Education
Download on the App Store

All Algorithmen 1, SS2018, Vorlesung episodes

  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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
  • 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