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 symmetrische Funktionen.- 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.