23 Folgen

Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:

Ergebnisüberprüfung (Checkers) und Zertifizierung
Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
Grundbegriffe des Algorithm Engineering
Effektive Umsetzung verketteter Listen
Unbeschränkte Arrays, Stapel, und Warteschlangen
Hashtabellen: mit Verkettung, linear probing, universelles Hashing
Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
Selektion: quickselect
Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)

Algorithmen 1, SS2019, Vorlesung Karlsruher Institut für Technologie

    • Kurse
    • 5.0, 1 Bewertung

Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:

Ergebnisüberprüfung (Checkers) und Zertifizierung
Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
Grundbegriffe des Algorithm Engineering
Effektive Umsetzung verketteter Listen
Unbeschränkte Arrays, Stapel, und Warteschlangen
Hashtabellen: mit Verkettung, linear probing, universelles Hashing
Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
Selektion: quickselect
Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)

    • video
    23: Algorithmen I, Übung, SS 2019, 24.07.2019

    23: Algorithmen I, Übung, SS 2019, 24.07.2019

    23 |
    0:00:00 Start
    0:00:13 Übung: Überblick
    0:03:26 Dijkstras Algorithmus
    0:07:19 Bellmann Ford Algorithmus
    0:14:50 Minimale Spannbäume
    0:20:31 Steinerbäume
    0:27:20 Problem des Handlungsreisenden (TSP)

    • 31 Min.
    • video
    22: Algorithmen I, Vorlesung, SS 2019, 22.07.2019

    22: Algorithmen I, Vorlesung, SS 2019, 22.07.2019

    22 |
    0:00:00 Start
    0:00:23 Generische Optimierungsansätze
    0:05:36 Rucksackproblem
    0:09:28 Maximierungsprolem
    0:12:42 Black-Box-Löser
    0:17:38 Lineare Programmierung
    0:24:53 Kürzeste Wege
    0:29:29 Tierfutter
    0:35:21 Algorithmen und Implementierungen
    0:39:09 Ganzzahlige Lineare Programmierung
    0:53:05 Greedy-Algorithmen
    1:00:00 Dynamische Programmierung
    1:17:32 Algorithmenentwurf mittels dynamischer Programmierung
    1:23:01 Systematische Suche

    • 1 Std. 24 Min.
    • video
    21: Algorithmen I, Vorlesung, SS 2019, 17.07.2019

    21: Algorithmen I, Vorlesung, SS 2019, 17.07.2019

    21 |
    0:00:00 Start
    0:00:10 Rückblick
    0:01:58 Heutige Vorlesung
    0:03:31 Minimale Spannbäume
    0:08:34 MST-Kanten auswählen und verwerfen
    0:22:22 Jarnik-Prim-Algorithmus
    0:37:10 Analyse - Jarnik-Prim-Algorithmus
    0:38:04 Kruskals-Algorithmus
    0:45:14 Kruskals Algorithmus - Korrektheit
    0:49:51 Union-Find Datenstruktur
    1:03:25 Pfadkompression
    1:08:34 Union by Rank
    1:10:11 Analyse - nur Union by Rank
    1:11:33 Analyse - nur Pfadkompression
    1:12:05 Analyse - Pfadkompression und Union by Rank
    1:15:21 Ackermannfunktion - Beispiele
    1:15:44 Kruskal mit Union-Find
    1:21:09 Vergleich Jarnik-Prim vs. Kruskal
    1:23:00 Mehr MST-Algorithmen
    1:25:11 Zusammenfassung

    • 1 Std. 27 Min.
    • video
    20: Algorithmen I, Vorlesung, SS 2019, 15.07.2019

    20: Algorithmen I, Vorlesung, SS 2019, 15.07.2019

    20 |
    0:00:00 Start
    0:01:21 Kürzeste Wege: Definition
    0:02:23 Dijkstras Algorithmus. Pseudocode
    0:08:12 Dijkstra: negative Kantengewichte
    0:17:02 Monotone ganzzahlige Prioritätslisten
    0:19:49 Negative Zyklen
    0:21:55 Zurück zu Basiskonzepten
    0:26:31 Allgemeines Korrektheitskriterium
    0:31:09 Bellman-Ford-Algorithmus
    0:39:29 Beispiel
    0:43:57 Bellman-Ford: Laufzeit
    0:45:30 Azyklische Graphen
    0:49:38 Von überall nach überall
    0:52:15 Kürzeste Wege: Zusammenfassung
    0:57:10 Exkurs: Routing in Straßennetzwerken
    1:01:56 Ideen für Routenplanung
    1:03:47 Ansatz: Transit-Node Routing
    1:09:15 Zweite Beobachtung
    1:17:04 Offene Fragen
    1:18:36 Minimale Spannbäume (MST)
    1:23:59 Minimal aufspannende Wälder (MSF)

    • 1 Std. 25 Min.
    • video
    19: Algorithmen I, Vorlesung, SS 2019, 03.07.2019

    19: Algorithmen I, Vorlesung, SS 2019, 03.07.2019

    19 |
    0:00:00 Start
    0:00:11 Rückblick: Kürzeste Wege
    0:02:00 Dijkstras Algorithmus
    0:02:54 Allgemeine Definition
    0:07:38 Kante relaxieren
    0:13:02 Dijkstras Algorithmus: Pseudocode
    0:16:44 Beispiel
    0:23:52 Korrektheit
    0:37:29 Implementierung
    0:40:10 Prioritätsliste
    0:46:50 Beispiel
    0:49:18 Dijkstra: Laufzeit
    0:58:32 Analyse im Mittel
    0:59:32 Monotone ganzzahlige Prioritätslisten
    1:01:18 Negative Kosten
    1:03:38 Zurück zu Basiskonzepten
    1:06:34 Allgemeines Korrektheitskriterium
    1:08:46 Bellman-Ford Algorithmus

    • 1 Std. 9 Min.
    • video
    18: Algorithmen I, Vorlesung, SS 2019, 01.07.2019

    18: Algorithmen I, Vorlesung, SS 2019, 01.07.2019

    18 |
    0:00:00 Start
    0:07:02 Graph-Traversierung
    0:11:13 Breitensuche
    0:13:13 Tiefensuche
    0:21:56 DFS-Baum
    0:28:14 DFS-Nummerierung
    0:38:39 Topologische Sortierung
    0:43:27 Topologisches Sortieren mittels DFS
    0:55:01 Begriff Zusammenhang
    1:02:26 BFS vs DFS
    1:07:16 Kürzeste Wege : Definition
    1:17:22 Dijkstras Algorithmus

    • 1 Std. 26 Min.

Kundenrezensionen

5.0 von 5
1 Bewertung

1 Bewertung

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie