نظریه محاسبه

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, url:https://link.springer.com/book/10.1007/978-1-84882-497-3