درس نظریه محاسبه (بهار ۹۴-۹۵)

در این درس با قابلیت‌ها و عدم قابلیت‌های ماشین تورینگ به عنوان قوی‌ترین ماشین محاسباتی شناخته شده می‌پردازیم.

فیلم‌های درس در سایت ویدئوی دانشکده ریاضی شریف اینجاست.

مبحث منبع
ماشین تورینگ فصل ۷ از کتاب مارتین
زبان‌های بازگشتی و بازگشتی شمارشی فصل ۸ از کتاب مارتین (۸.۱ تا ۸.۳ و ۸.۵)
مسئله‌های تصمیم‌ناپذیر فصل ۹ از کتاب مارتین (۹.۱ تا ۹.۴)
توابع محاسبه‌پذیر فصل ۱۰ از کتاب مارتین
شمارش موثر فصل ۳ از کتاب بریحز (قضیه‌های ۳.۶ و ۳.۸ و ۳.۹ آن‌چه برای فهم آن‌ها نیاز است)
دو قضیه از توابع محاسبه‌پذیر فصل ۴ از کتاب بریحز (قضیه‌های ۴.۲ و ۴.۳)
قضیه بازگشت و رایس فصل ۵ از کتاب بریحز (قضیه‌های۵.۱ و ۵.۲ و ۵.۴ و ۵.۵ و ۵.۶ و ۵.۸ و ۵.۱۰ (قضیه رایس) و ۵.۱۱ و ۵.۱۳ (قضیه بازگشت))
قضیه بازگشت (این‌بار با نگاه کامپیوتری) فصل ۶.۱ از کتاب سیپسر
اثبات‌پذیری نظریه‌های منطقی فصل ۶.۲ از کتاب سیپسر
تقلیل تورینگ فصل ۶.۳ از کتاب سیپسر
نظریه اطلاعات فصل ۶.۴ از کتاب سیپسر
پیچیدگی محاسبه فصل ۷ از کتاب سیپسر (۷.۲ تا ۷.۴)
اتوماتای سلولی -

اسلایدها:

  • اسلایدهای جلسه اول (معرفی درس)

منابع

  1. Martin. Introduction to Languages and the Theory of Computation. 4th ed.  McGraw-Hill Education, 2010. ISBN: 9780073191461.
  2. Bridges. Computability: A Mathematical Sketchbook.  Springer, 1998. ISBN: 9780387941745.
  3. Sipser Introduction to the Theory of Computation. 3rd ed.  Cengage Learning, 2012. ISBN: 978-1133187790.
  4. درس نظریه محاسبه در مکتب‌خونه
  5. جزوه درس از جلسه ۷ تا ۲۳

تمرین‌ها و امتحان‌ها

  1. تمرین سری ۱ (راه حل)
  2. تمرین سری ۲ (راه حل)
  3. تمرین سری ۳ (راه حل)
  4. تمرین سری ۴ (راه حل)
  5. تمرین سری ۵ (راه حل)
  6. کوئیز ۱
  7. میان‌ترم
  8. پایان‌ترم