Limits of Computation: From a Programming Perspective

ویرایش: 1 
نویسندگان: Bernhard Reus (auth.)  
سری: Undergraduate Topics in Computer Science 
ISBN (شابک) : 9783319278872, 9783319278896 
ناشر: Springer International Publishing 
سال نشر: 2016 
تعداد صفحات: 352 
زبان: English 
فرمت فایل : PDF (درصورت درخواست کاربر به PDF، EPUB یا AZW3 تبدیل می شود) 
حجم فایل: 8 مگابایت 

قیمت کتاب (تومان) : 55,000



این کتاب درسی اساسی ترین و گیج کننده ترین سؤالات را در مورد مبانی محاسبات مورد بحث قرار می دهد. در 23 فصل به اندازه سخنرانی، یک تور هیجان انگیز را از طریق مهم ترین نتایج در زمینه محاسبه پذیری و پیچیدگی زمانی، از جمله مسئله توقف، قضیه رایس، قضیه بازگشت کلین، پایان نامه چرچ-تورینگ، قضایای سلسله مراتبی، و کوک-لوین ارائه می کند. قضیه. هر فصل شامل مطالب تست شده در کلاس درس، از جمله مثال ها و تمرین ها است. پیوندهای بین فصل‌های مجاور، روایتی منسجم را ارائه می‌دهند.

نتایج بنیادی با استفاده از برنامه‌هایی که به زبان برنامه‌نویسی ضروری ساده و سطح بالا نوشته شده‌اند، به وضوح توضیح داده می‌شوند، که فقط به دانش ریاضی پایه نیاز دارد. در سراسر کتاب، تأثیر نتایج ارائه شده بر کل رشته علوم کامپیوتر مورد تاکید قرار گرفته است. نمونه ها از تجزیه و تحلیل برنامه تا شبکه، از برنامه نویسی پایگاه داده تا بازی ها و پازل های محبوب را شامل می شود. پاورقی های بیوگرافی متعددی درباره دانشمندان مشهوری که این موضوع را توسعه داده اند نیز گنجانده شده است. در عین حال قابل دسترس، مقدمه ای بر محاسبات و پیچیدگی برای دانشجویان علوم کامپیوتر قرن بیست و یکم.

This textbook discusses the most fundamental and puzzling questions about the foundations of computing. In 23 lecture-sized chapters it provides an exciting tour through the most important results in the field of computability and time complexity, including the Halting Problem, Rice's Theorem, Kleene's Recursion Theorem, the Church-Turing Thesis, Hierarchy Theorems, and Cook-Levin's Theorem. Each chapter contains classroom-tested material, including examples and exercises. Links between adjacent chapters provide a coherent narrative.

Fundamental results are explained lucidly by means of programs written in a simple, high-level imperative programming language, which only requires basic mathematical knowledge. Throughout the book, the impact of the presented results on the entire field of computer science is emphasised. Examples range from program analysis to networking, from database programming to popular games and puzzles. Numerous biographical footnotes about the famous scientists who developed the subject are also included.

"Limits of Computation" offers a thorough, yet accessible, introduction to computability and complexity for the computer science student of the 21st century.

Front Matter....Pages i-xviii
Limits? What Limits?....Pages 1-9
Front Matter....Pages 11-11
Problems and Effective Procedures....Pages 13-28
The WHILE-Language....Pages 29-45
Programs as Data Objects....Pages 47-54
An Undecidable (Non-computable) Problem....Pages 55-63
More Undecidable Problems....Pages 65-70
Self-referencing Programs....Pages 71-86
The Church-Turing Thesis....Pages 87-96
Front Matter....Pages 97-112
Measuring Time Usage....Pages 113-121
Complexity Classes....Pages 123-148
Hierarchy Theorems....Pages 149-149
Famous Problems in P....Pages 151-160
The One-Million-Dollar Question....Pages 161-171
How Hard Is a Problem?....Pages 173-181
Complete Problems....Pages 183-194
Front Matter....Pages 195-216
How to Solve NP-Complete Problems....Pages 217-226
Molecular Computing....Pages 227-239
Quantum Computing....Pages 241-249
Back Matter....Pages 251-274
....Pages 149-149