|
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. Anhand Kürzeste-Wege-Probleme wird der typische Algorithm Engineering Kreislauf dargestellt. Einen wichtigen Themenaspekt bilden die Externspeicheralgorithmen inkl. cache-effizienter Algorithmen, denn die realen Rechenmaschinen entfernen sich zunehmend vom idealisierten von 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>
