전산학

분류

자세한 것은 전산학을 참고하라.
문서설명
P = NP P = NP. 전산학의 초대형 떡밥 복잡도 종류 P와 NP의 관계에 대한 문제. 밀레니엄문제 일곱 개 중 하나로, 이게 참이라는 결과가 만에 하나 나온다면 전산학 뿐만 아니라 온갖 엉뚱한 곳에서 폭풍이 몰아칠 것이 분명하다. 물론 거짓이라고 하더라도 드럽게 어려운 문제인 건 사실이다.
알고리즘 Algorithm. 교과서적인 정의를 쓰자면 "유한한 규칙으로 (필요하다면) 무한히 많은 일을 할 수 있는 잘 정의된 명령들의 집합"이지만 사실 우리는 알고리즘이 곧 계산이며 증명임을 알고 있으니 굳이 이런 정의도 필요한지 의문이다.
NP 복잡도 Nondeterministic, Polynomial time. 비결정적튜링기계(NTM)에서 다항시간 안에 풀 수 있는 결정문제의 집합. 함수문제에 대응되는 복잡도는 FNP이다. 가끔씩 NP를 Non-polynomial time으로 착각하는 사람이 있지만 지수시간 안에 풀 수 있는 문제들의 집합은 EXPTIME으로 따로 복잡도가 있다.
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개의 평면에 속했다;…
계산 모델 계산, 또는 그와 동등한 알고리즘을 기술하기 위한 수학적 모델. 알고리즘은 곧 그 알고리즘이 받아 들이는 형식언어를 기술하는 것으로 생각할 수도 있으므로 이는 형식언어론과도 연결되며, 형식 언어의 종류를 기술하는 계산복잡도 이론과도 연결된다.
하이퍼 계산 Hypercomputation. 흔히 계산을 튜링 기계로 할 수 있는 일로 정의하곤 하지만 좀 무리를 해서 그보다 넓은 개념을 생각할 수 있는데 이들을 통틀어 이른다. 하이퍼 계산을 할 수 있는 기계를 하이퍼컴퓨터라 부른다.
쿡-레빈 정리 Cook-Levin theorem. SAT가 NP-완전함을 증명한다. 기본적인 아이디어는 비결정적 튜링 기계(NTM)를 다항시간 안에 동형의 SAT 인스턴스로 변환할 수 있다는 것이다. (변환 과정은 사실 별로 어려운 건 아님) NP의 정의에 따라 모든 NP 문제는 다항시간 안에 문제를 푸는 NTM이 존재할테니 SAT는 NP보다 어렵지 않은데 SAT가 NP인 건 자명하니 결국 NP-완전이 된다.
처치 부호화 Church encoding. Alonzo Church가 제안한, 자연수 같은 일반적인 개념들을 람다 대수로 부호화하는 방법. 람다 대수에서 모든 것은 함수이기 때문에 이 개념들 또한 적절한 고차 함수로 표현되어야 하는데, 다행히도(?) 이 부호화 방법은 어려운 것이 아니다. 단지 귀찮을 뿐. \mathbf{T} = \lambda a.\, \lambda b.\, a \mathbf{F} = \lambda a.\, \lambda b.\, b bb\ then\ elsebthenelse\tau\to\tau\to\tau \mathbf{if} = \lambda x.\, \lambda a.\, \lambda b.\, x\ a\ b \mathbf{and} = \lambda x.\, \lambda y.\, x\ y\ x \mathbf{or} = \lambda x.\, \lambda y.\, x\ x\ y \mathbf{not} = \lambda x.\left( \lambda a.\, \lambda …
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
튜링 완전 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}라고 표현할 수 있다. 문제의 복잡도를 이런 식으로 분류하는 것은 여러 가지로 중요한데 이를테면 어떤 문제는 좀 더 단순한 (추상) 기계만으로 풀 수 있거나 훨씬 효율적으로 풀수 있다거나 하는 특성이 있기 때문이다.…
자료구조 Data structure. 어떻게 자료가 컴퓨터 상에서 표현되며 조작되는지를 결정하는 요소. 웬만한 자료구조들은 자료구조를 다루기 위한 알고리즘과 함께 기술되곤 한다. NIST 자료구조 사전도 참고할 것.

세부 분류


도쿠위키DokuWiki-custom(rev 9085d92e02)을 씁니다.
마지막 수정 2011-05-30 18:25 | 외부 편집기