Skip to main content
HOME
www.lmu.de
Fakultät 11
UnterrichtsMitschau
Lehrfilme
UnterrichtOnline.org
What is VideoOnline?
Watch our introduction!
Aktuelle Vorlesungen
Alle Vorlesungen
Faculties
Fakultätsübergreifende Vorlesungen
Katholisch-Theologische Fakultät (Fakultät 1)
Evangelisch-Theologische Fakultät (Fakultät 2)
Juristische Fakultät (Fakultät 3)
Fakultät für Betriebswirtschaft (Fakultät 4)
Volkswirtschaftliche Fakultät (Fakultät 5)
Medizinische Fakultät (Fakultät 7)
Tierärztliche Fakultät (Fakultät 8)
Fakultät für Geschichts- und Kunstwissenschaften (Fakultät 9)
Fakultät für Philosophie, Wissenschaftstheorie und Religionswissenschaft (Fakultät 10)
Fakultät für Psychologie und Pädagogik (Fakultät 11)
Fakultät für Kulturwissenschaften (Fakultät 12)
Fakultät für Sprach- und Literaturwissenschaften (Fakultät 13)
Sozialwissenschaftliche Fakultät (Fakultät 15)
Fakultät für Mathematik, Informatik und Statistik (Fakultät 16)
Fakultät für Physik (Fakultät 17)
Fakultät für Chemie und Pharmazie (Fakultät 18)
Fakultät für Biologie (Fakultät 19)
Fakultät für Geowissenschaften (Fakultät 20)
Seniorenstudium
Tutorials
FAQs
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
Recording from:
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"
Recording from:
06.07.2016
Lecturer:
Prof. Dr. Martin Hofmann
Flüsse in Netzwerken
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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)
Recording from:
14.06.2016
11. Dynamische Programmierung, Längste gemeinsame Teilfolge
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
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
Recording from:
12.04.2016
Lecturer:
Prof. Dr. Martin Hofmann
RSS-Feed abonnieren: