Computation
계산이론 (Theory of Computation) 은 컴퓨터과학의 한 분야로, 어떤 문제를 컴퓨터로 풀수 있는지, 또 얼마나 효율적으로 풀수 있는지를 탐구한다. 이 분야는 크게 계산가능성 이론 (Computability Theory) 과 계산복잡도이론 (Computational Complexity Theory) 으로 나뉘어 있는데, 두 분야 모두 추상 기계를 다룬다.... 위키백과 : 계산이론
Computation 은 주어진 입력으로부터 문제의 해법을 찾는 것으로 정의될 수 있다. 그것이 컴퓨터과학과 수학의 하위과목인 계산이론 (Theory of Computation) 에서 다루는 것이다. 그것은 현대적인 전자컴퓨터가 발명되기 전인 20 세기에 처음 등장했다. 그때 수학자들은 수학문제들이 간단한 방법으로 해결가능한지 아닌지를 알려고 노력했다. 첫째 단계가 문제를 풀기위한 "간단한 방법 (simple method)" 이 의미하는 바를 정의하는 것이었다. 달리말하면, 계산의 형식모델 (formal model of computation) 을 필요로 했다.
초기의 연구자들에 의해 여러개의 계산모델이 만들어졌다. 그중 하나가 튜링기계 (Turing Machine) 으로서 read/write head 가 스캐닝하는 데로 언제든지 사각형의 무한 길이의 테이프상에 문자를 저장하는 것이다. 또다른 모델이 재귀함수 (Recursive Function) 으로서 수에 관한 연산을 위해 함수와 함수의 조합을 사용한다. 람다 계산법 (Lambda Calculus) 도 유사한 접근방법을 사용한다. 이와는 다른 것으로서 마르코프 알고리즘 (Markov Algorithm) 과 포스트 시스템 (Post Systems) 은 문자열에 관한 연산을 위해 grammar-like rules 를 사용한다. 이러한 형식모델 (formalisms) 들은 계산능력에서 동등한 것으로 보여지는데 -- 즉 그중 하나의 모델로 수행될 수 있는 어떠한 계산도 다른 모델로도 수행될수 있다. 또한 그 모델들은 컴퓨터가 무한 메모리를 가지고 있다고 가정하면 보통의 컴퓨터에서 동등한 능력을 보인다. 결국 알고리즘 개념이 "적절하게 (proper)" 형식화되면 모든 알고리즘은 Turing Machine 에서 수행될수 있다고 알려지게 되었고 ; 그것은 처치-튜링 명제 (Church-Turing Thesis) 라고 알려지게 되었다. 대개 어떤 것이 기계로 계산될 수 있는가에 대한 의문은 계산가능성 이론 (Computability Theory) 에서 다루어진다.
계산이론 (Theory of Computation) 은 이러한 일반적인 계산모델을 연구하며, 또한 컴퓨팅의 한계도 연구한다 : 어떤 문제가 컴퓨터로 해결불가능 한가? (예를들면 halting problem, Post correspondence problem) 어떤 문제가 컴퓨터로 해결가능 하지만 해법이 비현실적이어서 계산에 너무 오랜 시간이 필요한가? (예를들면 Presburger arithmetic) 주어진 해법을 체크하는 것보다 문제를 해결하는 것이 더 어려울 수 (hard) 있는가? (예를들면 복잡도 부류 P 와 NP). 대개 주어진 문제에서 필요로 하는 시간과 메모리와 관련된 의문은 계산복잡도이론 (Computational Complexity Theory) 에서 다루어진다.
일반적인 계산모델에 덧붙여서, 더 단순한 계산모델들이 특별히 제한된 응용에 사용된다. 예를들면 regular expressions 이 유닉스와 Perl 같은 프로그램 언어에서 문자열 패턴을 나타내는데 사용된다. Regular expression 과 수학적으로 동등한 또다른 형식 (formalism) 인 Finite automata 는 회로설계와 여러 종류의 problem-solving 에 사용된다. 문맥자유 문법 (Context Free Grammar) 는 프로그램 언어 문법에서 사용된다. Non-deterministic pushdown automata 는 context-free grammar 와 동등한 또다른 형식이다. Primitive recursive function 은 recursive function 의 하위부류이다.
계산의 다른 모델들은 다른 작업을 수행하는 능력을 가진다. 계산모델의 능력을 측정하는 한가지 방법은 그 모델이 생성할 수 있는 형식언어 (Formal Language) 의 종류를 연구하는 것이다 ; 이것은 언어에 대한 촘스키계층 (Chomsky Hierarchy) 로 이끈다.
다음 표에서는 계산가능성 이론 (Computability Theory) (청색) 과 계산복잡도이론 (Computational Complexity Theory) (녹색) 에서 고려되는 문제들 (또는 언어, 문법들) 을 분류하는 일부를 보여준다. 만일 문제 X 가 Y 의 진부분집합 이라면 X 는 Y 의 아래에 위치하고 검은색 선으로 연결된다. 만일 X 가 부분집합이지만 같은 집합 (equal sets) 인지도 모를 때는 점선으로 연결된다. ........... (Wikipedia : Computation)
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|||||
|
|
|
| ||||||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
| ||||||||||
|
|
|
|
|
|
|
|
| |||
|
|
|
|
|
|
|
|
| |||
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
| |||||
|
|
|
|
|
|
|
|
| |||
|
|
|
|
|
|
|
|
| |||
|
|
|
|
|
|
|
|
|
|||
|
|
|
| ||||||||
|
|
|
|
|
| ||||||
|
|
|
|
| |||||||
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|||||
site :
Online papers : Computationalism : David Chalmers
paper :
기계와 계산 (Machine and Computation) : Allen Newell
video :
컴퓨테이션 이론, 2014년 2학기 : 건국대학교 : 남원홍 ... 동영상 23개
Theory of Computation - Fall 2011 (Course) : UCDavis : Dan Gusfield, 2012/12/11 .... Playlist 22 : text ... Introduction to the Theory of Computation (Michael Sipser)
Introduction to the Theory of Computation : Coderisland : Shai Simonson, 2010/05/07 .... Playlist 129