Effiziente Algorithmen für grundlegende Funktionen

Der erfolgreiche Einsatz von Rechnern bei der Lösung von Problemen in fast allen Lebensbereichen beruht u. a. auf der technologischen Entwicklung, die zu schnelle­ ren Rechnern mit größerem Speicher führte, auf der größeren Benutzerfreundlich­ keit der Rechner und auf effizienteren Algorithmen zur Lösung der betrachteten Probleme. Dieses Buch befaßt sich mit dem Entwurf effizienter Algorithmen für grundlegende Probleme, die häufig als Teilprobleme in komplexeren Problemen auftreten. Während auf der unteren Ebene der Hardware von Rechnern, also in Schaltkreisen, Schaltwerken und VLSI-Chips, schon immer mit einem hohen Grad an Parallelität gearbeitet wurde, konnte auf höherer 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 bezüglich paralleler Rechenzeit und Hardwaregröße (bei Hardwarelösungen) bzw. bezüglich paralleler Rechenzeit, Zahl der benutzten Prozessoren und Spei­ cherplatz (bei Softwarelösungen) effizient sind. Es werden effiziente Algorithmen für 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 Zählfunktionen bezeichnet werden können, und Speicherzugriffsfunktionen behan­ delt. In diesem Teil des Buches werden vor allem Hardwarelösungen präsentiert. Für das Rechnen mit Matrizen, einfache Probleme auf Graphen, Sortierprobleme und Probleme der Elementaren Zahlentheorie werden effiziente Softwarelösungen vorgestellt. Das Buch enthält außerdem allgemeine Methoden der automatischen Parallelisierung sequentieller Algorithmen, Reduktionskonzepte zum Vergleich der Komplexität der behandelten Probleme und effiziente Simulationen zwischen den benutzten Rechenmodellen.

1. Einleitung.- 1.1 Wann sind Algorithmen effizient?.- 1.2 Welches sind die grundlegenden Funktionen?.- 1.3 Welche Rechenmodelle werden benutzt?.- 1.4 Was mißt die Größenordnung der Rechenzeit?.- 1.5 Komplexitätsklassen.- 1.6 Beziehungen zwischen den Rechenmodellen.- Aufgaben.- 2. Die Minimierung Boolescher Funktionen.- 2.1 Rechenregeln und Normalformen.- 2.2 Primimplikanten, Minimalpolynome und PLA s.- 2.3 Der Quine/Mc Cluskey-Algorithmus zur Berechnung aller Primimplikanten.- 2.4 Weitere Algorithmen zur Berechnung aller Primimplikanten.- 2.5 Methoden zur Berechnung von Minimalpolynomen aus der Menge aller Primimplikanten.- 2.6 Karnaugh-Diagramme.- 2.7 Partiell definierte Boolesche Funktionen.- 2.8 Funktionen mit mehreren Outputs.- 2.9 Monotone und symmetrische Funktionen.- 2.10 Disjunkte Konjunktionen.- 2.11 Wie effizient sind Minimalpolynome?.- 2.12 Schaltkreise mit vier logischen Stufen.- Aufgaben.- 3. Addition, Subtraktion, Multiplikation und Division.- 3.1 Die Schulmethode für die Addition.- 3.2 Von Neumann Addierwerke.- 3.3 Carry-Look-Ahead Addierer.- 3.4 Conditional Sum Addierer.- 3.5 Optimale Präfixberechnung.- 3.6 Ein billiger und schneller Addierer.- 3.7 Subtraktion und Zweierkomplementdarstellung.- 3.8 Die Schulmethode für die Multiplikation.- 3.9 Eine Divide-and-Conquer Methode.- 3.10 Die Radix-4 Darstellung.- 3.11 Die Schnelle Fouriertransformation und Konvolutionen.- 3.12 Der Chinesische Restklassensatz.- 3.13 Die Multiplikationsmethode von Schönhage und Strassen.- 3.14 Die Boolesche Konvolution.- 3.15 Die Schulmethode für die Division.- 3.16 Die Newtonmethode.- 3.17 Die IBM-Methode.- 3.18 Ein schneller Divisionsschaltkreis.- Aufgaben.- 4. Symmetrische Funktionen.- 4.1 Definitionen und Beispiele.- 4.2 Effiziente Schaltkreise für symmetrischeFunktionen.- 4.3 Die Paritätsfunktion.- 4.4 Die symmetrischen Funktionen in AC0.- Aufgaben.- 5. Speicherzugriffsfunktionen.- Aufgaben.- 6. Das Rechnen mit Matrizen.- 6.1 Addition und Multiplikation.- 6.2 Das Gaußsche Eliminationsverfahren.- 6.3 Ein effizienter paralleler Algorithmus zur Determinantenberechnung.- Aufgaben.- 7. Einfache Grapheigenschaften.- 7.1 Zusammenhangskomponenten.- 7.2 Transitiver Abschluß, starker Zusammenhang und zweifacher Zusammenhang.- 7.3 Kürzeste Wege.- 7.4 Minimale Spannbäume.- 7.5 Planarität, Matchings und Flußprobleme.- Aufgaben.- 8. Sortieren.- 8.1 Schaltkreise für Sortierprobleme.- 8.2 INSERTION SORT.- 8.3 MERGE SORT.- 8.4 QUICK SORT.- 8.5 HEAP SORT.- 8.6 Ein linearer Algorithmus zur Medianberechnung.- 8.7 BUCKET SORT.- 8.8 Sortiernetzwerke.- 8.9 Sortieren mit parallelen Registermaschinen.- Aufgaben.- 9. Elementare Zahlentheorie.- 9.1 Kryptographische Systeme.- 9.2 Potenzen, multiplikative Inverse und größte gemeinsame Teiler.- 9.3 Das Jacobi-Symbol.- 9.4 Ein probabilistischer Primzahltest.- Aufgaben.- 10. Reduktionen und automatische Parallelisierung.- 10.1 Parallelisierung polynomieller Formeln.- 10.2 Speicherplatz und parallele Rechenzeit.- 10.3 Reduktionskonzepte.- 10.4 Reduktionen.- Aufgaben.- 11. Beziehungen zwischen den Rechenmodellen.- 11.1 Ein Vergleich der Schaltkreismodelle.- 11.2 Ein Vergleich der Parallelrechnermodelle.- 11.3 Simulationen von Schaltkreisen durch Parallelrechner.- 11.4 Eine Simulation von Parallelrechnern durch Schaltkreise.- Aufgaben.- Schriftenverzeichnis.