3 Review(s)

Der erfolgreiche Einsatz von Rechnern bei der Loesung von Problemen in fast allen Lebensbereichen beruht u.a. auf der technologischen Entwicklung, die zu schnelle- ren Rechnern mit groesserem Speicher fuehrte, auf der groesseren Benutzerfreundlich- keit der Rechner und auf effizienteren Algorithmen zur Loesung der betrachteten Probleme. Dieses Buch befasst sich mit dem Entwurf effizienter Algorithmen fuer grundlegende Probleme, die haeufig als Teilprobleme in komplexeren Problemen auftreten. Waehrend auf der unteren Ebene der Hardware von Rechnern, also in Schaltkreisen, Schaltwerken und VLSI-Chips, schon immer mit einem hohen Grad an Parallelitaet gearbeitet wurde, konnte auf hoeherer Ebene lange Zeit nur sequentiell gerechnet werden. Dies aendert sich nun durch die Entwicklung von Rechnern mit immer mehr Prozessoren. Das Buch legt daher einen Schwerpunkt auf Algorithmen, die gleich- zeitig bezueglich paralleler Rechenzeit und Hardwaregroesse (bei Hardwareloesungen) bzw. bezueglich paralleler Rechenzeit, Zahl der benutzten Prozessoren und Spei- cherplatz (bei Softwareloesungen) effizient sind. Es werden effiziente Algorithmen fuer 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 Zaehlfunktionen bezeichnet werden koennen, und Speicherzugriffsfunktionen behan- delt. In diesem Teil des Buches werden vor allem Hardwareloesungen praesentiert. Fuer das Rechnen mit Matrizen, einfache Probleme auf Graphen, Sortierprobleme und Probleme der Elementaren Zahlentheorie werden effiziente Softwareloesungen vorgestellt. Das Buch enthaelt ausserdem allgemeine Methoden der automatischen Parallelisierung sequentieller Algorithmen,Reduktionskonzepte zum Vergleich der Komplexitaet der behandelten Probleme und effiziente Simulationen zwischen den benutzten Rechenmodellen.