دانلود کتاب Randomness and Completeness in Computational Complexity (به فارسی: تصادفی بودن و کامل بودن در پیچیدگی محاسباتی) نوشته شده توسط «Dieter van Melkebeek (auth.)»
اطلاعات کتاب تصادفی بودن و کامل بودن در پیچیدگی محاسباتی
موضوع اصلی: ریاضیات محاسباتی
نوع: کتاب الکترونیکی
ناشر: Springer-Verlag Berlin Heidelberg
نویسنده: Dieter van Melkebeek (auth.)
زبان: English
فرمت کتاب: pdf (قابل تبدیل به سایر فرمت ها)
سال انتشار: 2000
تعداد صفحه: 198
حجم کتاب: 3 مگابایت
کد کتاب: 3540414924 , 9783540414926
نوبت چاپ: 1
توضیحات کتاب تصادفی بودن و کامل بودن در پیچیدگی محاسباتی
این کتاب حاوی نسخه اصلاح شده پایان نامه ای است که نویسنده در گروه علوم کامپیوتر دانشگاه شیکاگو نوشته است. این پایان نامه مطابق با الزامات مدرک دکترا در ژوئن 1999 به دانشکده علوم فیزیکی ارسال شد. در ماه می 2000 مفتخر به دریافت جایزه پایان نامه دکتری ACM در سال 1999 شد. خلاصه پیچیدگی محاسباتی مطالعه مشکل ذاتی کامپیوتر است. – مشکلات ملی و قدرت ابزارهایی که ممکن است برای حل آنها استفاده کنیم. هدف آن تشریح تعداد منابعی است که برای محاسبه راه حل به عنوان تابعی از اندازه مسئله نیاز داریم. منابع معمولی شامل زمان در معماری های متوالی و موازی و فضای حافظه است. همانطور که می‌خواهیم از جزئیات نمایش ورودی و ویژگی‌های مدل کامپیوتری انتزاع کنیم، در نهایت با کلاس‌هایی از مسائل مواجه می‌شویم که می‌توانیم در محدوده‌های منابع قوی خاصی مانند زمان چند جمله‌ای، زمان لگاریتمی موازی و فضای لگاریتمی حل کنیم. تحقیقات در تئوری پیچیدگی به تعیین روابط بین این طبقات { شامل و جدایی ها خلاصه می شود. در این پایان نامه به نقش تصادفی بودن و بررسی ویژگی های مختلف مسائل سخت برای به دست آوردن تفکیک ها می پردازیم. ما همچنین قدرت عدم قطعیت و تناوب و همچنین مسائل مکان در مقابل زمان را بررسی می کنیم. تصادفی بودن منبعی را فراهم می‌کند که به نظر می‌رسد در موقعیت‌های مختلف کمک می‌کند.
This book contains a revised version of the dissertation the author wrote at the Department of Computer Science of the University of Chicago. The thesis was submitted to the Faculty of Physical Sciences in conformity with the requirements for the PhD degree in June 1999. It was honored with the 1999 ACM Doctoral Dissertation Award in May 2000. Summary Computational complexity is the study of the inherent di culty of compu- tional problems and the power of the tools we may use to solve them. It aims to describe how many resources we need to compute the solution as a function of the problem size. Typical resources include time on sequential and parallel architectures and memory space. As we want to abstract away from details of input representation and speci cs of the computer model, we end up with classes of problems that we can solve within certain robust resource bounds such as polynomial time, parallel logarithmic time, and logarithmic space. Research in complexity theory boils down to determining the relationships between these classes { inclusions and separations. In this dissertation, we focus on the role of randomness and look at various properties of hard problems in order to obtain separations. We also investigate the power of nondeterminism and alternation, as well as space versus time issues. Randomness provides a resource that seems to help in various situations.
دانلود کتاب «تصادفی بودن و کامل بودن در پیچیدگی محاسباتی»
