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

Advanced Theory of Computation

شماره درس: ۴۰۷۹۵.۳ تعداد واحد: ۳
مقطع: کارشناسی ارشد نوع درس: نظری
پیش‌نیاز: – هم‌نیاز: –

اهداف درس

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

ریز مواد

  1. مروری بر نظریه‌ی ماشین‌های تورینگ، ماشین‌های تورینگ چندنواری و غیرقطعی، تز تورینگ-چرچ، مسایل و زبان‌های بازگشتی و به‌طور بازگشتی شمارا. مروری بر مسایل تصمیم ناپذیر، مساله‌ی توقف و انواع آن، قضیه‌ی رایس. مروری بر کلاس‌های پیچیدگی الگوریتم‌ها.
  2. ماشین‌های تورینگ تناوبی (Alternating TM) و ماشین‌های تورینگ پیشگو (Oracle TM) و قضایای مربوط به آن‌ها.
  3. نظریه‌ی توابع بازگشتی و تز چرچ. حساب لامبدا و قضایای تمامیت آن، توابع بازگشتی جزیی و عددگذاری گدلی.
  4. خودارجاعی (Self-Reference)، قضیه Knaster-Tarski و به‌کارگیری آن در نظریه‌ی خودکارها و منطق‌های نقطه‌ی ثابت، مفاهیم منطقی اثبات (Provability Logic).
  5. مقدمه‌ای بر نظری آتوماتای متناهی بر رشته‌های نامتناهی، منطق مرتبه‌ی دوم Monadic و نتایج بوخی و رابین در ارتباط آتوماتای بر رشته‌های نامتناهی با منطق‌های مرتبه‌ی دوم.
  6. قضیه‌ی تناظر Post و سیستم‌های Post.
  7. سیستم‌های محاسباتی منصف (Fair Systems) و قضیه Harel. انواع تعاریف انصاف و قضایای مرتبط.
  8. قضیه‌ی کلینی (Kleene Theorem) و نتایج آن، مروری بر انواع جبرهای کلینی (Kleene Algebras).
  9. مروری بر نظریه‌ی انواع چرچ (Church's Type Theory) و نظریه‌ی انواع ساختی مارتین-لاف (Lof's Constructive Type Theory).

ارزیابی

  • تمرین: شش سری تمرین مسئله مدار و پژوهش مدار (۲۰٪ کل نمره)
  • پروژه پژوهشی: شامل گزارش پژوهشی و سمینار (۲۰٪ کل نمره)
  • آزمون: آزمون‌های میان‌ترم و پایان‌ترم (۶۰٪ کل نمره)

مراجع

  1. D. Kozen. Theory of Computation. Springer, 2006.

مراجع کمکی

  1. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  2. Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Springer, 2002.
  3. M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
  4. J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd edition, Addison-Wesley, 2006.
  5. H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.
  6. Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005.
  7. Steven Homer and Alan L. Selman. Computability and Complexity Theory. 2nd edition, Springer, 2011.