جزوه و کتاب نظریه ی محاسبات پیام نور

با توجه به کمبود منبع فارسی در خصوص درس نظریه مجاسبات و جایگزین شدن منبع این درس با دروس با محتوای متفاوت و اسم مشابه مانند محاسبات عددی جزوه حاضر با تلاش گروهی از دانشجویان پیام نور دماوند و استاد عسکرزاده به زیبایی تمام گردآوردی شده است.

در کتاب نظریه ی محاسبات به سه موصوع اساسی می پردازیم. موضوع اول که در دروس قبل نیز مطرح گردیده اتاماتا است، موضوع دوم پاسخ به این سوال است که آیا می توان برای حل همه مسائل الگوریتمی یافت؟ این مبحث با عنوان محاسبه پذیری در کتب نظریه محاسبات مطرح می گردد و مشخص خواهد شد که برای حل بسیاری از مسائل به نظر ساده ی اطراف ما هیچ الگوریتمی وجود ندارد. موضوع سوم نظریه پیچیدگی محاسبات است که در پاسخ به اینکه آیا منابع حافظه و پردازشی لازم برای حل یم مسئله وجود دارد یا خیر.

جزوه نظریه ی محاسبات از ۷ فصل تشکیل شده است. در ابتدای هر فصل مقدمه ای اختصاصی آورده شده است که خواننده دلایل مطالعه فصل را بهتر درک کند و اگر این کتاب مرحع درسی خارج از مقطع کارشناسی پیام نور بود با توجه به این مفدمه می توان فصولی از کتاب را حذف نمود. برای دانشچویان مهندسی کامپیوتر و علوم کاکپیوتر که دروسی مانند نظریه زبان ها و ماشین ها و اتاماتا را گذرانده اند فصل اول شامل الفباها، رشته ها، زبان ها . گرامرها بیشتر جنبه یادآوری دارند. موضوع فصل دوم به موضوع برنامه های با حافظه متناهی و مبدل های آن می پردازد این فصل هم برای دانشجویان مهندسی کامپیوتر نقش یادآوری دارد در فصل سوم به برنامه های بازگشتی و ….

فهرست مطالب :

فصل اول: نگاه کلی به نظریه محاسبات

• الفباها، رشته ها و نمایش ها
• زبان های صوری و گرامرها
• برنامه ها
• مسائل
• تقلیل پذیری در میان مسائل

فصل دوم: برنامه های با حافظه متناهی

• انگیزه
• مبدل های حالت متناهی
• گرامرهای نوع ۳ و گرامرهای منظم
• محدودیت برنامه های حافظه متناهی

فصل سوم: برنامه های بازگشتی با حافظه متناهی

• بازگشت
• مبدل های پشته ای

فصل چهارم: ماشین تورینگ

• مبدل های تورینگ
• برنامه ها و مبدل های تورینگ
• غیر قطعیت در مقابل قطعیت
• مبدل های تورینگ عمومی
• تصمیم ناپذیری
• ماشین های تورینگ و زیان نوع O
• مسئله تناظر پست

فصل پنجم: محاسبات با منابع محدود

• زمان و مکان
• سلسله مراتب زمان
• زمان چند جمله ای غیر قطعی
• مسائل NP کامل دیگر
• مکان چند جمله ای
• مسائل NP کامل

فصل ششم: محاسبات احتمالی

• برنامه های احتمالاتی مستقل از خطا
• برنامه های احتمالاتی که ممکن است خطاکنند
• مبدل تورینگ احتمالاتی
• زمان چند جمله ای احتمالی

فصل هفتم: مجاسبات موازی

• برنامه های موازی
• ماشین های دستیابی تصادفی موازی
• مدارها
• خانواده مدارهای یکنواخت
• خانواده مدارهای یکنواخت و محاسبات ترتیبی
• خانواده از مدارهای یکنواخت و PRAM ها