문서 보기문서 편집수정 내역 이론 컴퓨터 과학 (r0 버전으로 되돌리기) [include(틀:이론 컴퓨터 과학)] ||<tablewidth=100%><tablealign=center><tablebordercolor=#aa3366><tablebgcolor=#aa3366> {{{#ffffff '''이론 컴퓨터 과학 관련 틀'''}}} || ||<bgcolor=#fff,#1f2023> {{{#!folding [ 펼치기 · 접기 ] [include(틀:과학의 범위)] [include(틀:형식과학)] [include(틀:수학기초론)] [include(틀:이산수학)] [include(틀:컴퓨터공학)] }}} || [목차] == 개요 == 이론 컴퓨터 과학(영어: theoretical computer science) 또는 이론 전산학은 [[컴퓨터과학]]과 [[수학]]의 한 분야로, [[컴퓨터]]나 계산 과정의 추상적이고 근본적인 원리를 연구하는 학문이다. 컴퓨팅 이론(Computing Theory)라고도 한다. == 분류 == === 계산 이론(計算理論, Theory of computation) === ==== 계산 가능성 이론 ==== 계산 가능성 이론(computability theory)은 수학기초론과 이론 컴퓨터 과학의 대표적인 분야로, 계산 모형이 어떠한 계산을 할 수 있는지 다루는 것이다. ===== [[오토마타]] 이론 ===== '''오토마타 이론'''는 '자동'을 의미하는 그리스 단어인 Αυτόματα에서 유래한 용어로, 계산 능력이 있는 추상 기계와, 그 기계를 이용해서 풀 수 있는 문제들에 대해 학문적으로 접근한 [[컴퓨터과학]] 분야를 일컫는 말이다. 오토마타 이론은 [[컴퓨터 구조]] 설계, [[컴파일러]] 설계, 파싱, 정형화 등에 있어서 중요한 역할을 담당하는 이론이다. A survey for Modeling and Control of Hybrid System[* Labinaz, Gino, Mohamed M. Bayoumi, and Karen Rudie. "A survey of modeling and control of hybrid systems." Annual Reviews in Control 21 (1997): 79-92. 의 번역본]에 따르자면 "[[오토마톤]]이란 수학적으로 추상화된 개념으로 쓰일 경우, 자동기계를 기능적인 견지에서 모델화하여, 외부로부터의 자극, 입력신호에 대응하여 내부의 상태가 변화하고, 그리고 신호 또는 동작의 형태로 외부에 출력하는 것으로 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어 맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’ 에 관계되는 것이다." 라고 정의할 수 있다. ==== 계산 복잡도 이론 ==== 계산 복잡도(Computational complexity) 이론은, 계산 모형이 각 [[알고리즘]]에 대해 갖는 계산 복잡도를 분류하는 분야이다. 계산 가능성 이론은, 그 문제를 컴퓨터가 다룰 수 있는지 평가하지만, 그 결과가 얼마나 빠르게 나올지는 알 수 없다.[* [[체스]]나 [[바둑]]같은 2인 유한 턴제 확정 완전 정보 게임의 경우 [[체르멜로 정리]]에 의해 필승법이 항상 있고, [[경우의 수]]가 유한하므로 당연히 계산 가능하지만, 판의 크기를 n×n로 일반화하면 NP-Hard임이 알려져 있다.] 계산 복잡도 이론은 이러한 문제를 현실에서 어느 정도의 노력을 들여 풀 수 있는지, 얼마나 간단히 풀 수 있는지 평가 할 수 있도록 한다. === [[알고리즘|컴퓨터 알고리즘]] 성능 분석법 === 시간복잡도와 공간복잡도 계산 방법이 있다. * [[알고리즘]] 문서 참조 ==== [[P-NP 문제]] ==== [include(틀:상세 내용, 문서명=P-NP 문제)] === 수학적 최적화 === 제약 조건 내에서 최댓값 및 최소값을 계산하는 분야로, 이론 컴퓨터 과학의 중요한 분과이다. '''[[최적화 이론]]'''이라고도 한다. 일반적으로 이를 푸는 것(조합 최적화)은 알려진 다항 시간 해법이 없어 근사 해법을 구하거나 [[인공지능]], 담금질 기법, 선형계획법, 비선형계획법 등 다양한 기법을 도입한다. 볼록집합 등 다항 시간 해법이 존재하는 경우가 있어, 이러한 경우 별도의 분야가 있다. === [[이산수학]], [[수치해석학]] === [[이산수학]] 외에도 이산적인 세계외에 연속적인 세계에서의 공학적 이슈도 다룰 수 있는 [[수치해석학]] 도 컴퓨팅 이론의 한 분류이다. 사실상 수학 공식을 컴퓨터에서 표현하고 구동시키면 컴퓨터 [[알고리즘]]이 되는 것이다. === [[정보이론]] === 정보이론(Information Theory)은 디지털 정보의 정량화, 저장, 그리고 의사소통을 연구하는 과학적 연구이다. === 부호이론 (Coding theory) === 부호 이론은 부호의 속성과 특정 응용 프로그램에 대한 부호의 적합성에 대한 연구이다. 부호는 데이터 압축, 암호화, 오류 감지 및 수정, 데이터 전송 및 데이터 스토리지에 사용된다. 부호는 효율적이고 신뢰할 수 있는 데이터 전송 방법을 설계하기 위해 정보이론, 전기공학, 수학, 언어학 및 컴퓨터과학과 같은 다양한 과학 분야에서 연구된다. 여기에는 일반적으로 중복 제거 및 전송된 데이터의 오류 수정 또는 감지가 포함된다. == 여담 == 학부 졸업 후 일반 기업에 취직을 하는 것이 아닌 석박사 학위 취득을 위한 대학원[* 슈도코드 수준이 아니라 논문의 절반이 수식으로 도배되어 있는 경우가 태반이다.]에 입학하여 세부 전공으로 '''이론 전산학'''을 선택할 경우 대학 [[미적분학]], [[미분방정식]], [[통계학]], [[확률론]], [[수치해석학]], [[선형대수학]], [[이산수학]], [[정수론]]은 기본실력으로 깔고 가야 고생이 덜하며 심지어 시뮬레이션 영역까지 접근할 경우 [[미분기하학]], [[동역학]], [[유체역학]]이 필요할 수도 있다. == 같이 보기 == * [[국제 과학 올림피아드]]: [[국제정보올림피아드]], 아시아 태평양 정보 올림피아드, [[한국정보올림피아드]] * [[컴퓨터과학]] [[분류:형식과학]] [[분류:수학]] [[분류:이론전산학]][[분류:컴퓨터 공학]]캡챠되돌리기