계산 이론 개요

계산 이론 theory of computation

- 컴퓨터 과학의 한 분야

- 어떤 문제를 컴퓨터로 풀수있는지 -> 계산 가능성 이론 computability theory

- 얼마나 효율적으로 풀수있는지 탐구 -> 계산 복잡도 이론 computational complexity theory

=> 계산 이론은 계산 가능성 이론과 계산 복잡도 이론 2분야로 나뉨

 

 

계산 computation

- 주어진 입력으로부터 문제의 해법을 찾는 것

- 수학자들이 수학 문제를 간단한 방법 simple method로 해결가능한지 알려고함

=> 계산의 형식 모델 formal model of computation 이 요구됨