نظریه محاسبه
Theory of Computation
| نام درس: | نظریه محاسبه | مقطع: | کارشناسی |
|---|---|---|---|
| پیش‌نیاز: | مبانی نظریه محاسبه | گروه درس: | تخصصی اختیاری |
| هم‌نیاز: | ندارد | نوع درس: | نظری |
| تعداد واحد: | 3 | تعداد ساعت: | 48 |
| حل تمرین: | ندارد |
سرفصل درس:
- معرفی انواع مدل های محاسباتی تورینگ که با کامپیوتر معادل است. مدلهای محاسباتی شامل مدل ریاضی و ماشین توینگ و تز تورینگ چرچ. کدگذاری گودل و ماشین تورینگ جهانی. شمارش پذیری و محاسبه پذیری. مجموعه‌های محاسبه ناپذیر. مجموعه‌های خلاق .اوراکل. 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, https://link.springer.com/book/10.1007/978-1-84882-497-3