을 참고하라.
| 문서 | 설명 |
| IEEE 754 |
부동소숫점 실수를 표현하는 방법과 적용할 수 있는 연산들을 정의하는 IEEE표준. 최신판은 2008년에 나온 IEEE 754-2008(= ISO/IEC/IEEE 60559:2011)이지만, 그 이전판인 IEEE 754-1985와 비교해서 달라진 점은 없고 몇 가지 포맷 및 연산이 새로 추가되었을 뿐이다. 또한 기존에는 이진법 부동소숫점을 정의하는 IEEE 754(-1985)와 십진법 부동소숫점을 정의하는 IEEE 854-1987이 공존했으나, 2008년 표준은 이진법과 십진법을 함께 포함하고 있다.(-1)^0 \times 2^0 \times 0.0001\;1001\;1001\;1001\;1001\cdots_{(2)}(-1)^{\underline{0}} \times 2^{\underline{11}+(-14)} \times 0.1\;\underline{1001\;1001\;10}01\;1001\cdots_{(2)}
짝수로 반올림 (round to nearest, ties to even… |
| TSP |
Travelling Salesman Problem. 외판원 순회 문제라고 번역하는 것 같지만 귀찮으니 영문 약자로 많이 쓴다.
임의의 무방향 가중 그래프 G = (V, E, w)에 대하여 각 정점을 한 번씩만 지나고 다시 돌아오는 경로 (즉, 사실상 V의 순열) \pi = \langle v_0, \cdots, v_{|V|-1}, v_{|V|} = v_0 \rangle를 생각하자. (편의상 (u,v) \notin E일 경우 w(u,v) = \infty로 가정한다.) 이 경로의 길이 d(\pi) = \Sigma_{i=0}^{|V|-1} w(v_i, v_{i+1})를 정의할 때 \arg\min_\pi d(\pi)는 무엇인가?… |
| SAT |
충족 가능성(satisfiability) 문제. 요컨대 \wedge(AND)랑 \vee(OR)이랑 \neg(NOT)이랑 변수들로 이루어진 수식이 있을 때, 이 수식의 변수들에 적절히 참이나 거짓을 끼워 넣어서 전체 수식을 참으로 만들 수 있는지 묻는다.\mathrm{O}(n)\neg |
| 알고리즘 |
Algorithm. 교과서적인 정의를 쓰자면 "유한한 규칙으로 (필요하다면) 무한히 많은 일을 할 수 있는 잘 정의된 명령들의 집합"이지만 사실 우리는 알고리즘이 곧 계산이며 증명임을 알고 있으니 굳이 이런 정의도 필요한지 의문이다. |
| NP 복잡도 |
Nondeterministic, Polynomial time. 비결정적튜링기계(NTM)에서 다항시간 안에 풀 수 있는 결정문제의 집합. 함수문제에 대응되는 복잡도는 FNP이다. 가끔씩 NP를 Non-polynomial time으로 착각하는 사람이 있지만 지수시간 안에 풀 수 있는 문제들의 집합은 EXPTIME으로 따로 복잡도가 있다. |
| 하이퍼 계산 |
Hypercomputation. 흔히 계산을 튜링 기계로 할 수 있는 일로 정의하곤 하지만 좀 무리를 해서 그보다 넓은 개념을 생각할 수 있는데 이들을 통틀어 이른다. 하이퍼 계산을 할 수 있는 기계를 하이퍼컴퓨터라 부른다. |
| 타입 없는 람다 대수 |
Untyped lambda calculus. 말 그대로 타입이 존재하지 않는 람다 대수. 본래의 람다 대수는 처음부터 타입이 없는 것이었으나 타입이 있는 변종과 구분하기 위하여 이렇게 부르는데, 여기에는 타입 없는 람다 대수가 일반적으로는 타입이 있는 것보다 조금 더 풍부한 표현을 할 수 있다는 이유도 있다. 실제로 타입을 어떻게 넣느냐에 따라서 어떤 변종은 튜링 완전하지 않을 수도 있다. (이를테면 단순히타입된람다대수)… |
| 자료구조 |
Data structure. 어떻게 자료가 컴퓨터 상에서 표현되며 조작되는지를 결정하는 요소. 웬만한 자료구조들은 자료구조를 다루기 위한 알고리즘과 함께 기술되곤 한다.
NIST 자료구조 사전도 참고할 것. |
| 쿡-레빈 정리 |
Cook-Levin theorem. SAT가 NP-완전함을 증명한다.
기본적인 아이디어는 비결정적 튜링 기계(NTM)를 다항시간 안에 동형의 SAT 인스턴스로 변환할 수 있다는 것이다. (변환 과정은 사실 별로 어려운 건 아님) NP의 정의에 따라 모든 NP 문제는 다항시간 안에 문제를 푸는 NTM이 존재할테니 SAT는 NP보다 어렵지 않은데 SAT가 NP인 건 자명하니 결국 NP-완전이 된다. |
| Marching cubes |
컴퓨터그래픽스에서 복셀을 렌더링하기 위한 알고리즘.
이 알고리즘이라는 것이 격자에 정렬되어 있는 복셀들의 유무를 가지고 격자 안쪽에 폴리곤을 그려 넣는 게 다인데 이게 소프트웨어 특허가 걸려 버려서-_- 2005년까지 자유롭게 쓸 수 없었다. 사실은 거의 자명하게 나오는 알고리즘인데도! |
| LCG |
Linear Congruential Generator, 또는 선형 합동 생성기. 유사난수 알고리즘으로 씨수(seed) x_0에 대하여 다음 연산을 반복하여 얻어진다.
x_{n+1} = (ax_n + b) \mod M
연속된 난수끼리 correlation이 꽤 있기 때문에 시뮬레이션 따위로 쓰기는 좀 그렇다. (요즘은 이 용도로 메르센트위스터를 많이 쓴다.) George Marsaglia에 따르면 이 알고리즘으로 n-tuple을 만들어서 n차원 초공간에 점을 찍으면 많아봐야 (n! M)^{1/n}개의 초평면에 위치한다. 그러나 1970년대 악명 높던 RANDU는 고작 15개의 평면에 속했다;… |
| 계산 모델 |
계산, 또는 그와 동등한 알고리즘을 기술하기 위한 수학적 모델. 알고리즘은 곧 그 알고리즘이 받아 들이는 형식언어를 기술하는 것으로 생각할 수도 있으므로 이는 형식언어론과도 연결되며, 형식 언어의 종류를 기술하는 계산복잡도 이론과도 연결된다. |
| 튜링 완전 |
Turing completeness. 계산 모델의 한 분류. 어떤 계산 모델이 튜링 기계로 나타낼 수 있는 프로그램을 모두 나타낼 수 있고 그 역도 성립한다면 그 모델은 튜링 완전, 즉 튜링 기계와 동일한 능력을 가진다. |
| 람다 대수 |
Lambda calculus. 모든 것을 함수로 생각하는 계산 모델. "모든 것"이라는 건 말 그대로 모든 것으로, 심지어 숫자(처치 숫자를 보시라)나 집합 등도 그에 대응하는 함수로 생각하는 최소주의적인 접근을 취한다. 그런데도 이 계산 모델은 튜링 기계와 동치이다! |
| 계산 |
좁은 의미에서는 수식의 단순화로부터, 넓은 의미에서는 잘 정의된 입력을 그에 의존하는 다른 잘 정의된 출력으로 변환하는 모든 과정을 이른다. 전산학의 알고리즘을 계산의 엄밀한 정의로 쓸 수 있을 것이다. |
| 전산학 |
Computer science. "계산"이 정확히 무엇이며 그걸 도대체 어떻게 써 먹을지를 고민하는 학문. 영문을 그대로 직역하여 컴퓨터 과학이라고도 부르지만 이럴 때는 Edsger Dijkstra의 명언을 곱씹는 편이 좋다: |
| 튜링 기계 |
Alan Turing이 고안해낸 가상의 계산 모델. 람다 대수 따위와 동일한 계산 능력을 가지고 있으며 아마 이게 우리가 생각할 수 있는 가장 최고의 계산 모델일 거라는 예측이 있다. (처치튜링명제) |
| NP-완전 |
NP-complete. NP-C라고도 씀.
NP에 속하면서 다른 모든 NP 문제보다 적어도 쉽지 않은 문제들이 속한다. NP에 속하지는 않고 후자임이 알려진 문제는 NP-난해라고 함.
NP-완전한 문제는 P = NP가 증명되지 않는 한 다항 시간 안에 풀 수 없지만 그렇다고 항상 지수 시간이 걸리는 건 아니다. 지수 시간이 걸리는 문제의 집합은 EXPTIME이며 NP = EXPTIME인지는 미해결 문제임. 즉 재수 없으면 다항과 지수 사이에 있는 것들이 걸릴 수도 있...… |
| 문서 | 설명 |
| 복잡도 종류 |
Complexity class. 전산학에서 다루는 문제의 종류를 그 복잡도에 따라 분류한 집합. 알고리즘분석과 계산이론의 주된 주제 중 하나이다.
여기서 말하는 "복잡도"라는 것은 매우 잘 정의된 개념으로, 어떤 문제의 복잡도는 그 문제를 특정한 종류의 계산 모델로 풀 때 필요한 시간이나 공간을 가지고 결정된다. 예를 들어 외판원문제(TSP)의 결정문제 버전은 비결정적튜링기계에서는 입력 크기의 다항식에 비례하는 시간(다항시간) 안에 문제를 풀 수 있다는 게 알려져 있으며, 이를 복잡도 종류를 사용해서 표현하면 \mathrm{TSP} \in \mathbf{NP}라고 표현할 수 있다. 문제의 복잡도를 이런 식으로 분류하는 것은 여러 가지로 중요한데 이를테면 어떤 문제는 좀 더 단순한 (추상) 기계만으로 풀 수 있거나 훨씬 효율적으로 풀수 있다거나 하는 특성이 있기 때문이다.… |
