Algorithm Engineering Dozent: Stefan Schirra Stundenplan

Inhalt:
Ziel des Algorithm Engineering ist die Überbrückung 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.

Vorlesungsfolien:
Algorithm Engineering
C++
Generic Programming
Project Proposal: Adaptive Spatial Sorting
Algorithmics
Literate Programming
Algorithm Analysis Basics
Don't Guess, Measure!
Adaptive Sorting Analysis
Adaptive Sorting Algorithms
Adaptive Sorting Algorithms
Adaptive Sorting Project
Hybrid Sorting
Experiment Design and Set-Up
Experimental Studies on Sorting Algorithms
Code Tuning
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
Modeling
CGAL
Scatter Plots
Challenges in Algorithm Engineering

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.