نظریه محاسبه
Theory of Computation
| کارشناسی | مقطع: | نظریه محاسبه | نام درس: |
|---|---|---|---|
| تخصصی اختیاری | گروه درس: | مبانی نظریه محاسبه | پیش‌نیاز: |
| نظری | نوع درس: | ندارد | هم‌نیاز: |
| 48 | تعداد ساعت: | 3 | تعداد واحد: |
| ندارد | حل تمرین: |
سرفصل درس:
- معرفی انواع مدل های محاسباتی تورینگ که با کامپیوتر معادل است. مدلهای محاسباتی شامل مدل ریاضی و ماشین توینگ و تز تورینگ چرچ. کدگذاری گودل و ماشین تورینگ جهانی. شمارش پذیری و محاسبه پذیری. مجموعه‌های محاسبه ناپذیر. مجموعه‌های خلاق .اوراکل. P و NP. قضیه پست. توضیحی از محاسبه پذیریهای پیچیده تر. معرفی مسئله هایی که قابل محاسبه با تورینگ ماشین نیستند. روش اثبات حل ناپذیری مسائل با reduction.
منابع:
-
Sipser, M. (2003). Introduction to the Theory of Computation. 3th Edition, ACM Sigact News, 27(1), 27-29.
-
Cooper, S. Barry. (2003) Computability theory. CRC Press.
-
M. Divis, R. Sigal, E. Weyuker, (1997), Computability, Complexity, and Languages. 2nd Edition, Academic Press.
-
Wigderson, A. (2019), Mathematics and Computation, A Theory Revolutionizing Technology and Science, Princeton University Press. Retrieved from https://www.math.ias.edu/files/Book-online-Aug0619.pdf
-
Moore, C., & Mertens, S. (2011). The Nature of Computation. Oxford University Press. Retrieved from https://www-2.dc.uba.ar/staff/becher/Hopcroft-Motwani-Ullman-2001.pdf
-
Singh, A. (2009), Elements of Computation Theory, Springer London,