252-0002-00L  Datenstrukturen & Algorithmen

SemesterFrühjahrssemester 2014
DozierendeP. Widmayer
Periodizitätjährlich wiederkehrende Veranstaltung
LehrspracheDeutsch


KurzbeschreibungEs werden grundlegende Entwurfsmuster für Algorithmen (wie z.B. Induktion, divide-and-conquer, backtracking, dynamische Programmierung), klassische algorithmische Probleme (wie z.B. Suchen, Sortieren) und Datenstrukturen (wie z.B. Listen, Hashverfahren, Suchbäume) behandelt. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert.
LernzielVerständnis des Entwurfs und der Analyse grundlegender Algorithmen und Datenstrukturen.
InhaltEs werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert.
LiteraturTh. Ottmann, P.Widmayer: Algorithmen und Datenstrukturen, Spektrum-Verlag, 5. Auflage, Heidelberg, Berlin, Oxford, 2011
Voraussetzungen / BesonderesVoraussetzung:
252-0021-00L Einführung in die Programmierung