نظریه محاسبات پیشرفته
Advanced Theory of Computation
شماره درس: ۴۰۷۹۵.۳ | تعداد واحد: ۳ |
مقطع: کارشناسی ارشد | نوع درس: نظری |
پیشنیاز: – | همنیاز: – |
اهداف درس
هدف از این درس ارائهی دقیق انواع مدلهای ریاضی ارایهشده در تعریف مفهوم محاسبه و محاسبهپذیری و نتایج حاصل از آنها با فرض تسلط دانشجویان بر نظریهی زبانها و ماشینها و نظریهی محاسبات مقدماتی است.
ریز مواد
- مروری بر نظریهی ماشینهای تورینگ، ماشینهای تورینگ چندنواری و غیرقطعی، تز تورینگ-چرچ، مسایل و زبانهای بازگشتی و بهطور بازگشتی شمارا. مروری بر مسایل تصمیم ناپذیر، مسالهی توقف و انواع آن، قضیهی رایس. مروری بر کلاسهای پیچیدگی الگوریتمها.
- ماشینهای تورینگ تناوبی (Alternating TM) و ماشینهای تورینگ پیشگو (Oracle TM) و قضایای مربوط به آنها.
- نظریهی توابع بازگشتی و تز چرچ. حساب لامبدا و قضایای تمامیت آن، توابع بازگشتی جزیی و عددگذاری گدلی.
- خودارجاعی (Self-Reference)، قضیه Knaster-Tarski و بهکارگیری آن در نظریهی خودکارها و منطقهای نقطهی ثابت، مفاهیم منطقی اثبات (Provability Logic).
- مقدمهای بر نظری آتوماتای متناهی بر رشتههای نامتناهی، منطق مرتبهی دوم Monadic و نتایج بوخی و رابین در ارتباط آتوماتای بر رشتههای نامتناهی با منطقهای مرتبهی دوم.
- قضیهی تناظر Post و سیستمهای Post.
- سیستمهای محاسباتی منصف (Fair Systems) و قضیه Harel. انواع تعاریف انصاف و قضایای مرتبط.
- قضیهی کلینی (Kleene Theorem) و نتایج آن، مروری بر انواع جبرهای کلینی (Kleene Algebras).
- مروری بر نظریهی انواع چرچ (Church's Type Theory) و نظریهی انواع ساختی مارتین-لاف (Lof's Constructive Type Theory).
ارزیابی
- تمرین: شش سری تمرین مسئله مدار و پژوهش مدار (۲۰٪ کل نمره)
- پروژه پژوهشی: شامل گزارش پژوهشی و سمینار (۲۰٪ کل نمره)
- آزمون: آزمونهای میانترم و پایانترم (۶۰٪ کل نمره)
مراجع
- D. Kozen. Theory of Computation. Springer, 2006.
مراجع کمکی
- C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- Lane A. Hemaspaandra and Mitsunori Ogihara. The Complexity Theory Companion. Springer, 2002.
- M. R. Garey and D. S. Johnson. Computers and Intractibility: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979.
- J. E. Hopcroft and J. D. Ullman. Introduction to Automata Theory, Languages, and Computation. 3rd edition, Addison-Wesley, 2006.
- H. Rogers, Jr. Theory of Recursive Functions and Effective Computability. McGraw-Hill, 1967.
- Ingo Wegener. Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer, 2005.
- Steven Homer and Alan L. Selman. Computability and Complexity Theory. 2nd edition, Springer, 2011.