Effiziente Algorithmen Für Grundlegende Funktionen

ISBN-13: 9783519122760 / Niemiecki / Miękka / 1996 / 262 str.

Ingo Wegener

Opis

Der erfolgreiche Einsatz von Rechnern bei der Losung von Problemen in fast allen Lebensbereichen beruht u.a. auf der technologischen Entwicklung, die zu schnelle ren Rechnern mit grosserem Speicher fuhrte, auf der grosseren Benutzerfreundlich keit der Rechner und auf effizienteren Algorithmen zur Losung der betrachteten Probleme. Dieses Buch befasst sich mit dem Entwurf effizienter Algorithmen fur grundlegende Probleme, die haufig als Teilprobleme in komplexeren Problemen auftreten. Wahrend auf der unteren Ebene der Hardware von Rechnern, also in Schaltkreisen, Schaltwerken und VLSI-Chips, schon immer mit einem hohen Grad an Parallelitat gearbeitet wurde, konnte auf hoherer Ebene lange Zeit nur sequentiell gerechnet werden. Dies andert sich nun durch die Entwicklung von Rechnern mit immer mehr Prozessoren. Das Buch legt daher einen Schwerpunkt auf Algorithmen, die gleich zeitig bezuglich paralleler Rechenzeit und Hardwaregrosse (bei Hardwarelosungen) bzw. bezuglich paralleler Rechenzeit, Zahl der benutzten Prozessoren und Spei cherplatz (bei Softwarelosungen) effizient sind. Es werden effiziente Algorithmen fur 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 Zahlfunktionen bezeichnet werden konnen, und Speicherzugriffsfunktionen behan delt. In diesem Teil des Buches werden vor allem Hardwarelosungen prasentiert. Fur das Rechnen mit Matrizen, einfache Probleme auf Graphen, Sortierprobleme und Probleme der Elementaren Zahlentheorie werden effiziente Softwarelosungen vorgestellt. Das Buch enthalt ausserdem allgemeine Methoden der automatischen Parallelisierung sequentieller Algorithmen, Reduktionskonzepte zum Vergleich der Komplexitat der behandelten Probleme und effiziente Simulationen zwischen den benutzten Rechenmodellen."

Spis treści

Die Minimierung Boolscher Funktionen - Addition, Subtraktion, Multiplikation und Division - Symmetrische Funktionen - Speicherzugriffsfunktionen - Rechnen mit Matrizen - Einfache Grafeneigenschaften - Sortieren - Elementare Zahlentheorie - Reduktion und automatische Parallelisierung - Beziehung zwischen Rechenmodellen