컴퓨테이션 이론

어떤 수업인가?

• 수학 과목
• 코딩 안나옴
• 증명 과목

무엇을 배우는가?

Theory of Computation(계산 이론, 형식 언어론, 오토마타)

Computation이란?

• Compute : 컴퓨터가 하는 일
• Computer (계산기 vs 컴퓨터)
• 현대에 오면서 컴퓨터가 하는 일은 너무 많아짐. 그래서 컴퓨터가 수행하는 일에 대한 이론을 공부할 필요가 있어짐.
• 컴퓨터가 문제를 푸는 방법(방식)은 신기하게도 인간의 문제 풀이 방법(방식)을 따라했음.

결론 : 컴퓨터(인간)가 문제를 푸는 방법을 다룬다. 하지만, 컴퓨터(인간)가 문제를 푸는 방법은 상당히 복잡하므로 다양한 모델들을 사용한다.

계산 모델과 계산 이론

Abstract Model(추상화 모델? 요약화 모델!)

• Abstract Model를 "추상화" 모델이라 부르는 것은 별로 좋지 않은데, Abstract Model을 나타내는 데 부적절하기 때문. 요약화 모델이라고 부르는 것이 훨씬 나음.
• 요약화란 많은 정보들 사이에서 중요한 정보(내가 원하는 정보)들만 추려서 나타내는 것을 말함. 문제를 푸는 방법이 상당히 복잡하므로 중요한 정보들만 추려서 간단하게 나타내는 것!

이외에도 다양한 모델이 있으며, 차차 배워갈 것임

• Finite Automata : 디지털 회로 설계, 정규표현식 검색 등
• Pushdown Automata : 컴파일러, 프로그램 분석, 언어학 등
• Turing machine : 현재 컴퓨터의 모델
• ...

교육 목적

• 무엇이 풀 수 있고, 풀 수 없는지를 규정함
• 얼마나 빠르고, 얼마나 많은 메모리를 소모하는 지를 말함
• 어떤 계산 모델이 적절한지를 선택할 수 있게 해줌

생각하는 능력, 나 자체를 깔끔하게 명료하게 표현하는 방법, 문제를 푸는 방법, 문제를 풀지 못했을 때 생겨나는 일들을 아는 것 등이 교육 목적이다.