이론 컴퓨터 과학

이론 컴퓨터 과학 또는 이론 전산학(영어: theoretical computer science)은 컴퓨터 과학 및 수학의 한 분야로, 컴퓨터나 계산 과정의 추상적이고 근본적인 원리를 연구하는 학문이다.

계산 모형의 일종인 튜링 기계의 시각화

역사적으로 보았을 때 컴퓨터 과학의 기원은 수리 논리학의 발전과 함께 대두한 계산 가능성 연구로, 이에 관한 결정 문제와 튜링 기계 등을 논하던 계산 이론으로부터 이후 실질적인 응용으로 발전하여 나온 것이다. 이론 전산학과 일반적인 응용 전산학을 구분하는 명확한 기준은 없으나, 이론 전산학은 대체로 수학적인 면에 치중하는 경향이 있다.

이론 전산학은 계산 가능성 이론, 오토마타 이론 등 수리논리학적 분야를 기초로 삼으며, 더욱 세부적인 연구 분야로는 그래프 이론, 조합론, 정수론, 암호학, 유형 이론, 계산 복잡도 이론, 최적화 이론 등에 관한 연구가 있다.

같이 보기

• 재귀 이론
• 튜링 기계
• 수리 논리학