Algorithmen und Datenstrukturen

Flüsse in Netzwerken 2

(00:00:00) >: Beispiel für schlechte Laufzeit

(00:09:39) >: Der Algorithmus von Edmonds-Karp

(00:14:47) >: Distanz wird größer

(00:39:21) >: Zusammenhang zwischen Matching und Fluss

(00:45:43) >: Heiratsproblem

Recording from: 14.07.2009

Lecturer: Prof. Dr. Martin Hofmann

Flüsse in Netzwerken

(00:00:00) >: Fluesse in Netzwerken

(00:17:38) >: Flusseigenschaften

(00:20:01) >: Restnetzwerke und Erweiterungspfade

(00:30:40) >: Erweiterungspfad

(00:39:13) >: Max-Flow-Min-Cut Theorem

(01:03:47) >: Ford-Fulkerson-Methode

(01:22:00) >: Algorithmus von Edmonds-Karp

Recording from: 09.07.2009

Lecturer: Prof. Dr. Martin Hofmann

Kürzeste Wege

(00:00:00) >: Wiederholung

(00:06:35) >: Algorithmus von Dijkstra

(00:13:51) >: Korrektheit und Laufzeit von Dijkstra

(00:36:31) >: Negative Kantengewichte

(00:47:20) >: Algorithmus von Bellman-Ford

(01:00:10) >: Kürzester Weg zwischen allen Paaren

(01:04:36) >: Dynamische Programmierung

(01:18:55) >: Algorithmus von Floyd-Warshall

Recording from: 02.07.2009

Lecturer: Prof. Dr. Martin Hofmann

Minimale Spannbäume, Kürzeste Wege

(00:00:00) >: Wiederholung

(00:20:39) >: Kruskal's Algorithmus

(00:40:41) >: Kürzeste Wege

(01:05:21) >: Der Algorithmus von Dijkstra

Recording from: 30.06.2009

Lecturer: Prof. Dr. Martin Hofmann

Tiefensuche, Minimale Spannbäume, Algorithmus von Prim

(00:00:00) >: Wiederholung

(00:06:03) >: Topologische Sortierung

(00:14:21) >: Zerlegung in starke Zusammenhangskomponenten

(00:24:48) >: Beispiel DFS

(00:26:40) >: Korrektheitsbeweis

(00:35:19) >: Spannbäume

(00:53:56) >: Grundalgorithmus

(00:58:24) >: Finden sicherer Kanten

(01:08:15) >: Algorithmus von Prim

Recording from: 25.06.2009

Lecturer: Prof. Dr. Martin Hofmann

Algorithmen auf Graphen

(00:00:00) >: Breitensuche

(00:33:54) >: Tiefensuche

(00:49:29) >: Topologische Sortierung

(01:05:00) >: Graph mit SCC

Recording from: 23.06.2009

Lecturer: Prof. Dr. Martin Hofmann

Downloads: Folien (pdf) 1.3 MB

Amortisierte Analyse, Algorithmen auf Graphen

(00:00:00) >: Wiederholung

(00:30:45) >: Amortisierte Kosten von Make-Set und Link

(00:42:23) >: Backtracking

(01:04:09) >: Algorithmen auf Graphen

Recording from: 16.06.2009

Lecturer: Prof. Dr. Martin Hofmann

Amortisierungs-Analyse

(00:00:00) >: Wiederholung

(00:13:45) >: Aggregat-Methode

(00:21:20) >: Potenzial-Methode

(00:55:57) >: Optimierung union-by-rank

(01:07:35) >: Analyse von union-by-rank

Recording from: 09.06.2009

Lecturer: Prof. Dr. Martin Hofmann

Dynamische Programmierung

(00:00:00) >: Wiederholung Greedy

(00:14:28) >: Korrektheit Greedy

(00:30:51) >: Dynamische Programmierung

(00:42:00) >: Beispiel Dynam. Programmierung

(00:53:46) >: Fibonaccizahlen

(00:56:50) >: Längste gemeinsame Teilfolge lgT

(01:08:37) >: Berechnung mit dynam.Programmierung

(01:23:55) >: Zusammenfassung Dynam.Programmierung

Recording from: 28.05.2009

Lecturer: Prof. Dr. Martin Hofmann

Allgemeine Entwurfs - und Optimierungsmethoden

(00:00:00) >: Widerholung

(00:33:48) >: Greedy - Algorithmen

(00:45:40) >: Korrektheitsbeweis

(01:03:06) >: Huffman-Codes

(01:12:27) >: Der Huffman-Algorithmus

Recording from: 26.05.2009

Lecturer: Prof. Dr. Martin Hofmann

Downloads: Folien (pdf) 0.8 MB

Datenstrukturen Hashtabellen

(00:00:00) >: Direkte Adressierung

(00:31:37) >: Hashfunktionen

(00:58:02) >: Offene Adressierung

(01:19:30) >: Analyse der Offenen Adressierung

Recording from: 19.05.2009

Lecturer: Prof. Dr. Martin Hofmann

Rot-Schwarz-Bäume

(00:00:00) >: Wiederholung

(00:21:35) >: Rot-Schwarz-Bäume

(00:35:32) >: Einfügen R-S-Bäume

(00:53:06) >: Löschen R-S-Bäume

(01:01:28) >: Beispiel für Löschen

(01:22:09) >: Hashtabellen

Recording from: 14.05.2009

Lecturer: Prof. Dr. Martin Hofmann

Kapitel 3 Datenstrukturen

(00:00:00) >: Datenstrukturen

(00:29:33) >: AVL - Bäume

(00:55:20) >: B-Bäume

(01:22:52) >: Rot-Schwarz-Bäume

Recording from: 12.05.2009

Lecturer: Prof. Dr. Martin Hofmann

Downloads: Folien (pdf) 1.2 MB

Sortieren und Suchen Teil 2

(00:00:00) >: Wiederholung

(00:16:53) >: Untere Schranke für vergleichsbasiertes Sortieren

(00:44:15) >: Untere schranke für Maximum und Miniumum

(01:07:53) >: Vergleichskomplexität der Selektionsaufgabe

Recording from: 05.05.2009

Lecturer: Prof. Dr. Martin Hofmann

Heap-Sort und Quick-Sort

(00:00:00) >: Heap-Sort

(00:12:08) >: Heap-Insert

(00:17:00) >: Quicksort

(00:28:10) >: Partition

(00:49:14) >: Laufzeit von Quicksort

(00:55:20) >: Randomisiertes Quicksort

(01:04:40) >: Laufzeit Randomized-Quicksort

Recording from: 30.04.2009

Lecturer: Prof. Dr. Martin Hofmann

Wiederholung + Kapitel 2: Sortieren und Suchen

(00:00:00) >: Wiederholung

(00:09:01) >: Hauptsatz der Master - Methode

(00:37:01) >: Matrizenmultiplikation mit divide-and-conquer

(00:49:40) >: Heapsort

(01:17:27) >: Prozedur Heapify: Laufzeitanalyse

Recording from: 28.04.2009

Lecturer: Prof. Dr. Martin Hofmann

Downloads: Folien (pdf) 0.6 MB

Sortieren durch Mischen

(00:00:00) >: Teile und Herrsche

(00:16:56) >: Prozedur Merge

(00:24:22) >: Analyse vom Merge - Sort

(00:38:09) >: Asymptotik:Definition von O

(00:54:36) >: Asymptotik: Ausdrücke mit O

(01:18:42) >: Asymptotik und Induktion

Recording from: 23.04.2009

Lecturer: Prof. Dr. Martin Hofmann

Einführung + Sortieren durch Einfügen

(00:00:00) >: Überblick über die Vorlesung

(00:29:56) >: Einführung

(00:37:17) >: Sortieren durch Einfügen

(00:50:44) >: Laufzeitanalyse

Recording from: 21.04.2009

Lecturer: Prof. Dr. Martin Hofmann

Downloads: Folien (pdf) 0.4 MB

RSS-Feed abonnieren: