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

Theory of Computation

مقطع: کارشناسی گرایش: نرم‌افزار
نوع درس: نظری تعداد واحد: ۳
پیش‌نیاز: داده‌ساختارها و الگوریتم‌ها هم‌نیاز: –

هدف کلی

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

سرفصل‌ها

درس شامل سه بخش اصلی است:

  1. نظریه‌ی محاسبه‌پذیری و مقدمه‌ای بر پیچیدگی محاسبات
    • مدل تورینگی محاسبه، تز تورینگ-چرچ، توابع و زبان‌های تصمیم‌پذیر (بازگشتی)، توابع و زبان‌های تشخیص‌پذیر (بازگشتیانه شمارش‌پذیر)، توابع محاسبه نا‌پذیر، مساله‌ی توقف، ماشین تورینگ جهانی، ماشین تورینگ چند نواری و ماشین تورینگ غیرقطعی و قضایای معادل بودن آن‌ها (۳ جلسه)
    • روش‌های اثبات تصمیم‌ناپذیری و تشخیص‌ناپذیری زبان‌ها شامل روش کاهش به مساله توقف و روش کاهش تابعی (۲ جلسه)
    • مقدمه‌ای بر سایر مدل‌های محاسبه (۲ جلسه)
      • مدل ماشین دسترسی تصادفی (RAM) فون‌نیومان
      • نظریه‌ی توابع بازگشتی کلینی
      • حساب لامبدا چرچ
      • سیستم‌های پست
    • قضیه‌ی بازگشتی و خود-ارجاعی (۱ جلسه)
    • تعریف محاسباتی اطلاعات و پیچیدگی رشته‌ای (۲ جلسه)
    • مقدمه‌ای بر نظریه‌ی پیچیدگی و مروری بر کلاس‌های پیچیدگی زمان و حافظه و مسائل دشوار (۳ جلسه)
  2. منطق ریاضی از منظر نظریه‌ی محاسبات
    • منطق گزاره‌ها، نحو و معناشناسی آن، سیستم استنتاجی اصل موضوعی و قضایای صحت و تمامیت آن، قضایای تصمیم‌پذیری منطق گزاره‌ها (۲ جلسه)
    • منطق مرتبه اول، نحو و معناشناسی آن، قضایای فشردگی و لوون‌هایم-اسکولم (۲ جلسه)
    • سیستم استنتاجی اصل موضوعی منطق مرتبه‌ی اول و قضیه‌ی صحت آن (۱ جلسه)
    • قضیه‌ی گدل در تمامیت سیستم استنتاجی منطق مرتبه‌ی اول (۱ جلسه)
    • قضیه چرچ در تصمیم‌ناپذیری منطق مرتبه‌ی اول (۲ جلسه)
    • سیستم‌های اصل موضوعی نظریه اعداد و قضیه ناتمامیت گودل (شکل اول و دوم) (۲ جلسه)
  3. مقدمه‌ای بر نظریه آتوماتا بر ورودی‌های نامتناهی
    • آتوماتای بوخی و رابین بر رشته‌های نامتناهی (۲ جلسه)
    • قضایای مربوط به مکمل‌کردن و آزمون تهی بودن زبان آتوماتای بوخی، آتوماتای بوخی غیرقطعی، قضیه سفرا (۳ جلسه)
    • مقدمه‌ای بر رابطه مسائل تصمیم‌پذیری منطق با نظریه آتوماتا (۲ جلسه)
    • مقدمه‌ای بر آتوماتای بر ورودی درختی (۲ جلسه)

ارزیابی پیشنهادی

منابع پیشنهادی

  1. G. Boolos, J. Burgess, and R. Jeffrey. Computability and Logic. 5th Edition, Cambridge University Press, 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. 3rd Edition, Cengage Learning, 2012.