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

Advanced Theory of Computation

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

هدف کلی

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

سرفصل‌ها

  1. مروری بر اصول نظریه محاسبات
  2. مروری بر اصول نظریه پیچیدگی
  3. ماشین‌های تورینگ تناوبی و پیشگو
  4. حساب (arithmetic) و نظریه محاسبات
  5. خودارجاعی (Self-Reference) در محاسبه‌پذیری و منطق
  6. مقدمه‌ای بر نظریه اتوماتای متناهی بر رشته‌ها و درخت‌های نامتناهی
  7. سیستم‌های محاسباتی منصف (Fair Systems)
  8. سیستم‌های کلینی (Kleene)
  9. نظریه انواع (Type Theory) چرچ و مارتین-لاف
  10. توصیف و تحلیل سیستم‌های انواع در نظریه زبان‌های برنامه‌سازی

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

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

  1. D. Kozen. Theory of Computation. Springer, 2006.
  2. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  3. J. Shallit. A Second Course in Formal Languages and Automata Theory. Cambridge University Press, 2008.
  4. S. Homer and A. L. Selman. Computability and Complexity Theory. 2nd Edition, Springer, 2011.
  5. I. Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005.