نظریه محاسبات
Theory of Computation
| شماره درس: ۴۰۴۵۵ | تعداد واحد: ۳ |
| مقطع: کارشناسی | نوع درس: نظری |
| پیش‌نیاز: ساختمان داده‌ها و الگوریتم‌ها | هم‌نیاز: – |
اهداف درس
هدف از ارائه‌ی این درس آشنایی دانشجویان با مبانی نظریه‌ی محاسبات و مفاهیم اصلی مدل‌های محاسبه‌پذیری، مسائل حل‌شدنی، منطق ریاضی و مقدمه‌ای بر نظریه آتوماتا بر ورودی‌های نامتناهی رشته‌ای یا درختی است. این درس در واقع تأمین‌کننده پایه‌ی نظری لازم برای دانشجویانی است که در دوره‌های تحصیلات تکمیلی در گرایش‌های نظریه‌ی محاسبات و الگوریتم یا روش‌های صوری در مهندسی نرم‌افزار و درستی‌یابی سیستم‌ها تحصیل می‌کنند، و همچنین منطق ریاضی لازم برای هوش مصنوعی را بنا می‌نهد.
ریز مواد
درس شامل سه بخش اصلی است:
- نظریه‌ی محاسبه‌پذیری و مقدمه‌ای بر پیچیدگی محاسبات
- مدل تورینگی محاسبه، تز تورینگ-چرچ، توابع و زبانهای تصمیم‌پذیر (بازگشتی)، توابع و زبانهای تشخیص‌پذیر (بازگشتیانه شمارش‌پذیر)، توابع محاسبه نا‌پذیر، مساله‌ی توقف، ماشین تورینگ جهانی، ماشین تورینگ چند نواری و ماشین تورینگ غیرقطعی و قضایای معادل بودن آن‌ها (۳ جلسه)
- روش‌های اثبات تصمیم‌ناپذیری و تشخیص‌ناپذیری زبان‌ها شامل روش کاهش به مساله توقف و روش کاهش تابعی (۲ جلسه)
- مقدمه‌ای بر سایر مدل‌های محاسبه (۲ جلسه)
- مدل ماشین دسترسی تصادفی (RAM) فون‌نیومان
- نظریه‌ی توابع بازگشتی کلینی
- حساب لامبدا چرچ
- سیستم‌های پست
- قضیه‌ی بازگشتی و خود-ارجاعی (۱ جلسه)
- تعریف محاسباتی اطلاعات و پیچیدگی رشته‌ای (۲ جلسه)
- مقدمه‌ای بر نظریه‌ی پیچیدگی و مروری بر کلاس‌های پیچیدگی زمان و حافظه و مسایل دشوار (۳ جلسه)
- منطق ریاضی از منظر نظریه‌ی محاسبات
- منطق گزاره‌ها، نحو و معناشناسی آن، سیستم استنتاجی اصل موضوعی و قضایای صحت و تمامیت آن، قضایای تصمیم‌پذیری منطق گزاره‌ها (۲ جلسه)
- منطق مرتبه اول، نحو و معناشناسی آن، قضایای فشردگی و لوون‌هایم-اسکولم (۲ جلسه)
- سیستم استنتاجی اصل موضوعی منطق مرتبه‌ی اول و قضیه‌ی صحت آن (۱ جلسه)
- قضیه‌ی گدل در تمامیت سیستم استنتاجی منطق مرتبه‌ی اول (۱ جلسه)
- قضیه چرچ در تصمیم‌ناپذیری منطق مرتبه‌ی اول (۲ جلسه)
- سیستم‌های اصل موضوعی نظریه اعداد و قضیه ناتمامیت گدل (شکل اول و دوم) (۲ جلسه)
- مقدمه‌ای بر نظریه آتوماتا بر ورودی‌های نامتناهی
- آتوماتای بوخی و رابین بر رشته‌های نامتناهی (۲ جلسه)
- قضایای مربوط به مکمل‌کردن و آزمون تهی بودن زبان آتوماتای بوخی، آتوماتای بوخی غیرقطعی، قضیه سفرا (۳ جلسه)
- مقدمه‌ای بر رابطه مسایل تصمیم‌پذیری منطق با نظریه آتوماتا (۲ جلسه)
- مقدمه‌ای بر آتوماتای بر ورودی درختی (۲ جلسه)
ارزیابی
- آزمون میان ترم (۲۵٪ کل نمره)
- آزمون پایان ترم (۴۰٪ کل نمره)
- حداقل شش سری تمرین (۲۵٪ کل نمره)
- ارزش‌یابی مستمر در کلاس شامل چند امتحانک از پیش اعلام شده (۱۰٪ از نمره اصلی و با امکان حداکثر معادل ۵٪ نمره کمکی)
- گزارش و ارائه‌ی پژوهش (اختیاری حداکثر ۱۵٪ نمره اضافی)
مراجع
- G. Boolos, J. Burgess, and R. Jeffrey. Computability and Logic. 5th Edition, Cambridge University Press, 2007.
- D. Kozen. Theory of Computation. Springer, 2006.
- S. Hedman. A First Course in Logic: An introduction to model theory, proof theory, computability, and complexity. Oxford University Press, 2004.
- M. Sipser. Introduction to the Theory of Computation. 2nd Edition, Thompson Co., 2006.