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

نظریه محاسبات (شماره درس: ۴٠۴۵۵)

Theory of Computation

اهداف درس نظریه محاسبات

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

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

1. نظریه ی محاسبه پذیری و مقدمه ای بر پیچیدگی محاسبات
   • مدل تورینگی محاسبه، تز تورینگ‐چرچ، توابع و زبانهای تصمیم پذیر (بازگشتی)، توابع و زبان های تشخیص پذیر (بازگشتیانه شمارش پذیر)، توابع محاسبه نا پذیر، مساله ی توقف، ماشین تورینگ جهانی، ماشین تورینگ چند نواری و ماشین تورینگ غیرقطعی و قضایای معادل بودن آنها (٣ جلسه)
     • روش های اثبات تصمیم ناپذیری و تشخیص ناپذیری زبان ها شامل روش کاهش به مساله توقف و روش کاهش تابعی (٢ جلسه)
     • مقدمه ای بر سایر مدل های محاسبه (٢ جلسه)
2. مدل ماشین دسترسی تصادفی (RAM) فون نیومان
3. نظریه ی توابع بازگشتی کلینی
4. حساب لامبدا چرچ
5. سیستم های پست
   • قضیه ی بازگشتی و خود‐ارجاعی (١ جلسه)
   • تعریف محاسباتی اطلاعات و پیچیدگی رشته ای (٢ جلسه)
   • مقدمه ای بر نظریه ی پیچیدگی و مروری بر کلاس های پیچیدگی زمان و حافظه و مسایل دشوار (٣ جلسه)
6. منطق ریاضی از منظر نظریه ی محاسبات
   • منطق گزاره ها، نحو و معناشناسی آن، سیستم استنتاجی اصل موضوعی و قضایای صحت و تمامیت آن، قضایای تصمیم پذیری منطق گزاره ها (٢ جلسه)
   • منطق مرتبه اول، نحو و معناشناسی آن، قضایای فشردگی و لوون هایم‐اسکولم (٢ جلسه)
   • سیستم استنتاجی اصل موضوعی منطق مرتبه ی اول و قضیه ی صحت آن (١ جلسه)
   • قضیه ی گدل در تمامیت سیستم استنتاجی منطق مرتبه ی اول (١ جلسه)
   • قضیه چرچ در تصمیم ناپذیری منطق مرتبه ی اول (٢ جلسه)
   • سیستم های اصل موضوعی نظریه اعداد و قضیه ناتمامیت گدل (شکل اول و دوم) (٢ جلسه)
7. مقدمه ای بر نظریه آتوماتا بر ورودی های نامتناهی
   • آتوماتای بوخی و رابین بر رشته های نامتناهی (٢ جلسه)
   • قضایای مربوط به مکمل کردن و آزمون تهی بودن زبان آتوماتای بوخی، آتوماتای بوخی غیرقطعی، قضیه سفرا (٣جلسه)
   • مقدمه ای بر رابطه مسایل تصمیم پذیری منطق با نظریه آتوماتا (٢ جلسه)
   • مقدمه ای بر آتوماتای بر ورودی درختی (٢ جلسه)

ارزیابی درس نظریه محاسبات

• آزمون میان ترم (٢۵ ٪کل نمره)
• آزمون پایان ترم (۴٠ ٪کل نمره)
• حداقل شش سری تمرین (٢۵ ٪کل نمره)
• ارزش یابی مستمر در کلاس شامل چند امتحانک از پیش اعلام شده (١٠ ٪از نمره اصلی و با امکان حداکثر معادل ۵ ٪نمره کمکی)
• گزارش و ارائه ی پژوهش (اختیاری حداکثر ١۵ ٪نمره اضافی)

مراجع درس نظریه محاسبات

[1] G. Boolos, J. Burgess, and R. Jeffrey. Computability and Logic. 5th edition, Cambridge UniversityPress, 2007.
[2] D. Kozen. Theory of Computation. Springer, 2006.
[3] S. Hedman. A First Course in Logic: An introduction to model theory, proof theory, computability,and complexity. Oxford University Press, 2004.
[4] M. Sipser. Introduction to the Theory of Computation. 2nd edition, Thompson Co., 2006.