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)
Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

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

    • Kurse

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)
Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

    • video
    23: Algorithmen 1, Vorlesung, SS 2018, 18.07.2018

    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 Std. 14 Min.
    • video
    22: Algorithmen 1, Vorlesung, SS 2018, 16.07.2018

    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 Std. 26 Min.
    • video
    21: Algorithmen 1, Übung, SS 2018, 04.07.2018

    21: Algorithmen 1, Übung, SS 2018, 04.07.2018

    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)

    • 41 Min.
    • video
    18: Algorithmen 1, Vorlesung, SS 2018, 25.06.2018

    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 Std. 24 Min.
    • video
    19: Algorithmen 1, Vorlesung, SS 2018, 27.06.2018

    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 Std. 29 Min.
    • video
    20: Algorithmen 1, Vorlesung, SS 2018, 02.07.2018

    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 Std. 17 Min.

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie