
09: Algorithmen I, Vorlesung, SS 2019, 27.05.2019
Autor
Beteiligtes Institut
Institut für Theoretische Informatik (ITI)
Genre
Beschreibung
09 |
0:00:00 Starten
0:00:24 Rückblick
0:06:17 Kollisionen
0:11:06 Analyse für zufällige Hash-Funktionen
0:21:54 Universelles Hashing
0:34:35 Beweis Theorem
0:42:08 Hashing mit linearer Suche(""linear probing"")
0:45:08 Der einfache Teil
0:51:03 Remove
1:01:36 Verketten vs. Lineare Suche
1:06:46 Kryptographische Hashfunktionen
1:10:29 Sotieren und Co
1:13:20 Lochkartensortierer
1:19:10 Einfache Sortieralgorithmen
1:21:52 Sentinels am Beispiel Sotieren durch Einfügen
1:24:47 Analyse
- - - - - - -
Titel der Serie:
Algorithmen I, Vorlesung, SS 2019
Beschreibung der Serie:
Das Modul beinhaltet die 'Basic Toolbox der Algorithmik'. Im Einzelnen werden folgende Themen bearbeitet:
- Ergebnisüberprüfung (Checkers) und Zertifizierung
- Asymptotische Algorithmenanalyse: worst case, average case, probabilistisch, amortisiert
- Grundbegriffe des Algorithm Engineering
- Effektive Umsetzung verketteter Listen
- Unbeschränkte Arrays, Stapel, und Warteschlangen
- Hashtabellen: mit Verkettung, linear probing, universelles Hashing
- Sortieren: effiziente Algorithmen (mergesort, quicksort), untere Schranken, radix sort
- Selektion: quickselect
- Prioritätslisten: binäre Heaps, addrssierbare Prioritätslisten
- Sortierte Folgen/Suchbäume: Wie unterstützt man alle wichtigen Operationen in logarithmischer Zeit
- Graphen (Repräsentation, Traversierung: Breitensuche, Tiefensuche, Anwendungen (topologisches Sortieren,...), Kürzeste Wege: Dijkstra's Algorithmus, Bellman-Ford Algorithmus, Minimale Spannbäume: Kruskals Algorithmus, Jarnik-Prim Algorithmus)
- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
Literaturhinweise:
Algorithms and Data Structures - The Basic Toolbox
K. Mehlhorn und P. Sanders
Springer 2008
Weiterführende Literatur
Algorithmen - Eine Einführung
T. H. Cormen, C. E. Leiserson, R. L. Rivest, und C. Stein
Oldenbourg, 2007
Algorithmen und Datenstrukturen
T. Ottmann und P. Widmayer
Spektrum Akademischer Verlag, 2002
Algorithmen in Java. Teil 1-4: Grundlagen, Datenstrukturen, Sortieren, Suchen
R. Sedgewick
Pearson Studium 2003
Algorithm Design
J. Kleinberg and É. Tardos
Addison Wesley, 2005
Vöcking et al.
Taschenbuch der Algorithmen
Springer, 2008
Laufzeit (hh:mm:ss)
01:27:03
Serie
Algorithmen I, Vorlesung, SS 2019
Publiziert am
06.06.2019
Fachgebiet
Lizenz
Auflösung | 1280 x 720 Pixel |
Seitenverhältnis | 16:9 |
Audiobitrate | 128000 bps |
Audio Kanäle | 2 |
Audio Codec | aac |
Audio Abtastrate | 48000 Hz |
Gesamtbitrate | 933998 kbps |
Farbraum | yuv420p |
Container | mov,mp4,m4a,3gp,3g2,mj2 |
Medientyp | video/mp4 |
Dauer | 5223 s |
Dateiname | DIVA-2019-485_hd.mp4 |
Dateigröße | 609.767.916 byte |
Bildwiederholfrequenz | 25 |
Videobitrate | 799901 kbps |
Video Codec | h264 |
Embed-Code