02 |

0:00:00 Start

0:00:16 Rückblick Vorlesung 24.04

0:03:42 Schulalgorithmus

0:05:55 Beispiel

0:07:05 Analyse

0:12:35 Exkurs: O-Kalkül

0:26:00 Ein rekursier Algorithmus: Hintergrund

0:33:22 Analyse

0:39:48 Exkurs: Algorithmen-Entwurfsmuster

0:43:01 Karatsuba-Ofman-Multiplikation (1962)

0:50:32 Gibt es noch besser?

0:55:41 Pseudocode

0:58:32 Korrektheit / Design by contract

1:06:16 Schleifeninvarianten

1:08:51 Beispiel

- - - - - - -

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