نظریه محاسبات
زمینهٔ وسیعی که امکان و کارایی حل مسائل گوناگون را به وسیلهٔ مدلهای محاسباتی، با استفاده از الگوریتمها را مورد مطالعه قرار میدهد / From Wikipedia, the free encyclopedia
نظریهٔ رایانش[1] یا نظریهٔ محاسبات (به انگلیسی: Theory of computation) زمینهٔ وسیعی است که امکان و کارایی حل مسائل گوناگون به وسیلهٔ مدلهای محاسباتی، با استفاده از الگوریتمها را مورد مطالعه قرار میدهد.
این نظریه را به دو شاخهٔ عمده بهصورت زیر تقسیم میکنند:
- نظریهٔ محاسبهپذیری یا قابلیت محاسبه
- نظریهٔ پیچیدگی
هر دو شاخهٔ فوق با مدلهای صوری محاسبات سر وکار دارد.