No label defined (Q4023845)

Algorithmen müssen, damit sie für praktische Probleme tauglich sind, nicht nur korrekt sein, sondern auch eine akzeptable Ausführungszeit besitzen. Als akzeptabel gilt ein schlimmstenfalls polynomiales asymptotisches Zeitverhalten. Nur mit solchen Algorithmen können noch für hohe Problemgrößen Lösungen in praktisch realisierbaren Zeiträumen gefunden werden. Deshalb stellt das Auffinden eines effizienten Algorithmus oft erst die praktische Lösung eines Problems dar, obwohl schon lange andere (weniger effiziente) Lösungsalgorithmen bekannt sind. Da die Befehlsausführungszeit nur als konstanter Faktor in die Betrachtung eingeht, bringt die Beschleunigung der Computer hier keine prinzipielle Änderung der Situation. Die Konstruktion effizienter Algorithmen hat also auch heute noch eine große Bedeutung. Der Autor diskutiert diese Problematik und untersucht Techniken des Algorithmenentwurfs. Eine große Zahl teilweise sehr bekannter Algorithmen wird systematisch hergeleitet und im Detail angegeben. Die behandelten Gebiete sind: Sortieren, Datenhaltung, Graphen, und algebraische Berechnungen. Das Buch eignet sich als methodisches Lehrbuch aber auch als Nachschlagewerk. Als Sprache der Algorithmenformulierung wird eine Pascal-ähnliche Notation verwendet.