Effiziente Algorithmen für grundlegende Funktionen

استفاده موفقیت‌آمیز از ماشین‌حساب‌ها در حل مسائل تقریباً در همه زمینه‌های زندگی، از جمله، مبتنی بر پیشرفت‌های فناوری است که منجر به رایانه‌های سریع‌تر با حافظه بزرگ‌تر، کاربرپسندی بیشتر ماشین‌حساب‌ها و الگوریتم‌های کارآمدتر برای حل شده است. مشکلات مورد بررسی این کتاب در مورد طراحی الگوریتم های کارآمد برای مسائل اساسی است که اغلب به عنوان مسائل فرعی در مسائل پیچیده تر ظاهر می شوند. در حالی که درجه بالایی از موازی بودن همیشه در سطح پایین تر سخت افزار رایانه ها، یعنی در مدارها، مکانیسم های سوئیچینگ و تراشه های VLSI استفاده شده است، برای مدت طولانی فقط امکان محاسبه متوالی در سطح بالاتر وجود داشت. این امر اکنون با توسعه رایانه هایی با پردازنده های بیشتر و بیشتر در حال تغییر است. بنابراین، این کتاب بر روی الگوریتم‌هایی تمرکز دارد که از نظر زمان محاسبات موازی و اندازه سخت‌افزار (در مورد راه‌حل‌های سخت‌افزاری) یا از نظر زمان محاسبات موازی، تعداد پردازنده‌های مورد استفاده و فضای ذخیره‌سازی (در مورد راه‌حل‌های نرم‌افزاری) کارآمد هستند. . الگوریتم‌های کارآمد برای طراحی PLA بهینه مورد بحث قرار می‌گیرند. سپس توابع حسابی پایه جمع، تفریق، ضرب و تقسیم، توابع متقارن که می توان آنها را توابع شمارش نیز نامید و توابع دسترسی به حافظه بررسی می شود. این بخش از کتاب عمدتاً راه حل های سخت افزاری را ارائه می دهد. راه حل های نرم افزاری کارآمد برای محاسبه با ماتریس ها، مسائل ساده روی نمودارها، مرتب سازی مسائل و مسائل در تئوری اعداد ابتدایی ارائه شده است. این کتاب همچنین شامل روش‌های کلی موازی‌سازی خودکار الگوریتم‌های متوالی، مفاهیم کاهش برای مقایسه پیچیدگی مسائل مطرح شده و شبیه‌سازی کارآمد بین مدل‌های محاسباتی مورد استفاده است.

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.