KIT-Bibliothek
Audio-/Videodatei publizieren

02: Algorithmen 1, Vorlesung, SS 2017, 26.04.2017, 02

Autor

Tamim Asfour

Herausgeber

KIT | Webcast

Beteiligtes Institut

Institut für Theoretische Informatik (ITI)

Genre

Vorlesung

Beschreibung

0:00:00 Starten
0:00:07 Erinnerung VL 24.04.2017
0:01:55 Karatsuba-Ofman Multiplikation
0:04:33 Skalierung
0:06:59 Blick über den Tellerrand
0:09:45 Algorithmenanalyse
0:13:07 Zweite Vereinfachung: Asymptotik
0:19:44 O-Kalkül Rechenregeln
0:23:29 Maschinenmodell: RAM
0:31:59 ""Kleine"" ganze Zahlen?
0:35:00 Algorithmenanalyse im RAM-Modell
0:38:15 Mehr Maschinenmodell
0:40:56 Pseudocode
0:41:56 Design by Contract / Schleifeninvarianten
0:56:16 Programmanalyse
1:00:30 Eine Rekurrenz für Teile und Herrsche
1:02:54 Master Theorem (Einfache Form)

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

Lehrinhalt:
Dieses Modul soll Studierenden grundlegende Algorithmen und Datenstrukturen vermitteln.

Die Vorlesung behandelt unter anderem:
- Grundbegriffe des Algorithm Engineering
- Asymptotische Algorithmenanalyse (worst case, average case, probabilistisch, amortisiert)
- Datenstrukturen z. B. Arrays, Stapel, Warteschlangen und Verkettete Listen
- Hashtabellen
- Sortieren: vergleichsbasierte Algorithmen (z.B. quicksort, insertionsort), untere Schranken, Linearzeitalgorithmen (z.B. radixsort)
- Prioritätslisten
- Sortierte Folgen,Suchbäume und Selektion
- Graphen (Repräsentation, Breiten-/Tiefensuche, Kürzeste Wege, Minimale Spannbäume)
- Generische Optimierungsalgorithmen (Greedy, Dynamische Programmierung, systematische Suche, Lokale Suche)
- Geometrische Algorithmen

Laufzeit (hh:mm:ss)

01:16:52

Serie

Algorithmen I, Vorlesung, SS 2017

Publiziert am

03.05.2017

Fachgebiet

Informatik

Lizenz

KITopen-Lizenz

Auflösung 1280 x 720 Pixel
Seitenverhältnis 16:9
Audiobitrate 109078 bps
Audio Kanäle 2
Audio Codec aac
Audio Abtastrate 48000 Hz
Gesamtbitrate 917167 bps
Farbraum yuv420p
Container mov,mp4,m4a,3gp,3g2,mj2
Medientyp video/mp4
Dauer 4612 s
Dateiname DIVA-2017-195_hd.mp4
Dateigröße 4.096 byte
Bildwiederholfrequenz 25
Videobitrate 801998 bps
Video Codec h264

Embed-Code