Effiziente Algorithmen fr grundlegende Funktionen

Der erfolgreiche Einsatz von Rechnern bei der Lsung von Problemen in fast allen Lebensbereichen beruht u.a. auf der technologischen Entwicklung, die zu schnelle ren Rechnern mit grerem Speicher fhrte, auf der greren Benutzerfreundlich keit der Rechner und auf effizienteren Algorithmen zur Lsung der betrachteten Probleme. Dieses Buch befat sich mit dem Entwurf effizienter Algorithmen fr grundlegende Probleme, die hufig als Teilprobleme in komplexeren Problemen auftreten. Whrend auf der unteren Ebene der Hardware von Rechnern, also in Schaltkreisen, Schaltwerken und VLSI-Chips, schon immer mit einem hohen Grad an Parallelitt gearbeitet wurde, konnte auf hherer Ebene lange Zeit nur sequentiell gerechnet werden. Dies ndert sich nun durch die Entwicklung von Rechnern mit immer mehr Prozessoren. Das Buch legt daher einen Schwerpunkt auf Algorithmen, die gleich zeitig bezglich paralleler Rechenzeit und Hardwaregre (bei Hardwarelsungen) bzw. bezglich paralleler Rechenzeit, Zahl der benutzten Prozessoren und Spei cherplatz (bei Softwarelsungen) effizient sind. Es werden effiziente Algorithmen fr den Entwurf optimaler P LA's diskutiert. Danach werden die grundlegenden arithmetischen Funktionen Addition, Subtrak tion, Multiplikation und Division, die symmetrischen Funktionen, die auch als Zhlfunktionen bezeichnet werden knnen, und Speicherzugriffsfunktionen behan delt. In diesem Teil des Buches werden vor allem Hardwarelsungen prsentiert. Fr das Rechnen mit Matrizen, einfache Probleme auf Graphen, Sortierprobleme und Probleme der Elementaren Zahlentheorie werden effiziente Softwarelsungen vorgestellt. Das Buch enthlt auerdem allgemeine Methoden der automatischen Parallelisierung sequentieller Algorithmen,Reduktionskonzepte zum Vergleich der Komplexitt der behandelten Probleme und effiziente Simulationen zwischen den benutzten Rechenmodellen.