| '''이론 컴퓨터 과학 {{{#!wiki style="display: inline-block; font-family:Times New Roman, serif;font-style:italic"''' | |||||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | <colbgcolor=#aa3366> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 기계 · 람다 대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | FSM · 푸시다운 · 튜링 머신(폰노이만 구조) · 정규 표현식 · 콘웨이의 생명 게임 | ||||
| 계산 복잡도 이론 | 점근 표기법 · 튜링 기계^고전, 양자, 비결정론적, 병렬 임의접근 기계^ · 알고리즘 · 자료구조 · 알고리즘 패러다임(그리디 알고리즘, 동적 계획법) | ||||
| 정보이론 | 데이터 압축(무손실 압축 포맷 · 손실 압축 포맷) · 채널 코딩(채널 용량) · 알고리즘 정보 이론(AIT) · 양자정보과학 | ||||
| 프로그래밍 언어이론 | 프로그래밍 언어(함수형 언어 · 객체 지향 프로그래밍) · 메타 프로그래밍 · 형식언어 · 유형 이론 · 프로그래밍 언어 의미론 · 파싱 · 컴파일러 이론 | ||||
| 주요 알고리즘 및 자료구조 | |||||
| 기초 | 정렬 알고리즘 · 순서도 · 탐색 알고리즘 | ||||
| 추상적 자료형 및 구현 | 배열^벡터^ · 리스트^연결 리스트^ · 셋(set)^레드-블랙 트리, B-트리^ · 우선순위 큐^힙, 피보나치 힙^ | ||||
| 수학적 최적화 | 조합 최적화 | 외판원 순회 문제 · 담금질 기법 · 유전 알고리즘 · 기계학습 | |||
| 볼록 최적화 | 내부점 방법 · 경사하강법 | ||||
| 선형계획법 | 심플렉스법 | ||||
| 계산 수론 및 암호학 | 밀러-라빈 소수판별법 · Pollard-rho 알고리즘 · 쇼어 알고리즘 · LLL 알고리즘 · 해시(MD5 · 암호화폐 · 사전 공격(레인보우 테이블) · SHA) · 양자 암호 | ||||
| 대칭키 암호화 방식 | 블록 암호 알고리즘(AES · ARIA · LEA · Camellia) · 스트림 암호 알고리즘(RC4) | ||||
| 공개키 암호화 방식 | 공개키 암호 알고리즘(타원 곡선 암호 · RSA) · 신원 기반 암호 알고리즘(SM9) | ||||
| 계산기하학 | 볼록 껍질 · 들로네 삼각분할 및 보로노이 도형^Fortune의 line-sweeping 알고리즘^ · 범위 탐색^vp-tree, R-tree^ · k-NN | ||||
| 그래프 이론 | 탐색^BFS, DFS, 다익스트라 알고리즘, A* 알고리즘^ · 에드몬드-카프 · 크루스칼 알고리즘 · 위상 정렬 · 네트워크 이론 | ||||
| 정리 | |||||
| 정지 문제대각선 논법 · 암달의 법칙 · P-NP 문제미해결 · 콜라츠 추측미해결 | |||||
| 틀:이산수학 · 틀:수학기초론 · 틀:컴퓨터공학 | }}}}}}}}} | ||||
| 이론 컴퓨터 과학 관련 틀 | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
1. 개요
이론 컴퓨터 과학(Theoretical Computer Science) 또는 이론 전산학은 컴퓨터과학과 수학의 한 분야로, 컴퓨터나 계산 과정의 추상적이고 근본적인 원리를 연구하는 학문이다. 컴퓨팅 이론(computing theory)라고도 한다.2. 분류
2.1. 계산 이론(計算理論, theory of computation)
2.1.1. 계산 가능성 이론
계산 가능성 이론(computability theory)은 수학기초론과 이론 컴퓨터 과학의 대표적인 분야로, 계산 모형이 어떠한 계산을 할 수 있는지 다루는 것이다.2.1.1.1. 오토마타 이론
오토마타 이론는 '자동'을 의미하는 그리스 단어인 Αυτόματα에서 유래한 용어로, 계산 능력이 있는 추상 기계와, 그 기계를 이용해서 풀 수 있는 문제들에 대해 학문적으로 접근한 컴퓨터과학 분야를 일컫는 말이다. 오토마타 이론은 컴퓨터 구조 설계, 컴파일러 설계, 파싱, 정형화 등에 있어서 중요한 역할을 담당하는 이론이다.A survey for Modeling and Control of Hybrid System[1]에 따르자면 "오토마톤이란 수학적으로 추상화된 개념으로 쓰일 경우, 자동기계를 기능적인 견지에서 모델화하여, 외부로부터의 자극, 입력신호에 대응하여 내부의 상태가 변화하고, 그리고 신호 또는 동작의 형태로 외부에 출력하는 것으로 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어 맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’ 에 관계되는 것이다." 라고 정의할 수 있다.
2.1.2. 계산 복잡도 이론
계산 복잡도(computational complexity) 이론은, 계산 모형이 각 알고리즘에 대해 갖는 계산 복잡도를 분류하는 분야이다. 계산 가능성 이론은, 그 문제를 컴퓨터가 다룰 수 있는지 평가하지만, 그 결과가 얼마나 빠르게 나올지는 알 수 없다.[2] 계산 복잡도 이론은 이러한 문제를 현실에서 어느 정도의 노력을 들여 풀 수 있는지, 얼마나 간단히 풀 수 있는지 평가 할 수 있도록 한다.2.2. 컴퓨터 알고리즘 성능 분석법
시간복잡도와 공간복잡도 계산 방법이 있다.- 알고리즘 문서 참조
2.2.1. P-NP 문제
2.3. 수학적 최적화
제약 조건 내에서 최댓값 및 최소값을 계산하는 분야로, 이론 컴퓨터 과학의 중요한 분과이다. 최적화 이론이라고도 한다. 일반적으로 이를 푸는 것(조합 최적화)은 알려진 다항 시간 해법이 없어 근사 해법을 구하거나 인공지능, 담금질 기법, 선형계획법, 비선형계획법 등 다양한 기법을 도입한다. 볼록집합 등 다항 시간 해법이 존재하는 경우가 있어, 이러한 경우 별도의 분야가 있다.2.4. 이산수학, 수치해석학
이산수학 외에도 이산적인 세계외에 연속적인 세계에서의 공학적 이슈도 다룰 수 있는 수치해석학 도 컴퓨팅 이론의 한 분류이다. 사실상 수학 공식을 컴퓨터에서 표현하고 구동시키면 컴퓨터 알고리즘이 되는 것이다.2.5. 정보이론
정보이론(information theory)은 디지털 정보의 정량화, 저장, 그리고 의사소통을 연구하는 과학적 연구이다.2.6. 부호이론 (coding theory)
부호 이론은 부호의 속성과 특정 응용 프로그램에 대한 부호의 적합성에 대한 연구이다. 부호는 데이터 압축, 암호화, 오류 감지 및 수정, 데이터 전송 및 데이터 스토리지에 사용된다. 부호는 효율적이고 신뢰할 수 있는 데이터 전송 방법을 설계하기 위해 정보이론, 전기공학, 수학, 언어학 및 컴퓨터과학과 같은 다양한 과학 분야에서 연구된다. 여기에는 일반적으로 중복 제거 및 전송된 데이터의 오류 수정 또는 감지가 포함된다.3. 여담
학부 졸업 후 일반 기업에 취직을 하는 것이 아닌 석박사 학위 취득을 위한 대학원[3]에 입학하여 세부 전공으로 이론 전산학을 선택할 경우 대학 미적분학, 미분방정식, 통계학, 확률론, 수치해석학, 선형대수학, 이산수학, 정수론은 기본실력으로 깔고 가야 고생이 덜하며 심지어 시뮬레이션 영역까지 접근할 경우 미분기하학, 동역학, 유체역학이 필요할 수도 있다.4. 같이 보기
- 국제 과학 올림피아드: 국제정보올림피아드, 아시아 태평양 정보 올림피아드, 한국정보올림피아드
- 컴퓨터과학
[1] 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. 의 번역본[2] 체스나 바둑같은 2인 유한 턴제 확정 완전 정보 게임의 경우 체르멜로 정리에 의해 필승법이 항상 있고, 경우의 수가 유한하므로 당연히 계산 가능하지만, 판의 크기를 n×n로 일반화하면 NP-Hard임이 알려져 있다.[3] 슈도코드 수준이 아니라 논문의 절반이 수식으로 도배되어 있는 경우가 태반이다.