Algorithmen 1, SS2019, Vorlesung

Karlsruher Institut für Technologie (KIT)
  • 0,0 (0)
  • КУРСЫ
Algorithmen 1, SS2019, Vorlesung

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)

  1. 30.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 мин.

  2. 25.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 ч. 25 мин.

  3. 18.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 ч. 28 мин.

  4. 16.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 ч. 25 мин.

  5. 05.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 ч. 10 мин.

  6. 04.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 ч. 26 мин.

  7. 27.06.2019 · ВИДЕО

    17: Algorithmen I, Vorlesung, SS 2019, 26.06.2019

    17 | 0:00:00 Start 0:00:05 Rückblick und Überblick 0:01:35 Graphen 0:02:12 Repräsentation von Graphen 0:02:33 Kantenfolgenrepräsentation 0:03:31 Adjazenzfelder 0:05:59 Kantenliste -> Adjazenzfeld 0:07:29 Adjazenzlisten 0:13:10 Customization (Zuschneiden) 0:13:53 Beispiel: DAG-Erkennung 0:23:23 Adjazenz-Matrix 0:31:24 Pfade zählen mittels linearer Algebra (LA) 0:35:54 Beispiel, wo Graphentheorie bei LA hilft 0:38:56 Implizite Repräsentation 0:40:53 Zusammenhangstest für Intervallgraphen 0:43:46 Beispiel 0:45:13 Graphpräsentation: Zusammenfassung 0:52:00 Graph-Traversierung 0:58:59 Breitensuche 1:07:32 Repräsentation des Baums 1:16:41 Repräsentation von Q und Q' mittels FIFO 1:19:17 Tiefensuche 1:24:26 DFS-Baum

    1 ч. 27 мин.

  8. 25.06.2019 · ВИДЕО

    16: Algorithmen I, Vorlesung, SS 2019, 24.06.2019

    16 | 0:00:00 Start 0:00:11 Wiederholung 0:11:16 Locate 0:19:22 Einfügen-Algorithmenskizze 0:50:36 Zusammenfassung 0:53:43 Graphen 0:58:43 Graphen-Anwendung 1:05:15 Operationen 1:10:05 Kantenfolgenrepräsentation 1:13:28 Adjazenzfelder

    1 ч. 31 мин.
См. все (23)

Об этом подкасте

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)

Информация

  • Автор
    Karlsruher Institut für Technologie (KIT)
  • Годы выхода
    2 тыс.
  • Выпуски
    23
  • Ограничения
    Без ненормативной лексики
  • Сайт подкаста
    Algorithmen 1, SS2019, Vorlesung

Еще от провайдера «Karlsruher Institut für Technologie»

Чтобы прослушивать выпуски с ненормативным контентом, войдите в систему.

Следите за новостями подкаста

Войдите в систему или зарегистрируйтесь, чтобы следить за подкастами, сохранять выпуски и получать последние обновления.
Выберите страну или регион

Африка, Ближний Восток и Индия

Азиатско-Тихоокеанский регион

Европа

Латинская Америка и страны Карибского бассейна

США и Канада