نظریه محاسبات

Theory of Computation

شماره درس: ۴۰۴۵۵ تعداد واحد: ۳
مقطع: کارشناسی نوع درس: نظری
پیش‌نیاز: ساختمان داده‌ها و الگوریتم‌ها هم‌نیاز: –

اهداف درس

هدف از ارائه‌ی این درس آشنایی دانشجویان با مبانی نظریه‌ی محاسبات و مفاهیم اصلی مدل‌های محاسبه‌پذیری، مسائل حل‌شدنی، منطق ریاضی و مقدمه‌ای بر نظریه آتوماتا بر ورودی‌های نامتناهی رشته‌ای یا درختی‌ است. این درس در واقع تأمین‌کننده پایه‌ی نظری لازم برای دانشجویانی است که در دوره‌های تحصیلات تکمیلی در گرایش‌های نظریه‌ی محاسبات و الگوریتم یا روش‌های صوری در مهندسی نرم‌افزار و درستی‌یابی سیستم‌ها تحصیل می‌کنند، و همچنین منطق ریاضی لازم برای هوش مصنوعی را بنا می‌نهد.

ریز مواد

درس شامل سه بخش اصلی است:

ارزیابی

مراجع

  1. G. Boolos, J. Burgess, and R. Jeffrey. Computability and Logic. 5th Edition, Cambridge University Press, 2007.
  2. D. Kozen. Theory of Computation. Springer, 2006.
  3. S. Hedman. A First Course in Logic: An introduction to model theory, proof theory, computability, and complexity. Oxford University Press, 2004.
  4. M. Sipser. Introduction to the Theory of Computation. 2nd Edition, Thompson Co., 2006.