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. 2019. 07. 30. · 비디오

    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. 2019. 07. 25. · 비디오

    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. 2019. 07. 18. · 비디오

    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. 2019. 07. 16. · 비디오

    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. 2019. 07. 05. · 비디오

    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. 2019. 07. 04. · 비디오

    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. 2019. 06. 27. · 비디오

    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. 2019. 06. 25. · 비디오

    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)
  • 방송 연도
    2019년
  • 에피소드
    23
  • 등급
    전체 연령 사용가
  • 웹사이트 보기
    Algorithmen 1, SS2019, Vorlesung

Karlsruher Institut für Technologie의 콘텐츠 더 보기

무삭제판 에피소드를 청취하려면 로그인하십시오.

이 프로그램의 최신 정보 받기

프로그램을 팔로우하고, 에피소드를 저장하고, 최신 소식을 받아보려면 로그인하거나 가입하십시오.
국가 또는 지역 선택

아프리카, 중동 및 인도

아시아 태평양

유럽

라틴 아메리카 및 카리브해

미국 및 캐나다