نظریه‌ی محاسبه - کارشناسی علوم کامپیوتر

ترم اول سال تحصیلی ۹۶-۱۳۹۵

اخبار درس

۱۹ شهریور ۹۵

با سلام. به درس نظریه‌ی محاسبه خوش آمدید. مزید امتنان است ضمن ثبت‌نام در سامانه‌ی آموزشی دانشگاه؛ اطلاعات پرسش‌نامه‌ی درس را پس از جلسه‌ی اول و قبل از جلسه‌ی سوم تکمیل فرمایید. لینک‌های مربوطه‌ را می‌توانید در قسمت پیوندها مشاهده نمایید.

اطلاعات عمومی

تاریخ‌های مهم
  • یک‌شنبه؛ ۲ آبان ۱۳۹۵ - میان‌ترم اول
  • سه‌شنبه؛ ۱۶ آذر ۱۳۹۵ - میان ترم دوم
  • آزمون پایان ترم - طبق اعلام سیستم گلستان
سرفصل درس
بخش ۱: نظریه‌ی محاسبه‌پذیری شامل نظریه‌ی چرچ-تورینگ، ماشین‌های تورینگ و انواع آن، تعریف الگوریتم و مسائل هیلبرت، تصمیم‌پذیری، زبان‌های تصمیم‌پذیر، تصمیم‌ناپذیری، قطری سازی، کاهش‌پذیری، مسائل تصمیم‌ناپذیر در نظریه‌ی زبان، توابع محاسبه‌پذیر، قضیه‌ی Rice، قضیه‌ی بازگشتی، تصمیم‌پذیری نظریه‌های منطق، کاهش‌پذیری تورینگ، اعداد گودل، قضایای مختلف در نظریه‌ی بازگشت، توابع بازگشتی اولیه، توابع بازگشتی جزئی.
بخش ۲: نظریه‌ی پیچیدگی شامل پیچیدگی زمانی، رده‌های P و NP، NP-کامل بودن و برخی مسائل NP-کامل، پیچیدگی حافظه، قضیه Savitch، رده‌ی PSPACE، PSPACE-کامل بودن، رده‌های L و NL، NL-کامل بودن، برابری NL و coNL.
مراجع
  • [S12] Sipser, Michael. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2012.
  • [B94] Bridges, Douglas S. Computability: a mathematical sketchbook. Vol. 146. Springer Science & Business Media, 1994.
از مرجع [S12]، فصل‌های ۳ الی ۸ و از مرجع [B94]، فصل‌های ۲ الی ۵ مورد نیاز خواهند بود.
پیوندها
تحویل به موقع تمرین‌ها
در این درس حداقل ۱۲ سری تمرین خواهیم داشت و لازم است تا تمرین‌ها در موعد مقرر، تحویل شوند. به ازای هر روز تاخیر در تحویل تمرین، %۱۰ نمره کسر خواهد شد و پس از گذشت 72 ساعت از موعد تحویل، %۱۰۰ نمره کسر می‌گردد.

جلسات درس

جلسه‌ی اول

آزمون‌ها

...

نمرات

ردیف عنوان نمره شرح
۱ تمرین ۵ شامل حداقل ۱۲ سری تمرین
۲ آزمون‌های کتبی میان‌ترم اول ۳ ۱۰ یک‌شنبه، ۲ آبان ۱۳۹۵ (فصل‌های ۳ تا ۵ از [S12])
میان‌ترم دوم ۳ سه‌شنبه، ۱۶ آذر ۱۳۹۵ (فصل‌های ۷ و ۸ از [S12])
پایان ترم ۹ کل مباحث
۳ تلاش بیشتر  
جمع نمرات ۲۰ + ۲

سوالات رایج

...