| '''이론 컴퓨터 과학 {{{#!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. 개요
optimization theory
최적화 이론(optimization theory)은 각종 공학적 최적화를 위한 해를 구하는 방법론이다. 선수과목에는 간단한 대학 미적분학과 선형대수학 지식이 필요하다.
- 조합 최적화 (Combinatorial Optimization)는 주어진 항목들의 조합으로 해가 표현되는 최적화 문제. 계산 복잡도에서 'NP-어려움'이 나오는 비선형계획법 문제들은 최적해를 구하기 힘들다. 구할 수 있다 해도 비용이 많이 든다. 따라서 NP-어려움임을 증명하는 방법, NP-어려움일 경우 해의 품질을 포기하고 근사해를 구하는 기법들을 배우게 된다. 대표적으로 '순회 판매자 문제'가 있다.
- 메타 휴리스틱(meta heuristics) (대학원): 최적해(optimal solution)을 보장하지는 않지만 준최적해(suboptimal solution)을 빠르게 찾는 알고리즘. 유전 알고리즘, 모방 알고리즘, 입자 군집 최적화(particle swarm optimization, PSO), 개미 집단(ant colony) 알고리즘, 타부 탐색(Tabu search), 담금질 기법(simulated annealing), 하모니 탐색(Harmonic search) 등이 있다.
- 함수 최적화(function optimization): 어떤 목적 함수(objective function)가 있을 때, 이 함수를 최대로 하거나 최소로 하는 변수 값을 찾는 최적화 문제. 수리계획법 문제들은 상당수 이쪽 범주에 들어간다.
- 경제학, 산업공학 : 수리경제학에서 최적화를 다룬다. 최적화는 의사결정을 내리는 경제 주체가 가장 바람직하다고 생각하는 상태를 만들기 위해 하는 것이다. 인간의 합리성 등을 가정하고 소비자의 효용극대화, 기업의 이윤극대화의 해를 구한다. 동적 계획법이나 최적제어론 역시 경제학에 응용되고 있다. 레닌그라드 공방전 당시 라도가 호수의 수송 문제에 이런 방법론들이 적용되어 수많은 사람들의 목숨을 구했다.
- 전산학의 한 분야인 컴퓨팅 이론에서 많이 쓰인다. 세부적으로 들어가면 담금질 기법, 선형계획법, 비선형계획법 등 다양한 알고리즘을 활용한다.
2. 세부 내용
- 선형 계획법 (linear programming)
- 심플렉스법(simplex method)
- 비선형 계획법 (nonlinear programming)
- 1차원 최소화(one-dimensional minimization method)
- 비제약 최적화(constrained optimization)
- 제약 최적화(unconstrained optimization)
- 경사하강법(Gradient Descent method)
- 기하급수 계획법(geometric programming)
- 동적 계획법(dynamic programming)
- 정수 계획법(integer programming)
- 확률 계획법(stochastic programming)
- 최적제어와 최적기준 방법(optimal control and optimality criteria)
- 블록함수(Convex)와 오목함수(Concave)