CEB - - Limits to Parallel Computation-P Completeness Theory-Ray Greenlaw, Jim Hoover, Larry Ruzzo-1995

سایت CEB:ترجمه تخصصی رشته کامپیوتر - معرفی و دانلود کتب انگلیسی رشته کامپیوتر

امتیاز کاربران

ستاره غیر فعالستاره غیر فعالستاره غیر فعالستاره غیر فعالستاره غیر فعال

انتشارات: Oxford University Press

 اثر: Ray Greenlaw, Jim Hoover, Larry Ruzzo

تعداد صفحه: 327

حجم: 1.14MB

جلد کتاب

توضیحات کتاب (خلاصه پیشگفتار):

This book is an introduction to the rapidly growing theory of P-completeness — the branch of complexity theory that focuses on identifying the “hardest” problems in the class P of problems solvable in polynomial time. P-complete problems are of interest because they all appear to lack highly parallel solutions. That is, algorithm designers have failed to find NC algorithms, feasible highly parallel solutions that take time polynomial in the logarithm of the problem size while using only a polynomial number of processors, for them. Consequently, the promise of parallel computation, namely that applying more processors to a problem can greatly speed its solution, appears to be broken by the entire class of P-complete problems. This state of affairs is succinctly expressed as the following question: Does P equal NC?

The first part of the book is a thorough introduction to the theory of P-completeness. We begin with an informal introduction. Then we discuss the major parallel models of computation, describe the classes NC and P, and present the notions of reducibility and completeness. We subsequently introduce some fundamental P-complete problems, followed by evidence suggesting why NC does not equal P. Next, we discuss in detail the primary P-complete problem, that of evaluating a Boolean circuit. Following this we examine several sequential paradigms and their parallel versions. We describe a model for classifying algorithms as inherently sequential. We finish Part I with some general conclusions about practical parallel computation.

The second part of the book provides a comprehensive catalog of P-complete problems, including several unpublished and new P-completeness results. For each problem we try to provide the essential idea underlying its P-complete reduction, and as much information and additional references about related problems as possible. In addition to the P-complete problems catalog, we provide a list of open problems, a list of problems in the class CC, and a list of problems in the class RNC.

The book has been designed so that it will be suitable as a text for a one semester graduate course covering topics in parallel computation. The book would be ideal for use in a seminar course focusing on P-completeness theory. It can also be used as a supplementary text for a graduate level course in complexity theory. Several of the chapters in the book could be covered in a graduate level course or the book could be used as a reference for courses in the theory of computation. This work could also be used as a rich source of sample problems for a variety of different courses. For the motivated student or researcher interested in learning about P-completeness, the book can be used effectively for self study.

آیکن نشانگر نوع فایل در سایت CEBدانلود

برای دانلود کتاب، ثبت درخواست ترجمه، و دریافت رایگان خبرنامه‌های سایت نیاز به ثبت نام دارید.

آیا از خواندن متون ترجمه‌ای بی سر و ته خسته شده‌اید؟ و بدنبال راهی برای بهره‌گیری از یک متن اصیل برای یادگیری هستید؟
آیا وقت کافی برای فهم و یا ترجمه‌ی مطلب خود در اختیار ندارید؟
از خواندن متنی که کارتان گیر آن است کلافه شده‌اید؟
کار را به ما بسپارید، خیالتان راحت!

هم اکنون! سايت CEB را به چند نفر از دوستان خود هم معرفی کنيد؛ با اين کار علاوه بر حمايت از ما، به بالا رفتن کيفيت خدمات و پايين ماندن تعرفه‌ی دانلود هم کمک کرده‌ايد.

dear author and publishers!
If you do not agree that your books be freely available through this site to Iranians - Those who are not subject to the Copy Right law - please contact us through your official email address so that we can identify you as the author or publisher of that books and remove all your books that you don't like to be accessible through this site. Note that only downloadable material can be appeared on this website. Also note that this site is not the source of illegal publication of the books; We only gathered the books accessible via the Internet together and maked these books more accessible to Iranians.

Valid XHTML 1.0 Transitional