Algorithm Engineering

Dozent: Stefan Schirra     Stundenplan

Inhalt:
Ziel des Algorithm Engineering ist die Verringerung der Kluft zwischen den in der Algorithmik entwickelten Methoden und den in der Praxis eingesetzten. Diese Kluft hat sich in manchen Gebieten ergeben, weil die Theoretische Algorithmik in erster Linie an asymptotisch effizienten Algorithmen interessiert ist und oft zu stark vereinfachende Annahmen trifft. Die vereinfachenden Annahmen betreffen dabei sowohl die Modellierung der Probleme als auch die dem Algorithmenentwurf zugrundeliegenden Maschinenmodelle. In der Vorlesung werden Methoden des Algorithm Engineerings behandelt. Die Methodik des Algorithm Engineering ist im wesentlichen durch einen Zyklus bestehend aus Algorithmenentwurf, -analyse, Implementierung und experimenteller Auswertung charakterisiert. In einem die Vorlesung begleitenden Beispielprojekt soll die Methodik des Algorithm Engineering in den begleitenden Übungen mit Leben erfüllt werden.
Die folgende Abbildung wurde mir freundlicherweise von Peter Sanders zur Verfügung gestellt

Vorlesungsfolien:
Algorithm Engineering
C++
Algorithmics
Algorithm Analysis Basics
Literate Programming
Don't Guess, Measure!
Generic Programming
Project: Spatial Sorting
Adaptive Sorting Analysis
Adaptive Sorting
Adaptive Sorting
Sorting
Sorting
Experiment Design and Set-Up
Case Studies on Sorting Algorithms
More on C++ Templates
Reporting Data from Experiments
Some Software Engineering
Certifying Algorithms
Precision and Robustness in Geometric Computations
Case Study: Reliability of Point-in-Polygon Strategies
Exact Geometric Predicates
Software Libraries
Graph Algorithms Libraries BOOST and LEDA
Adaptive Sorting: Some Experimental Results
CGAL
Code Tuning
Challenges in Algorithm Engineering

Übungsblätter:
Übungsblatt 1
Übungsblatt 2

Voraussetzungen:
Grundkenntnisse in Algorithmik, Programmiersprache C++.

Erwerb der Leistungspunkte:
Erfolgreiche Teilnahme am Projekt. Bearbeiten der Übungsaufgaben.

Prüfung:
mündlich

Note:
The course will be taught in English if requested.