25 Folgen

Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
Dozenten: Jun.-Prof. Dennis Hofheinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

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

    • Kurse

Der Inhalt der Vorlesung orientiert sich am Buch »Algorithms and Data Structures - The Basic Toolbox« von Kurt Mehlhorn und Peter Sanders. Der Studierende
- kennt und versteht grundlegende, häufig benötigte Algorithmen, ihren Entwurf, Korrektheits- und Effizienzanalyse, Implementierung, Dokumentierung und Anwendung,
- wendet die im Modul Grundlagen der Informatik (Bachelor Informationswirtschaft) erworbenen Programmierkenntnisse auf nichttriviale Algorithmen an,
- wendet die in Grundbegriffe der Informatik (Bachelor Informatik) bzw. Grundlagen der Informatik (Bachelor Informationswirtschaft) und den Mathematikvorlesungen erworbenen mathematischen
Herangehensweise an die Lösung von Problemen an. Schwerpunkte sind hier formale Korrektheitsargumente und eine mathematische Effizienzanalyse.
Dozenten: Jun.-Prof. Dennis Hofheinz | Karlsruher Institut für Technologie (KIT), Institut für Theoretische Informatik | Vorlesungsaufzeichnung: KIT | WEBCAST: http://webcast.kit.edu

    • video
    25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016

    25: Algorithmen I, Vorlesung, SS 2016, am 20.07.2016

    25 |
    0:00:00 Starten
    0:00:06 Prioritätslisten
    0:03:14 Binäre Heaps
    0:07:39 Adressierbare Prioritätslisten
    0:08:26 Adressierbare Binäre Heaps
    0:09:05 Sortierte Folgen
    0:10:42 Binäre Suchbäume
    0:16:08 Repräsentation von Graphen
    0:23:11 Graphentraversierung
    0:30:07 Kürzeste Wege
    0:41:22 Minimale Spannbäume
    0:46:37 Generische Optimierungsansätze
    0:57:13 Zusammenfassung

    • 58 Min.
    • video
    24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016

    24: Algorithmen I, Vorlesung, SS 2016, am 13.07.2016

    24 |
    0:00:00 Starten
    0:00:06 Kap. 13: Zusammenfassung
    0:03:32 Zusammenfassung - Datenstrukturen
    0:06:22 Zusammenfassung - Algorithmen
    0:09:41 Zusammenfassung - Entwurfstechniken I
    0:12:53 Zusammenfassung - Entwurfstechniken II
    0:14:53 Zusammenfassung - Analysetechniken
    0:18:06 Zusammenfassung - weitere Techniken
    0:18:50 Schnelldurchlauf
    0:19:32 Amuse Geule
    0:20:05 Exkurs: Pseudocode
    0:21:47 Exkurs O-Kalkül, die Erste
    0:24:04 Algorithmentheorie
    0:25:44 Invarianten
    0:26:03 Master Theorem
    0:29:27 Form Follows Function
    0:30:56 Felder (Arrays)
    0:31:46 Amortisierte Komplexität unbeschr. Felder
    0:32:39 Beweis: Konto-Methode (oder Versicherung)
    0:34:35 Hashing (Streuspeicherung)
    0:39:27 Sortieren & Co

    • 48 Min.
    • video
    23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016

    23: Algorithmen I, Vorlesung, SS 2016, am 11.07.2016

    Die Vorlesung (23, 11.07.16, SS2016) konnte wegen technischer Probleme nicht aufgezeichnet werden. Der Vorlesungsinhalt ist aber identisch mit der Aufzeichnung vom 06.07.2015 (SS2015)

    23 |
    0:00:00 Starten
    0:00:07 Dynamische Programmierung – Aufbau aus Bausteinen
    0:02:12 "Systematische SuchSystematische Suche"
    0:06:14 Beispiel: Branch-and-Bound für das Rucksackproblem
    0:20:42 Beispielrechnung
    0:33:16 Branch-and-Bound – allgemein
    0:34:48 Beispielrechnung
    0:42:53 Lokale Suche – global denken, lokal handeln
    0:47:44 Hill Climbing
    0:49:08 Problem: Lokale Optima
    0:51:55 Warum die Nachbarschaft wichtig ist
    0:53:41 Jenseits von Hill Climbing
    1:00:35 Evolutionäre Algorithmen
    1:03:40 Zusammenfassung
    1:10:03 Werbeblock
    1:10:48 Kap. 13: Parallele Algorithmen
    1:20:51 Rechnertypen
    1:24:10 Gemeinsamer Speicher (shared memory)
    1:25:07 Rechenmodell

    • 1 Std. 29 Min.
    • video
    22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016

    22: Algorithmen I, Vorlesung und Übung, SS 2016, am 06.07.2016

    22 |
    0:00:00 Starten
    0:00:10 Erinnerung VL 04.07.2016
    0:04:13 Wiederholung Beispiel: Rucksackproblem
    0:05:15 Nie zurückschauen - Greedy-Algorithmen
    0:08:50 Beispiel: Rucksackproblem (1)
    0:17:16 Dynamische Programmierung - Aufbau aus Bausteinen
    0:18:29 Beispiel: Rucksackproblem (2)
    0:21:09 Dynamische Programmierung
    0:22:37 Beweis des Lemmas
    0:29:10 Berechnung von P(i,C) elementweise
    0:33:21 Rekonstruktion des Lösung
    0:34:54 Beispiel
    0:40:36 Beginn Übung 11
    0:40:41 Roadmap
    0:41:22 Schwierige Probleme
    0:46:15 Erinnerung: Lineare Programme
    0:47:48 LP graphisch
    0:52:37 Erinnerung: Travelling Salesman Problem
    0:53:59 Ein ILP für TSP
    0:59:25 Heuristiken
    1:01:14 Ameisen Algorithmen
    1:04:50 Vertex Cover
    1:06:25 Approximation
    1:07:21 Eine Approximation für Vertex Cover
    1:10:53 Metaheuristiken und Nachbarschaften
    1:12:22 Nachbarschaftsheuristiken
    1:19:10 Lokale Suche für Vertex Cover
    1:20:13 Tabu-Suche für Vertex Cover
    1:22:29 Zusammenfassung

    • 1 Std. 23 Min.
    • video
    21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016

    21: Algorithmen I, Vorlesung, SS 2016, am 04.07.2016

    21 |
    0:00:00 Starten
    0:00:06 Erinnerung VL 29.06.2016
    0:02:08 Kruskals Algorithmus
    0:04:38 Union-Find Datenstruktur
    0:18:24 Pfadkompression
    0:20:57 Union by Rank
    0:26:19 Analyse Union by Rank bzw. Pfadkompression
    0:40:55 Kruskal mit Union-Find
    0:45:05 Beispiel
    0:49:09 Vergleich Jarník-Prim - Kruskal
    0:50:55 Mehr MST-Algorithmen
    0:54:03 Zusammenfassung
    0:56:05 Kap. 12: Generische Optimierungsansätze
    0:56:47 Durchgehendes Beispiel: Rucksackproblem
    0:58:30 Allgemein: Maximierungsproblem
    1:00:28 Black-Box-Löser
    1:01:45 Lineare Programmierung
    1:04:22 Ein einfaches Beispiel
    1:07:13 Beispiel: Kürzester Weg
    1:09:27 Eine Anwendung - Tierfutter
    1:11:04 Verfeinerungen
    1:12:48 Algorithmen und Implementierungen
    1:14:14 Ganzzahlige Lineare Programmierung
    1:15:09 Beispiel: Rucksackproblem
    1:16:20 Umgang mit (M)ILPs

    • 1 Std. 18 Min.
    • video
    20: Algorithmen I, Vorlesung und Übung, SS 2016, am 29.06.2016

    20: Algorithmen I, Vorlesung und Übung, SS 2016, am 29.06.2016

    20 |
    0:00:00 Starten
    0:00:06 Erinnerung VL 27.06.2016
    0:02:09 Kap. 11: Minimale Spannbäume
    0:02:28 Minimale Spannbäume (MST)
    0:03:22 Minimale aufspannende Wälder (MSF)
    0:03:36 Anwendungen
    0:04:57 MST-Kanten auswählen und verwerfen: Die Schnitteigenschaft (Cut Property)
    0:12:19 MST-Kanten auswählen und verwerfen: Die Kreiseigenschaft (Cycle Property)
    0:15:54 Der Jarník-Prim-Algorithmus
    0:28:39 Analyse
    0:32:00 Kruskals Algorithmus (1956)
    0:37:47 Kruskals Algorithmus - Korrektheit
    0:40:56 Union-Find Datenstruktur
    0:44:15 Beginn Übung 10
    0:44:15 Kürzeste Wege Algorithmen: Bellman-Ford
    0:45:40 Bellman-Ford: Pseudo-Code
    0:46:40 Bellman-Ford: Korrektheit (Beweis-Idee)
    0:48:53 Bellman-Ford: Beispiel
    0:53:03 Bellman-Ford: Bestimmung eines negativen Kreises
    0:55:03 Minimale Spannbäume
    0:57:00 Minimale Spannbäume: Jarník-Prim
    0:58:37 Minimale Spannbäume: Kruskal
    1:00:00 Steinerbäume
    1:05:42 Steinerbaum: Was kann schief gehen?
    1:10:09 Problem des Handlungsreisenden (TSP)

    • 1 Std. 15 Min.

Top‑Podcasts in Kurse

Zuhörer haben auch Folgendes abonniert:

Mehr von Karlsruher Institut für Technologie