scientific article; zbMATH DE number 108385

MaRDI QIDQ4023845zbMATH OpenFDO

Authors Christoph Meinel

Publication date 23 January 1993

zbMATH Keywords

complexity of algorithms efficiency

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

Cited in

(6)

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4023845)