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: (Zugriff: vorname.nachname Matrikelnummer)

Organizational Issues
Algorithm Engineering
C++
Planar Point Location
Literate Programming
Algorithm Design Basics
Algorithm Analysis Basics
Generic Programming
Experiment Design
Point in Polygon First Results
Precision and Robustness in Geometric Computations
Exact Geometric Predicates
More on C++ Templates
Point in Polygon Second Results
Experimentation
Point in Polygon Further Results
CGAL
Partial Analysis of a Point in Polygon Algorithm
Arrangements in CGAL
Optimal Point Location Data Structures
Reporting Data from Experiments
Some Software Engineering
Certifying Algorithms
Software Libraries

Voraussetzungen:
Grundkenntnisse in Algorithmik, Programmiersprache C++.

Erwerb der Leistungspunkte:
Erfolgreiche Teilnahme am Projekt.

Testdaten fürs Projekt:
Polygoneckpunkt- und Punktanfragedateien liegen dank Hinrich nun als 7-zip Datei vor: polygondata+querypoints.7z

Testdaten fürs Debuggen von Point-in-Polygon Algorithmen:
(Format beachten!)

Datensatz	Polygoneckpunkte	Anfragepunkte	Korrekte Resultate
real world	polygon.txt	querypoints.txt	locations.txt
random	polygon.txt	querypoints.txt	locations.txt
random orthogonal	polygon.txt	querypoints.txt	locations.txt

Prüfung:
mündlich

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