Zur Navigation springen

Algorithmen und Datenstrukturen

Achtung. Diese Aufzeichnung ist aus dem Semester: SoSe09

Videostream und Folien Flüsse in Netzwerken 2

  1. (00:00:00) >
    Beispiel für schlechte Laufzeit
  2. (00:09:39) >
    Der Algorithmus von Edmonds-Karp
  3. (00:14:47) >
    Distanz wird größer
  4. (00:39:21) >
    Zusammenhang zwischen Matching und Fluss
  5. (00:45:43) >
    Heiratsproblem
Aufzeichnung vom: 14.07.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Flüsse in Netzwerken

  1. (00:00:00) >
    Fluesse in Netzwerken
  2. (00:17:38) >
    Flusseigenschaften
  3. (00:20:01) >
    Restnetzwerke und Erweiterungspfade
  4. (00:30:40) >
    Erweiterungspfad
  5. (00:39:13) >
    Max-Flow-Min-Cut Theorem
  6. (01:03:47) >
    Ford-Fulkerson-Methode
  7. (01:22:00) >
    Algorithmus von Edmonds-Karp
Aufzeichnung vom: 09.07.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Kürzeste Wege

  1. (00:00:00) >
    Wiederholung
  2. (00:06:35) >
    Algorithmus von Dijkstra
  3. (00:13:51) >
    Korrektheit und Laufzeit von Dijkstra
  4. (00:36:31) >
    Negative Kantengewichte
  5. (00:47:20) >
    Algorithmus von Bellman-Ford
  6. (01:00:10) >
    Kürzester Weg zwischen allen Paaren
  7. (01:04:36) >
    Dynamische Programmierung
  8. (01:18:55) >
    Algorithmus von Floyd-Warshall
Aufzeichnung vom: 02.07.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Minimale Spannbäume, Kürzeste Wege

  1. (00:00:00) >
    Wiederholung
  2. (00:20:39) >
    Kruskal's Algorithmus
  3. (00:40:41) >
    Kürzeste Wege
  4. (01:05:21) >
    Der Algorithmus von Dijkstra
Aufzeichnung vom: 30.06.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Tiefensuche, Minimale Spannbäume, Algorithmus von Prim

  1. (00:00:00) >
    Wiederholung
  2. (00:06:03) >
    Topologische Sortierung
  3. (00:14:21) >
    Zerlegung in starke Zusammenhangskomponenten
  4. (00:24:48) >
    Beispiel DFS
  5. (00:26:40) >
    Korrektheitsbeweis
  6. (00:35:19) >
    Spannbäume
  7. (00:53:56) >
    Grundalgorithmus
  8. (00:58:24) >
    Finden sicherer Kanten
  9. (01:08:15) >
    Algorithmus von Prim
Aufzeichnung vom: 25.06.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Algorithmen auf Graphen

  1. (00:00:00) >
    Breitensuche
  2. (00:33:54) >
    Tiefensuche
  3. (00:49:29) >
    Topologische Sortierung
  4. (01:05:00) >
    Graph mit SCC
Aufzeichnung vom: 23.06.2009
Dozent: Prof. Dr. Martin Hofmann
Download:
Folien (pdf), 1.2 MB

Videostream und Folien Amortisierte Analyse, Algorithmen auf Graphen

  1. (00:00:00) >
    Wiederholung
  2. (00:30:45) >
    Amortisierte Kosten von Make-Set und Link
  3. (00:42:23) >
    Backtracking
  4. (01:04:09) >
    Algorithmen auf Graphen
Aufzeichnung vom: 16.06.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Amortisierungs-Analyse

  1. (00:00:00) >
    Wiederholung
  2. (00:13:45) >
    Aggregat-Methode
  3. (00:21:20) >
    Potenzial-Methode
  4. (00:55:57) >
    Optimierung union-by-rank
  5. (01:07:35) >
    Analyse von union-by-rank
Aufzeichnung vom: 09.06.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Dynamische Programmierung

  1. (00:00:00) >
    Wiederholung Greedy
  2. (00:14:28) >
    Korrektheit Greedy
  3. (00:30:51) >
    Dynamische Programmierung
  4. (00:42:00) >
    Beispiel Dynam. Programmierung
  5. (00:53:46) >
    Fibonaccizahlen
  6. (00:56:50) >
    Längste gemeinsame Teilfolge lgT
  7. (01:08:37) >
    Berechnung mit dynam.Programmierung
  8. (01:23:55) >
    Zusammenfassung Dynam.Programmierung
Aufzeichnung vom: 28.05.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Allgemeine Entwurfs - und Optimierungsmethoden

  1. (00:00:00) >
    Widerholung
  2. (00:33:48) >
    Greedy - Algorithmen
  3. (00:45:40) >
    Korrektheitsbeweis
  4. (01:03:06) >
    Huffman-Codes
  5. (01:12:27) >
    Der Huffman-Algorithmus
Aufzeichnung vom: 26.05.2009
Dozent: Prof. Dr. Martin Hofmann
Download:
Folien (pdf), 0.7 MB

Videostream und Folien Datenstrukturen Hashtabellen

  1. (00:00:00) >
    Direkte Adressierung
  2. (00:31:37) >
    Hashfunktionen
  3. (00:58:02) >
    Offene Adressierung
  4. (01:19:30) >
    Analyse der Offenen Adressierung
Aufzeichnung vom: 19.05.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Rot-Schwarz-Bäume

  1. (00:00:00) >
    Wiederholung
  2. (00:21:35) >
    Rot-Schwarz-Bäume
  3. (00:35:32) >
    Einfügen R-S-Bäume
  4. (00:53:06) >
    Löschen R-S-Bäume
  5. (01:01:28) >
    Beispiel für Löschen
  6. (01:22:09) >
    Hashtabellen
Aufzeichnung vom: 14.05.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Kapitel 3 Datenstrukturen

  1. (00:00:00) >
    Datenstrukturen
  2. (00:29:33) >
    AVL - Bäume
  3. (00:55:20) >
    B-Bäume
  4. (01:22:52) >
    Rot-Schwarz-Bäume
Aufzeichnung vom: 12.05.2009
Dozent: Prof. Dr. Martin Hofmann
Download:
Folien (pdf), 1.2 MB

Videostream und Folien Sortieren und Suchen Teil 2

  1. (00:00:00) >
    Wiederholung
  2. (00:16:53) >
    Untere Schranke für vergleichsbasiertes Sortieren
  3. (00:44:15) >
    Untere schranke für Maximum und Miniumum
  4. (01:07:53) >
    Vergleichskomplexität der Selektionsaufgabe
Aufzeichnung vom: 05.05.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Heap-Sort und Quick-Sort

  1. (00:00:00) >
    Heap-Sort
  2. (00:12:08) >
    Heap-Insert
  3. (00:17:00) >
    Quicksort
  4. (00:28:10) >
    Partition
  5. (00:49:14) >
    Laufzeit von Quicksort
  6. (00:55:20) >
    Randomisiertes Quicksort
  7. (01:04:40) >
    Laufzeit Randomized-Quicksort
Aufzeichnung vom: 30.04.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Wiederholung + Kapitel 2: Sortieren und Suchen

  1. (00:00:00) >
    Wiederholung
  2. (00:09:01) >
    Hauptsatz der Master - Methode
  3. (00:37:01) >
    Matrizenmultiplikation mit divide-and-conquer
  4. (00:49:40) >
    Heapsort
  5. (01:17:27) >
    Prozedur Heapify: Laufzeitanalyse
Aufzeichnung vom: 28.04.2009
Dozent: Prof. Dr. Martin Hofmann
Download:
Folien (pdf), 0.6 MB

Videostream und Folien Sortieren durch Mischen

  1. (00:00:00) >
    Teile und Herrsche
  2. (00:16:56) >
    Prozedur Merge
  3. (00:24:22) >
    Analyse vom Merge - Sort
  4. (00:38:09) >
    Asymptotik:Definition von O
  5. (00:54:36) >
    Asymptotik: Ausdrücke mit O
  6. (01:18:42) >
    Asymptotik und Induktion
Aufzeichnung vom: 23.04.2009
Dozent: Prof. Dr. Martin Hofmann

Videostream und Folien Einführung + Sortieren durch Einfügen

  1. (00:00:00) >
    Überblick über die Vorlesung
  2. (00:29:56) >
    Einführung
  3. (00:37:17) >
    Sortieren durch Einfügen
  4. (00:50:44) >
    Laufzeitanalyse
Aufzeichnung vom: 21.04.2009
Dozent: Prof. Dr. Martin Hofmann
Download:
Folien (pdf), 0.4 MB
RSS-Feed abonnieren: RSS-Feed abonieren

Die Unterrichtsmitschau und didaktische Forschung ist eine Einrichtung des Departments für Pädagogik und Rehabilitation der Ludwig Maximilians Universität München. Auf VideoOnline finden Sie ein Vorlesungsverzeichnis aller Vorlesungen und Veranstaltungen der LMU, die von uns aufgezeichnet werden. Loggen Sie sich über das LMU Portal ein, um Zugriff auf die Videos Ihrer Studienfächer zu bekommen.