Algorithmen und Datenstrukturen

Geometrische Algorithmen

(00:02:44) >: Grundbegriffe (Punkte, Vektoren, Strecken,...)

(00:11:12) >: Line Intersection - Feststellen, ob sich zwei Strecken schneiden

(00:42:20) >: Konvexe Hülle

(00:50:40) >: Graham's Scan (Anwendung der konvexen Hülle)

(00:59:34) >: Jarvis' March (Anwendung der konvexen Hülle)

(01:04:56) >: Punkte mit kleinstem Abstand finden - über divide and conquer Methode

Date: 12.07.2016

Lecturer: Prof. Dr. Martin Hofmann

Ford-Fulkerson Algorithmus, Bipartite Matchings

(00:01:18) >: Suche in Zeichenketten: Problemstellung

(00:03:34) >: Notation und Grundlagen

(00:09:11) >: String matching: naives Verfahren

(00:11:18) >: Rabin-Karp

(00:35:43) >: Endliche Automaten

(00:39:01) >: String-matching mit Automaten

(00:54:44) >: Knuth-Morris-Pratt Verfahren

(01:17:18) >: Boyer-Moore Verfahren

(01:22:21) >: Heuristik "Gutes Suffix"

Date: 06.07.2016

Lecturer: Prof. Dr. Martin Hofmann

Flüsse in Netzwerken

Date: 05.07.2016

Lecturer: Prof. Dr. Martin Hofmann

Algorithmen von Bellman-Fort und Floyd-Warshall, Flüsse in Netzwerken

(00:00:00) >: Negative Kantengewichte

(00:03:26) >: Der Algorithmus von Bellman-Ford

(00:32:06) >: Der Algorithmus von Floyd-Warshall

(00:38:26) >: Flüsse in Netzwerken

(01:19:41) >: Das Max-Flow-Min-Cut Theorem

Date: 29.06.2016

Lecturer: Prof. Dr. Martin Hofmann

16. Der Dijkstra-Algorithmus

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

(00:25:01) >: Der Algorithmus von Dijkstra

(00:46:03) >: Korrektheit des Dijkstra Algorithmus

(01:06:18) >: Negative Kantengewichte

(01:16:46) >: Korrektheit und Laufzeit des Dijkstra-Algorithmus

(01:20:10) >: Der Algorithmus von Bellman-Ford

Date: 28.06.2016

Lecturer: Prof. Dr. Martin Hofmann

Downloads: algodat_k05.pdf (pdf) 1.1 MB

15. Minimale Spannbäume, Algorithmen von Kruskal und Prim

(00:00:00) >: Topologische Sortierung

(00:14:33) >: Graph mit SCC

(00:30:25) >: Korrektheitsbeweis

(00:38:12) >: Grundalgorithmus

(00:54:50) >: Algorithmus von Prim

(01:02:05) >: Korrektheit & Laufzeit des Algorithmus von Prim

(01:06:34) >: Algorithmus von Kruskal

(01:16:17) >: Kürzeste Wege

(01:20:18) >: Negative Zyklen und Algorithmen

(01:27:04) >: Relaxierung

Date: 22.06.2016

Lecturer: Stephan Barth

Algorithmen auf Graphen

(00:00:00) >: Allgemeine Entwurfs- und Optimierungsmethoden

(00:17:47) >: Algorithmen auf Graphen - Allgemeines

(00:56:24) >: Tiefensuche

Date: 21.06.2016

Lecturer: Prof. Dr. Martin Hofmann

13. Amortisierte Komplexität von Union-Find

(00:00:00) >: Amortisierte Analyse von Union-Find

(00:36:06) >: Bestmögliche Schranke

(00:38:02) >: Backtracking

(00:40:22) >: Damenproblem

(01:01:23) >: Iterative Deepening

(01:09:11) >: Branch and bound

Date: 16.06.2016

Lecturer: Prof. Dr. Martin Hofmann

12 Amortisierungs-Analyse

(00:00:00) >: Amortisierungs-Analyse Definition

(00:08:07) >: Einführendes Beispiel Binärzähler

(00:28:52) >: Queue als zwei Stacks

(00:50:17) >: Eine Datenstruktur für Disjunkte Mengen

(00:55:26) >: Union Find

(01:04:59) >: Optimierung Union by Rank

(01:15:14) >: Weitere Laufzeitverbesserung durch Pfadkompression

(01:22:47) >: Amortisierte Analyse von Union-Find (Fortsetzung nächste Sitzung)

Date: 14.06.2016

11. Dynamische Programmierung, Längste gemeinsame Teilfolge

Date: 08.06.2016

Lecturer: Prof. Dr. Martin Hofmann

Teil 4: Allgemeine Entwurfs- und Optimierungsmethoden

(00:00:00) >: Nachtrag zu Hashtabellen

(00:03:47) >: Greedy Algorithmen

(00:05:34) >: Beispiel - Auswahlproblem

(00:21:39) >: Korrektheitsbeweis

(00:49:42) >: Huffman Codes

(01:14:49) >: Korrektheit des Huffman-Algorithmus

Date: 07.06.2016

Lecturer: Prof. Dr. Martin Hofmann

Downloads: algodatk04_vo.pdf (pdf) 0.9 MB

9. Hashtabellen: offene Adressierung, Lineares- und quadratisches Sondieren

(00:00:00) >: Wiederholung

(00:18:58) >: Mittlere Suchdauer bei Linearem Sondieren

(00:21:00) >: Bloom-Filter

(00:39:56) >: Cuckoo-Hashing

(00:45:36) >: Zusammenfassung

(00:48:27) >: Allgemeine Entwurfs- und Optimierungsmethoden

Date: 02.06.2016

Lecturer: Prof. Dr. Martin Hofmann

Hashtabellen

(00:00:00) >: Hashfunktionen

(00:26:41) >: Offene Adressierung

(00:42:38) >: Hashfunktionen für offene Adressierung (Lineares und Quadratisches Sondieren)

(00:59:54) >: Analyse der offenen Adressierung

Date: 31.05.2016

Lecturer: Prof. Dr. Martin Hofmann

Rot-Schwarz-Bäume als spezielle B-Bäume

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

(00:49:04) >: Dynamische Mengen als Hashtabelle

Date: 18.05.2016

Lecturer: Prof. Dr. Martin Hofmann

3. Datenstrukturen - Dynamische Mengen

(00:00:00) >: Lineare Laufzeit im schlechtesten Fall (Randomized Select)

(00:11:10) >: Teil 3 - Datenstrukturen

(00:11:20) >: Dynamische Mengen

(00:15:43) >: Realisierung durch Bäume - a) Binäre Suchbäume

(00:32:19) >: b) AVL-Bäume

(00:53:40) >: c) B-Bäume

Date: 11.05.2016

Lecturer: Prof. Dr. Martin Hofmann

Vergleichskomplexität, Max/Min, Selektion

(00:00:00) >: Abschätzung einer Summe durch ein Integral

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

(00:28:13) >: Bestimmung des Maximums

(01:10:20) >: Die Selektionsaufgabe

(01:12:22) >: Anwendung des Medians

Date: 10.05.2016

Lecturer: Prof. Dr. Martin Hofmann

Downloads: algodat_k02.pdf (pdf) 0.5 MB

4. Prioritätsschlange, Quicksort

(00:00:00) >: Widerholung

(00:01:35) >: Prozedur Build-Heap: Laufzeitanalyse

(00:11:59) >: Konvergenz und Wert der Summe

(00:14:56) >: Prozedur Heap-Sort

(00:20:34) >: Prioritätsschlangen

(00:28:18) >: Quicksort

(00:33:27) >: Prozedur Partition

(00:55:51) >: Randomisiertes Quicksort

Date: 20.04.2016

Lecturer: Prof. Dr. Martin Hofmann

3. Master-Methode, Heapsort

(00:00:00) >: O-Notation

(00:06:12) >: Asymptotik und Induktion

(00:16:28) >: Lösen von Rekurrenzen bei Divide-and-Conquer

(00:21:04) >: Hauptsatz der Master-Methode

(00:42:50) >: Matritzenmultiplikation

(00:48:44) >: Matrizenmultiplikation mit Divide-and-Conquer

(00:50:42) >: Strassens erstaunlicher Algorithmus

(00:55:29) >: Suchen und Sortieren

(00:59:03) >: Heapsort

(01:01:40) >: Heaps

(01:09:42) >: Heapify

Date: 19.04.2016

Lecturer: Prof. Dr. Martin Hofmann

2. Sortieren durch Mischen, O-Notation

(00:00:00) >: Größenordnungen

(00:02:42) >: Teile und herrsche

(00:08:52) >: Beispiel

(00:11:05) >: Prozedur Merge

(00:21:35) >: Analyse von Merge-Sort

(00:33:36) >: Asymptotik: Definition von O

(00:38:06) >: Beispiele

(01:01:20) >: Asymptotik: Teta, Omega

(01:06:11) >: Kleines o und omega

Date: 13.04.2016

Lecturer: Prof. Dr. Martin Hofmann

1. Sortieren durch Einfügen

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

(00:19:21) >: Inhalt der Vorlesung

(00:40:06) >: Sortieren

(00:42:29) >: Sortieren durch Einfügen

(00:53:55) >: Laufzeitanalyse

(01:21:20) >: Größenordnungen

Date: 12.04.2016

Lecturer: Prof. Dr. Martin Hofmann

RSS-Feed abonnieren: