| '''이론 컴퓨터 과학 {{{#!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=#a36> 이론 | ||||
| 기본 대상 | 수학기초론{수리논리학(논리 연산) · 계산 가능성 이론 · 범주론 · 집합론} · 이산수학(그래프 이론) · 수치해석학 · 확률론 및 통계학 · 선형대수학 | ||||
| 다루는 대상과 주요 토픽 | |||||
| 계산 가능성 이론 | 재귀함수 · 튜링 머신 · 람다대수 · 처치-튜링 명제 · 바쁜 비버 | ||||
| 오토마타 이론 | 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. 전산수학 분야
2.1.1. 이산수학, 수치해석학
이산수학 외에도 이산적인 세계외에 연속적인 세계에서의 공학적 이슈도 다룰 수 있는 수치해석학 도 컴퓨팅 이론의 한 분류이다. 사실상 수학 공식을 컴퓨터에서 표현하고 구동시키면 컴퓨터 알고리즘이 되는 것이다.2.1.2. 전산논리학
전산논리학이란, 기호논리학에 기반해 이를 컴퓨터 언어로 표현한 후 계산할 수 있도록 하는 분야이다.2.1.3. 그래프 이론
2.2. 계산 이론(計算理論, theory of computation)
2.2.1. 계산 가능성 이론
계산 가능성 이론(computability theory)은 수학기초론과 이론 컴퓨터 과학의 대표적인 분야로, 계산 모형이 어떠한 계산을 할 수 있는지 다루는 것이다.2.2.2. 오토마타 이론
오토마타 이론는 '자동'을 의미하는 그리스 단어인 Αυτόματα에서 유래한 용어로, 계산 능력이 있는 추상 기계와, 그 기계를 이용해서 풀 수 있는 문제들에 대해 학문적으로 접근한 컴퓨터과학 분야를 일컫는 말이다. 오토마타 이론은 컴퓨터 구조 설계, 컴파일러 설계, 파싱, 정형화 등에 있어서 중요한 역할을 담당하는 이론이다.A survey for Modeling and Control of Hybrid System[1]에 따르자면 "오토마톤이란 수학적으로 추상화된 개념으로 쓰일 경우, 자동기계를 기능적인 견지에서 모델화하여, 외부로부터의 자극, 입력신호에 대응하여 내부의 상태가 변화하고, 그리고 신호 또는 동작의 형태로 외부에 출력하는 것으로 ‘대상의 어떤 기능에 주목하여, 입력과 내부 출력 각 신호의 상호관계를 수학모델로 옮기고, 이 모델을 수학적으로 고찰 ·결론을 유도한다. 그리고 이 유도된 결론을 다시 원래의 대상에 꼭 들어 맞춰서 해석한다고 하는 일련의 과정의 일부 또는 전부’ 에 관계되는 것이다." 라고 정의할 수 있다.
2.2.2.1. 형식 언어 이론
형식 언어란 알파벳을 기반으로 형식 문법이라는 규칙에 따라 조합된 언어적 집합을 말한다. 형식 언어 이론은 이러한 형식 언어를 수학적으로 분석하여 통사적 패턴을 연구한다.2.2.3. 계산 복잡도 이론
계산 복잡도(computational complexity) 이론은, 계산 모형이 각 알고리즘에 대해 갖는 계산 복잡도를 분류하는 분야이다. 계산 가능성 이론은, 그 문제를 컴퓨터가 다룰 수 있는지 평가하지만, 그 결과가 얼마나 빠르게 나올지는 알 수 없다.[2] 계산 복잡도 이론은 이러한 문제를 현실에서 어느 정도의 노력을 들여 풀 수 있는지, 얼마나 간단히 풀 수 있는지 평가 할 수 있도록 한다.2.3. 알고리즘/자료구조
기초적인 알고리즘 및 자료구조들이 이에 해당한다.2.3.1. 컴퓨터 알고리즘 복잡도
시간복잡도와 공간복잡도 계산 방법이 있다.- 알고리즘 문서 참조
2.3.1.1. P-NP 문제
2.3.2. 수학적 최적화
제약 조건 내에서 최댓값 및 최소값을 계산하는 분야로, 이론 컴퓨터 과학의 중요한 분과이다. 최적화 이론이라고도 한다. 일반적으로 이를 푸는 것(조합 최적화)은 알려진 다항 시간 해법이 없어 근사 해법을 구하거나 인공지능, 담금질 기법, 선형계획법, 비선형계획법 등 다양한 기법을 도입한다. 볼록집합 등 다항 시간 해법이 존재하는 경우가 있어, 이러한 경우 별도의 분야가 있다.2.3.2.1. 기계학습
인공지능의 일종이지만, 이론적으로는 수학적 최적화에 기반해 기계에게 데이터로부터 학습할 수 있도록 하는 가장 효율적인 알고리즘을 개발하는 분야이다. 패턴 인식에 중점을 둔다.2.3.3. 계산기하학
고전적인 기하학적 문제를 컴퓨터로 표현하고 계산하는 알고리즘을 연구하는 분야부터, 3차원 기하학적 공간이나 모양을 그래픽스 상에 표현하는 것을 연구하는 CAD나 그래픽스 관련 응용 분야까지 존재한다. GIS와도 연관이 있다.2.3.4. 컴퓨터 대수
컴퓨터로 정수, 실수 등을 정확히 표현하고 계산하기 위한 방법 및 알고리즘을 연구하는 분야. 특정 수식에 여러 변수를 추가하고 계산하여 단순히 값을 도출하기보다 계산된 풀이의 표현을 도출하는데 목적이 있다.[3]2.3.5. 계산수론/암호학
알고리즘 수론이라고도 한다. 컴퓨터를 이용해 정수론과 대수기하학의 문제를 해결하기 위한 알고리즘 연구 분야이다. 암호학과 밀접한 연관이 있다.2.4. 정보이론
정보이론(information theory)은 디지털 정보의 정량화, 저장, 그리고 의사소통을 연구하는 과학적 연구이다.2.5. 네트워크 이론
이산수학의 그래프 이론을 응용해 현실 시스템에서의 임의의 연결망들에 대해 연구하는 분야이다.2.6. 부호이론 (coding theory)
부호 이론은 부호의 속성과 특정 응용 프로그램에 대한 부호의 적합성에 대한 연구이다. 부호는 데이터 압축, 암호화, 오류 감지 및 수정, 데이터 전송 및 데이터 스토리지에 사용된다. 부호는 효율적이고 신뢰할 수 있는 데이터 전송 방법을 설계하기 위해 정보이론, 전기공학, 수학, 언어학 및 컴퓨터과학과 같은 다양한 과학 분야에서 연구된다. 여기에는 일반적으로 중복 제거 및 전송된 데이터의 오류 수정 또는 감지가 포함된다.2.7. 프로그래밍 언어론
전산언어학 등에 기반해 프로그래밍 언어의 구조와 효율적인 설계, 구현과 분석을 연구하며, 프로그래밍 언어가 같은 의미론적인 부분을 수학적으로 분석하기도 한다.2.8. 병렬계산/분산계산
병렬 컴퓨팅과 분산 컴퓨팅의 기본이 되는 분야이다.2.9. 계산학습이론
기계학습의 이론적 방법론을 다루는 분야로, 기계학습의 오류 최소화, 성능 향상 뿐 아니라 알고리즘과 결합해 시간복잡도(즉 학습에 걸리는 시간)를 측정함으로서 학습에 성공했는지 실패했는지를 판정하는 등의 일을 한다. 또 컴퓨터가 제한된 여러 정보를 바탕으로 하나의 사실을 어떻게 추론해내는지에 대한 통계학에 기반한 알고리즘을 개발한다.3. 여담
학부 졸업 후 일반 기업에 취직을 하는 것이 아닌 석박사 학위 취득을 위한 대학원[4]에 입학하여 세부 전공으로 이론 전산학을 선택할 경우 대학 미적분학, 미분방정식, 통계학, 확률론, 수치해석학, 선형대수학, 이산수학, 정수론은 기본실력으로 깔고 가야 고생이 덜하며 심지어 시뮬레이션 영역까지 접근할 경우 미분기하학, 동역학, 유체역학이 필요할 수도 있다.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] 1990년대 이후로 쓰여진 계산이론물리 논문들에서 10줄이상의 무지막지하게 긴 수식을 본 경우, 이 분야에서 쓰는 프로그램을 통하여 도출한 수식일 가능성이 높다.[4] 슈도코드 수준이 아니라 논문의 절반이 수식으로 도배되어 있는 경우가 태반이다.