이론 컴퓨터 공학의 정의.

컴퓨텨 공학의 이론적 접근은 일반적인 컴퓨터 과학가 수학의 공통분모에 대한 하위 집합 이론으로서, 기존의 컴퓨터 공학에 비하여 조금 더 수학적인 접근과 논리적 연산의 주체에 대한 컴퓨팅 주체에 초점을 맞추고 있는 학문이며 이는 연산 이론을 포함하고 있습니다. 컴퓨터 공학의 이론적 영역을 정확하게 판단하고 카테고리를 나눈다는것은 대단히 어려운 난제에 가깝습니다. 하지만 우리는 이를 알고리즘의 형태와 SIGACT 이론에 대한 정의에 의해 구분지을 수 있을 것입니다. 이는 다음과 같이 설명할 수 있습니다.

 

TCS는 컴퓨터 프로그래밍의 배타적 알고리즘, 데이터 구조, 계산적 복합성을 띄게 되며 이는 병렬 및 분산형 연산, 확률론적 연산, 양자 연산, 자동 데이터 이론, 정보화 이론, 암호구조, 프로그램 의미개론과 알고리즘 검증절차, 기계적 학습, 계산 생물학, 계산 경제학, 마지막으로 컴퓨터 그 자체를 포함한 다양한 주제를 폭넓게 아우르고 있습니다. 

 

과거 이론 컴퓨터 공학의 정의와 관련하여 논리적 추론과 수학적 증명이 역사를 거듭하면서 존재해 왔습니다. 하지만 1931년 미국의 논리학자인 커트 괴델 (Kurt Godel)은 불완전한 정리로 어떤 진술이 증명되거나 반증될 수 있다는 것에 근본적인 한계가 존재할 수 있다는 것을 증명하게 되었습니다. 이는 공리적인 방식으로만 수학의 체계를 확립할 수 있다는 정의에 반기를 든 역사적인 사건으로서 이를 '괴델의 불완전성 정리' 라고 명명 하게 됩니다.

 

이러한 발전은 논리와 계산 가능성에 대한 현대의 지속적인 연구와 실제로 이론적인 컴퓨터 공학의 전체적인 분야로 이어지게 됩니다. 정보 이론은 미국의 응용수학학자이자 컴퓨터과학자인 클로드 섀넌 (Claude Shannon)에 의해 1948년 수학적인 의사 소통 이론으로 그 분야에 추가 되게 되었습니다. 같은 해, 향후 10년 동안 연구 성과를 발표하게 되며 학계의 주목을 이끌어낸 신경 심리학 분야의 대가 캐나다 출신의 도널드 헤브 (Donald O. Hebb)는 뇌에서 학습하는 수학적 모델을 발견하게 됩니다. 이 가설을 뒷받침하는 생물학적 데이터를 탑재하게 됨으로서, 신경 네트워크 분야와 평행하게 분포된 처리가 확립되었다는 것이 학계의 정설로 굳혀지고 있습니다. 

 

1971년 스티븐 쿡 (Stephen Cook)과 독립적으로 작업한 레오니드 레빈 (Leond Leong Levin)은 실제로 관련된 문제가 존재한다는 것을 이론 컴퓨터 공학의 구축으로 증명해 내었습니다. 이는 계산적 복잡성 이론 (Computational Complexity Theory)의 획기적인 발견이라고 할 수 있습니다. 계산적 복잡성 이론은 연산 문제를 그 본질적인 연산의 난이도에 따라 자동으로 분류하게 되고, 이러한 알고리즘을 서로 연관시켜 그 방정식을 풀어나가는 것에 초점을 맞추고 있는 이론입니다. 이러한 논리적 연산에 의한 계산 문제는 알고리즘과 같은 수학적 단계를 컴퓨터를 활용한 기계적 적용으로 인해 해결할 수 있게 되었습니다.

 

사용되는 알고리즘에 관계 없이 솔루션에 상당한 리소스가 필요한 경우, 문제는 본질적으로 어려운 것으로 간주되어 지게 됩니다. 계산적 복잡성 이론은 이러한 문제를 연구하기 위해 연산의 수학적 모델을 도입하고 계산적 복잡성, 즉 시간과 스토리지와 같은 문제를 해결하기 위해 필요한 자원의 양을 수량화함으로써 이러한 직관을 공식화하는데 성공하게 됩니다. 이는 통신의 양, 회로의 게이트 수, 프로세스 수 등과 같은 다양한 복잡성의 척도로 사용되어 지고 있습니다.

 

20세기 초에 이르러 양자 역학의 발전과 함께 수학적인 작동은 전체 입자 파장에 대해 수행될 수 있다는 개념이 학계에 등장하게 되었습니다. 즉, 동시에 여러 상태에서 알고리즘 연산 수식을 계산할 수 있게 된 것입니다. 이것은 1990년대 후반에 시작된 양자 컴퓨터의 개념으로 이어지게 되며, 이에 대한 증명은 MIT의 응용 수학 교수로 활동하고 있던 미국 출신의 피터 쇼르 교수 (Peter Williston Shor) 교수에 의해 진행되게 되었습니다. 그는 특히 고전적인 컴퓨터의 역할에서 실행되어 왔던 당시 최고 수준의 알고리즘보다 훨씬 더 높은 수준의 기하 급수적으로 빠른 알고리즘 요소를 도출하기 위한 알고리즘인 Shor의 알고리즘을 고안 해 내게 되었습니다.