|
Algorithm Engineering beinhaltet das Design von Algorithmen, ihre theoretische Analyse
sowie ihre experimentelle Analyse am Rechner. Dabei liegt der Schwerpunkt auf
der praktischen Seite.
Die klassische Algorithmik beschränkte sich lange Zeit auf die Theorie.
Viele Publikationen beschreiben die Algorithmen und Datenstrukturen unter
"idealen Voraussetzungen", die jedoch in der Praxis häufig nicht gegeben sind. Auch
wurden zunehmend hochkomplexe Datenstrukturen verwendet, die allgemein als "praktisch nicht implementierbar"
galten. Mit der zunehmenden Anwendung der theoretischen Ergebnisse in der Praxis merkte man, dass eine große
Lücke zwischen Theorie und Praxis existiert. Das Gebiet des Algorithm Engineering soll dem entgegenwirken,
indem es Algorithmen für die Praxis entwirft und analysiert, evaluiert und darauf aufbauend verbessert.
Nach einer Einführung werden spezielle ausgewählte Themen behandelt.
An dem Beispiel "Dynamische Kürzeste Wege" wird ein typischer Algorithm Engineering
Kreislauf dargestellt. Einen wichtigen Themenaspekt bilden die Externspeicheralgorithmen inkl.
cache-effizienter Algorithmen, denn die realen Rechenmaschinen entfernen sich zunehmend vom idealisierten
Neumann-Modell. Hierzu betrachten wir einige grundlegende Datenstrukturen sowie einfache Algorithmen für
grundlegende Probleme wie z.B. Sortieren. Weitere Themen beinhalten Algorithmen für NP-schwierige kombinatorische
Optimierungsprobleme aus dem Netzwerk-Design, der Bioinformatik und dem Graphenlayout. Ein Kapitel widmet sich
auch dem Design von experimentellen Analysen von Algorithmen.
|
Home
ls11.cs.tu-dortmund.de>
