Algorithm Engineering

Wintersemester 2007/08

Stefan Schirra

Projektdateien:
project files (new version 1.2)

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.

Slides: (Access User Name: firstname.lastname Password:your matriculation number)
   1 Algorithm Engineering
   2 Project: Planar Point Location
   3 C++
   4 Literate Programming
   5 Algorithm Design Basics
   6 Algorithm Analysis Basics
   7 Point in Polygon Testing
   8 Experiment Design
   9 Precision and Robustness in Geometric Computations
10 Experimentation ExpLab
11 Generic Programming PiP
12 More on C++ Templates
13 Point in Polygon Robustness
14 CGAL
15 Arrangements in CGAL
16 Reporting Data from Experiments PiP
17 Optimal Point Location Data Structures PiP
18 Some Software Engineering
19 Certifying Algorithms
20 Software Libraries
21 Graph Algorithms Software Libraries PiP
22 Challenges in Algorithm Engineering

      Lectures on Algorithm Engineering

Beispielpolygone:
30 vertices 300 vertices

Beispielcode:
Point location in polygons via CGAL Arrangements

Voraussetzungen: Grundkenntnisse in Algorithmik, C++.

Projekt: Punktlokalisierung in planaren Unterteilungen
Im Projekt werden wir ein klassisches geometrisches Problem betrachten: Punktlokalisierung in planaren Unterteilungen der Ebene. Dieses Problem hat zahlreiche Anwendungen, insbesondere in Geographischen Informationssystemen. Für dieses Problem wurden einige asymptotisch sehr effiziente Datenstrukturen gefunden, die aber meist in der Praxis nicht zum Einsatz kommen. Ziel des Projekts wird es sein, für gegebene Szenarien effiziente Punktlokalisierungsmethoden für planaren Unterteilungen zu entwickeln, die als CGAL Arrangements gegeben sind. Dazu wird es nötig sein, einiges über die C++ Software Bibliothek CGAL, Arrangements und Punktlokalisierung zu lernen. Im Hinblick auf die Verlässlichkeit der Implementierungen ist die Vorlesung Robust Geometric Computing hilfreich.

Erwerb der Leistungspunkte: Erfolgreiche Teilnahme am Projekt.

Prüfung: mündlich

Links:

Webmaster -