2.1 가변길이 문자열
고정길이 문자열과는 달리 문자열의 길이가 가변이다. 데이터 타입은 varchar(m) 형식이며, m은 1~255까지이다.
2.2 가중치(weight)
그래프(graph)에서 정점(u)과 정점(v)을 연결하는 변은 속성으로서 수치를 갖는 경우가 있다. 이 수치를 변의 가중치(weight)라 부른다.(그래프의 대상으로 하는 문제에 따라서 비용(cost), 길이로 부르는 경우도 있다.) 예를 들어 교통망을 나타내는 그래프에서는 역과 역 사이의 소요시간을 변의 가중치로 다룬다.
2.3 가지(branch edge)
데이터 구조인 트리(tree)와 그래프(graph)에서 정점과 정점의 사이를 연결해주는 선을 가지(branch edge, arc, 변)라 한다. 그래프에서는 일반적으로 ‘변’이라 부른다.
2.4 가지치기(tree pruning)
트리를 이용하여 경우의 수에 대한 어떠한 문제를 풀 경우, 모든 가능한 경우에 대해 탐색해보는 방법이 아닌 트리의 일반적인 탐색법, 즉, 깊이 우선 탐색의 요령으로 조사한다. 만약 도중에서 더 이상 진행해도 소용없다는(해가 얻어질 수 없다는)것이 밝혀지면, 그 이하의 부분 트리는 조사하지 않는다. 이것을 트리의 가지치기(tree pruning)라고 한다.
이 방법은 모든 경우의 탐색보다 훨씬 능률적으로 우수하다.
2.5 가지친(pruned) 결정 트리
뿌리마디에서 일광성 있게 순서대로 결정을 해서 모든 잎마디에 도달할 수 있는 결정트리를 가지친 결정트리라고 한다.
알고리즘은 비용과 밀접한 연관이 있다. 그렇기에 만약 어떤 알고리즘에 불필요한 요소가 포함되어 있거나 현재의 알고리즘이 간략하게 될 수 있다면, 간략화에 의해 훨씬 이상적인 알고리즘을 추구한다. 예를 들어 일반적으로 결정성 오토마타의 경우 주어진 입력에 대하여 상태의 수가 최소의 것을 구하는 알고리즘이 존재한다. 이러한 경우 보통 ‘결정성 오토마타의 간략화’라 한다.
2.7 간접 힙(indirect heap)
힙에서, 힙을 나타내는 배열 heap에 정점의 번호를 넣는다. 이 번호에서 각 정점의 필드를 간접적으로 참조하고, 그 값에 따라 힙의 부자관계를 정한다. 이처럼 대소 관계를 정하는 값을 힙에 넣지 않고 값을 지시하는 첨자나 포인터만을 힙에 넣는 기법을 간접 힙(indirect heap)이라 한다. 간접 힙처럼 데이터를 간접적으로 사용하는 방법은 데이터 구조의 취급을 간단히 하는 것 외에 계산 속도를 향상시키는 효과가 있기도 한다.
2.8 강연결 그래프
임의의 두 정점u,v에 대하여 u에서 v에 이르는 길과 v에서 u에 이르는 길의 양방이 존재하는 그래프이다.
2.9 강연결 성분
부분 그래프 중에서 강연결이지만 그것에 정점을 추가하면 더 이상 강연결이 아닌 것을 강연결 성분이라 부른다. 이 정의는 2중 연결 성분인 경우와 같다. 일반적으로 강연결이 아닌 그래프에서도 부분적으로 강연결 성분으로 분해할 수 있다. 이때, 원래의 그래프의 각 정점은 어느 하나의 강연결 성분에 속한다.
방향 그래프의 각 정점에서 임의의 정점에 이르는 길이 존재할 때 이 방향그래프를 강연결이라고 한다. 바꾸어 말하면, 임의의 두 정점u,v에 대하여 u에서 v에 이르는 길과 v에서 u에 이르는 길의 양방이 존재하는 것이 강연결 그래프의 조건이다.
2.11 거의 완전한 이진 트리(nearly complete binary tree)
값이 d-1까지 완전한(꽉 찬) 이진 트리를 거의 완전한 이진 트리라고 한다. 실질적으로 완전한 이진 트리는 모두 거의 완전하지만, 거의 완전한 이진 트리라고 해서 모두 실질적으로 완전하지는 않다.
2.12 검색문제(searching problem)
검색문제는 키(key) 필드의 값을 가지고 전체 레코드를 찾아내는 것이다.
2.13 검색시간(search time)
키를 찾기 위해 프로시저 search가 수행한 비교횟수를 검색시간이라고 한다.
게임트리라 하는 것은 장기나 바둑 같은 게임을 실제로 두 사람이 만나서 하는 것이 아닌 컴퓨터와 한 명의 사람이 하는 완전정보 게임을 말한다. 완전정보 게임이라는 것은 모든 정보가 반상에 나타나 있기 때문에 확률 등의 미확정 요소가 끼어들 여지가 없이 예측 가능한 다음 수를 놓을 수 있는 게임에만 적용된다.
게임에서 다음 수를 결정하는 방법은 게임의 트리 상에서 가능한 모든 경우를 탐색하는 일이며, 이것으로 가능한 수를 생각하고 또 몇 수 앞을 계산한 뒤 그 중에서 가장 최선이라고 생각되는 것을 선택한다.
이 트리를 탐색하는 방법은 깊이 우선 탐색으로 시행되며, 아직까지는 단순한 알고리즘만 구현 가능한 상태이다.
2.15 결정트리(decision tree)
판정조작(비교도 그 일종)에 의해 분할이 생기는 모습을 트리의 형으로 쓴 것을 결정트리(decision tree)라 한다.
2.16 결정불능(undecidable)
알고리즘을 개발하는 데 있어서 쉬운문제와 어려운 문제로 나뉜다. 쉬운문제는 효율이 좋은 알고리즘이 존재하는 문제이고, 어려운 문제는 존재하지 않은 문제를 일컫는다. 어려운 문제는 그 정도에 따라 4분류로 나뉘는데, 그 중에서 난이도 최고의 단계가 ‘결정불능(undecidable)’이다. 문제를 해결하는 알고리즘이 존재하지 않는다는 사실이 이미 증명된 이 결정불능 단계의 문제는 어떤 알고리즘을 개발한다해도 풀 수 없는 문제이다. 결정불능문제 중에서 가장 잘 알려진 것은 정지문제이다.
2.17 결정성(결정적인) 알고리즘(deterministic algorithm)
주어진 알고리즘에 입력 데이터를 집어넣으면 어떤 순서와 동작들에 의해 알고리즘이 수행되는지가 뚜렷하게 결정되는 알고리즘을 우리는 결정적인 알고리즘(deterministic algorithm)이라고 한다.
2.18 결정성 오토마타(deterministic automaton)
오토마타에서 각 상태로부터 나가는 몇 개의 화살표에 할당되어진 문자가 전부 다를 때, 이것은 어느 문자를 입력해도 다음 상태가 한 가지로 결정되는 것을 의미한다. 이러한 오토마타를 결정성 오토마타(deterministic automaton)라고 부른다.
2.19 결정 트리(decision tree)
각 마디에서 다음에 어떤 마디를 방문해야 하는지 결정해야 하므로 이 트리를 결정 트리(decision tree)라고 한다.
2.20 경로(path)
방향그래프에서 경로는 각 정점에서 다음 정점을 잇는 이음선이 존재하는 일련의 정점들이다.
그래프에서 한 시작 정점에서 끝 정점으로 가는 경로를 구할 경우, 그 경로를 구성하는 각 변의 가중치를 합한 것을 그 경로의 길이라 부른다.
트리의 높이가 높을수록 효율이 낮은 알고리즘이 된다. 이를 해결하기 위해 개발된 알고리즘이 동치류 알고리즘인데, 이 방법은 트리의 근을 찾는 조작 도중에 서서히 트리를 바꾸기로 한다. 이에 따라 각 정점에서 근까지의 거리가 평균적으로 짧아지고, 그 다음부터 그룹찾기가 빨라진다. 이 조작을 경로의 단축이라 한다.
2.23 경사진 트리(skewed tree)
노드들이 한 쪽 방향으로 몰려있는 트리를 말한다.
2.24 계산복잡도(computational complexity)
일반적으로 한 개의 문제에는 여러 가지의 알고리즘이 성립 가능하다. 이와 같은 경우에 알고리즘의 좋고 나쁨을 평가하는 기준으로서 가장 중요한 것은 각각의 알고리즘이 해답을 내기까지 어느 정도의 계산시간을 필요로 할 것인가이다. 이것을 그 알고리즘의 시간계산 또는 계산의 복잡도라 한다.
2.25 고밀도 그래프(dense graph)
연결 그래프에서 이음선의 개수가 정점의 개수의 범위에 대한 값의 상한과 가까운 그래프를 나태내면 고밀도 그래프라고 한다.
2.26 공간 복잡도(space complexity)
알고리즘을 수행시키기 위해서는 기억장치를 얼마나 많이 사용하는지를 말한다.
2.27 공개키 암호체계(public-key cryptosystem)
허용 가능한 메시지, 참여자의 집합(각 참여자는 모두 공개키와 비밀키를 가지고 있음), 참여자 간에 메시지를 주고 받을 수 있는 네트워크로 구성되어 있다.
2.28 공유된 주소 저장장소 구조(shared-address-space architecture)
공유된 주소 저장장소 구조에서는 공유된 주소 저장장소에 읽기/써넣기 접근을 모든 프로세서에 하드웨어로 허용한다.
2.29 교환정렬(bubble sort)
주어진 데이터를 크기순서로 정렬할 때, 두 개의 인접한 데이터가 순서대로 되어있지 않으면서 위치를 바꾸어주는 정렬방식이다. 버블정렬이라고도 한다.
2.30 균일하지 않은 메모리 접근(nonuniform memory access: NUMA)
예를 들어 어떤 구조가 다른 구조에 비해 독자적이지 않을 때 즉, 각 프로세서는 다른 프로세서에 속한 메모리에 접근할 수 있으나 다른 프로세서에 속한 메모리보다 자신에 속한 메모리에 더 빠르게 접근할 수 있을 때 만약 프로세서가 대부분 자신에 속한 메모리만 접근한다면, 수행성능은 좋을 수밖에 없다. 이러한 컴퓨터를 균일하지 않은 메모리 접근 컴퓨터라고 한다.
2.31 균일한 메모리 접근(uniform memory access: UMA)
공유된 주소 저장장소 구조에서는 공유된 주소 저장장소에 읽기/써넣기 접근을 모든 프로세서에 하드웨어로 허용한다. 프로세서는 공유된 주소 저장장소에 있는 데이터를 수정함으로써 서로 통신한다. 각 프로세서가 메모리의 워드(word)에 접근하는 데 걸리는 시간이 모두 같은 공유된 주소 저장장소 구조를 보여주는 컴퓨터를 균일한 메모리 접근 컴퓨터(UMA)라 한다.
2.32 균형유지 프로그램(balanging program)
이미 만들어진 이진검색 트리를 입력으로 받아서 같은 키로 구성된 균형 잡힌 이진검색 트리를 출력으로 내주는 프로그램을 일컫는다.
2.33 균형이 잡힌 트리(balanced tree)
모든 노드들에 대한 왼쪽 서브트리의 높이가 같거나 혹은 그 차이가 기껏해야 1인 트리를 말한다. 여기에는 이진트리인 AVL 트리, B 트리 등이 있다.
2.34 그래프(graph)
그래프는 꼭짓점(vertex)과 변(edge)으로 이루어져 있다. 흔히 그래프를 꼭짓점의 집합과 두 꼭짓점을 잇는 변의 집합의 순서쌍으로 정의한다. (예를 들어, 꼭짓점의 집합 V와 변의 집합 E를 포함하는 그래프 G를 (V,E)로 표현한다.) 변에 방향을 허용하느냐 마느냐에 따라서 방향이 있는 그래프, 혹은 방향이 없는 그래프로 나뉜다.
2.35 그래프 동형성 문제(Graph Isomorphic problem)
두 개의(방향 또는 비방향) 그래프 G = (V,E)와 G' = (V',E')는 다음 조건이 만족하면 동형이라고 한다.
2.36 그래프 채색문제(Graph Coloring Problem)
m개 색깔의 채색문제는 최대로 다른 서로 다른 색깔을 사용하여 그래프의 서로 이웃하는 어떠한 꼭짓점도 같은 색으로 채색하지 않으면서 방향이 없는 그래프의 꼭짓점들을 채색하는 모든 방법들을 찾는 문제이다.
2.37 근사알고리즘(approximation algorithm)
NP-hard로 알려진 최적화 문제는 정확한 해답을 구하는 것이 현실적으로 어렵기 이러한 경우 구하는 답이 반드시 최적 해는 아니더라도 최적 해에 근사한 것이면 우리는 만족스러운 해답으로 간주한다. 이와 같이 최적 해에 가까운 해답을 우리는 근사해라고 하며 근사 해를 구하는 알고리즘을 근사 알고리즘이라고 한다.
2.38 기수정렬(radix sort)
이 방법은 컴퓨터가 생겨나기 이전부터 사용되었던 방법으로, 과거의 카드 정렬기에서 사용하던 방법이었다. 키를 정렬하는 데 사용한 정보가 특정 기수이기 때문에 기수정렬이라고 한다.
2.40 깊이 우선 탐색
그래프의 탐색법 중 가장 응용 범위가 넓은 것으로, 하나의 길을 선택하여 갈 수 있는 곳까지 가서 진행할 수 없으면 되돌아가서 다른 길을 선택하는 탐색법이다. 말하자면, 한번 길을 선택하면 그 길에서 더 이상 갈 수 없는 곳이 나올 때까지 깊이 들어가는 방법이다.
2.41 깊이(depth)
트리에서 뿌리에서 어느 정점에 도달하기까지 통하는 가지의 수를 그 정점의 깊이(depth)라 한다.
2.42 꼬리 재귀 호출의 제거
재귀호출의 함수에서 함수를 호출할 때 호출된 곳에서 할 일은 아무것도 없고, 단지 호출한 장소로 돌아올 뿐인 경우에는 재귀 호출을 사용하지 않고 반복 형태로 고쳐 쓰는 것이 가능하다. 이것을 꼬리 재귀 호출의 제거라 한다. 이것은 프로그램을 고속화하는 테크닉의 하나이다.
스택에 관련된 용어이다. 스택에서, 스택으로부터 값을 꺼내는 조작을 팝업, 끄집어내기 또는 간단히 팝이라 한다.
3 ≪ ㄴ ≫
==== 내림수(floor)
실수 x보다 작거나 같은 가장 큰 정수를 나타낼 때, 그 정수를 ⌊x⌋라 표시하고 ⌊x⌋는 x의 내림수라 한다.
3.1 내부검색(internal search)
검색을 수행하기 위한 키가 모두 동시에 메모리 안에 있는 경우의 검색을 내부검색이라 한다.
3.2 내부마디(internal node)
최소한 하나의 자식마디를 가진 마디를 일컫는다.
3.3 너비우선검색(breadth-first search)
너비우선검색은 무방향 그래프 G(V, E)에서 시작하며 정점 V를 방문한 후 V에 인접한 아직 방문하지 않은 모든 정점들을 방문한 뒤, 다시 이 정점에 인접하면서 방문하지 않은 모든 정점들에 대해 너비 우선 검색을 반복적으로 수행한다. 즉, 깊이가 아닌 왼쪽에서 오른쪽으로의 진행순서로 인접한 노드를 먼저 방문하는 방법이다.
4.1 다익스트라 알고리즘
탐욕적인 방법을 사용하여 단일출발점 최단경로 문제를 푸는 알고리즘을 일컫는다.
4.2 다차시간 다일 축소가능(polynomial-time many-one reducible)
결정문제 A를 결정문제 B로 변환하는 다차시간 변환 알고리즘이 존재하면, 문제 A는 문제 B를 다차시간 다일 축소가능하다(일반적으로 문제 A는 문제 B로 축소된다고 한다).
기호로는 A∝B로 표현한다.
4.3 다차시간 비결정적 알고리즘(polynomial-time nondeterministic algorithm)
검증단계가 다차시간 알고리즘인 비결정적 알고리즘을 말한다.
4.4 다차시간 알고리즘(polynomial-time algorithm)
다차시간 알고리즘은 최악의 경우 시간복잡도의 상한이 입력 크기의 다차함수가 되는 알고리즘이다. 즉, n이 입력크기이면, 다음을 만족하는 다항식 p(n)이 존재한다.
W(n)∊O(p(n))
4.5 다차시간 튜링 축소가능(polynomial-time turning reducible)
문제 B를 푸는 가상적인 다차시간 알고리즘을 사용하여 문제 A를 다차시간에 풀 수 있다면, 문제 A는 문제 B로 다차시간 튜링 축소가능하다(보통 “A는 B로 튜링 축소된다.”라고 한다)라고 한다.
4.6 단계(step)
단계는 기계적 비교 또는 지정 한 번, 또는 분석을 기계독립적으로 유지하기 위한 비티의 비교나 지정 한 번과 같다고 여긴다.
4.7 단순경로(simple path)
그래프에서 같은 정점을 두 번 거치지 않는 경로를 단순경로라고 한다.
4.8 단순순환경로(simple cycle)
비방향 그래프에서 한 정점에서 출발하여 그 정점으로 되돌아가는 경로(이 경로상에는 최고한 정점이 3개 포함되어 있고, 거쳐 가는 중간 정점들은 모두 서로 다르다)를 단순순환경로라고 한다.
4.9 단위연산(basic operation)
배열 안에 있는 아이템의 개수를 입력크기로 사용하고, 이러한 입력크기를 구한 후, 어떤 명령문이나 명령문 군을 선정하여 알고리즘이 수행한 총 작업의 양을 이 명령문이나 명령문 군을 수행한 횟수에 대략적으로 비례하도록 한다. 이 명령문이나 명령문 군을 알고리즘의 단위연산이라고 한다.
4.10 대수(logarithm)
대수란 알고리즘 분석에서 가장 많이 사용되는 수학 도구 중의 하나로 우리가 알고 있는 로그(log)를 말한다. 시간복잡도를 구할 때 자주 이용된다.
4.11 데이터 병렬 프로그램(data paralled program)
병렬컴퓨터의 한 종류인 SIMD(단일명령흐름, 다중데이터 흐름) 컴퓨터는 같은 명령을 여러 가지 다른 데이터로 실행하는 프로그램에 적당하다. 이러한 프로그램을 데이터 병렬 프로그램이라고 한다.
4.12 데이터 압축(datacompression)
보조저장장치의 용량이 계속 커지고 가격이 계속 싸지고 있음에도 불구하고, 필요한 저장용량도 따라서 증가하기 때문에 저장장치의 공간은 계속 더 필요하게 된다. 그러므로 데이터가 저장되어 있는 파일을 가능한 한 효율적으로 저장하는 방법을 찾는 것이 바람직하다. 데이터 압축문제는 데이터 파일을 코드화하는 효율적인 방법을 찾는 것이다.
4.13 동적 상호연결 네트워크(dynamic interconnection network)
동적 상호연결 네트워크는 프로세서가 여러개의 스위치를 통하여 메모리에 연결되어 있는 것을 말한다.
4.14 동적검색(dynamic searching)
동적검색은 레코드가 추가 삭제되는 빈도수가 높아서, 한번에 모든 레코드를 파일에 저장하지 않는다. 따라서 구조는 배열구조를 사용하지 않으며, 비행예약 시스템 같은 검색이 동적검색이 요구되는 대표적인 경우이다.
4.15 동적계획법(dynamic programming)
동적계획법은 문제의 사례를 더 작은 사례로 분할한다는 점에서 분할정복법과 비슷하지만, 이 방법은 작은 사례를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 대신 그 저장한 결과를 이용한다. 따라서 이 방법은 상향식 접근 방법이다.
4.16 동형(isomorphic)
두 개의 그래프 G=(V,E)와 G'=(V',E')가 있을 때, V에 속하는 모든 노드 v1,v2에 대해서 이음선(u,v)가 E에 있고, 이음선 (f(u),f(v))가 E'에 있는 V에서 V'로 가는 일대일 함수 f가 존재할 때 두 그래프는 동형이라고 한다.
되추적은 막힌 것으로 이르는 마디라는 사실을 알면, 그 마디의 검색을 중단하고 그 마디의 부모마디로 돌아가서(“되추적”) 다음 자식마디의 검색을 계속하는 프로시저이다.
되추적 기술은 어떤 집합에서 어떤 기준을 만족하면서 그 집합에 속한 대상의 순서를 선택하는 문제를 푸는 데 사용하는 기술이다. 되추적의 전형적인 예는 서양장기의 n-여왕말 문제이다.
5.1 로피탈 정리
f(x)와 g(x)가 각각 미분계수 f'(x)와 g'(x)로 미분가능하고, 다음이 성립하면,
lim f(x) = lim g(x) = ∞
x→∞ x→∞
다음 등식은 우변의 극한이 존재하면 항상 성립한다.
lim f(x)/g(x) = lim f'(x)/g'(x)
x→∞ x→∞
6.1 마감시간 있는 스케줄 짜기
이 스케줄 짜기 문제에서는 각 작업을 끝내는 데 1의 단위시간이 걸리고, 마감시간과 이익이 할당되어 있다. 작업이 마감시간 전이나 마감시간에 시작된다면, 그 이익을 얻게 된다. 목표는 총 이익이 최대가 되게 작업의 스케줄을 짜는 것이다. 모든 작업을 스케줄에 포함시켜야 되는 것은 아니다. 작업이 마감시간 후로 짜여진 스케줄은 고려할 필요가 없다.
6.2 마디(node)
그래프의 용어에서 정점이라 불리는 것과 같은 의미의 용어로 마디는 상태공간 트리에서 사용한다. 이음선이 연결해주는 정점을 일컫는다.
6.3 마디거리(node distance)
뿌리마디에서 어떤 마디까지의 경로 상에 있는 마디의 총 개수를 그 마디까지의 마디거리라 한다.
6.4 마디의 깊이(depth)
뿌리에서 마디로 가는 유일한 경로 상에 있는 이음선의 개수이다.
6.5 마디의 수준(level)
=(동의어) 마디의 깊이
6.6 메시지 전달 구조(message-passing architecture)
메시지 전달 구조에서 각 프로세서는 자신만이 접근할 수 있는 독자 메모리를 가지고 있다. 데이터를 수정하는 대신 메시지를 전달하여 프로세서는 다른 프로세서와 통신을 한다. 메시지 전달 컴퓨터에서는 각 프로세서가 직접 다른 프로세서에 메시지를 보낼 수 있도록 연결되어 있다.
6.7 모든 경우 시간 복잡도(every-case time complexity)
입력 값에 상관없이 항상 단위연산의 횟수가 같을 경우 T(n)은 입력크기 n에 대하여 알고리즘이 단위연산을 수행하는 횟수로 정의된다. 이럴 때의 T(n)을 알고리즘의 모든 경우 시간복잡도라 한다.
6.8 모순 유도 증명법(proof by contradiction)
알고리즘의 시간복잡도의 분석에서 이를 증명하기 위해 사용하는 증명법으로, 이 증명법은 어떤 것을 사실이라고 가정하고 그 것으로부터 사실이 아닌 결과를 유도한다. 즉, 유도된 결과는 사실이라고 가정했던 것과는 모순이 된다. 따라서 애초에 가정했던 것이 사실일 수 없다고 결론짓는다.
6.9 몬테칼로 알고리즘(monte carlo algorithm)
몬테칼로 알고리즘은 확률적 알고리즘으로 표본공간의 무작위 표본의 평균치를 가지고 표본공간에서 정의된 무작위 변수의 기대치를 추정한다. 추정치가 실제 기대치에 근접하리라는 보장은 없지만, 알고리즘을 이용하는 시간이 증가할수록 실제 기대치에 근접할 확률은 증가한다.
무작위성은 절차를 포함한다. 직관적으로 무작위 절차란 다음을 의미한다. 첫째, 그 절차는 반드시 임의로 긴 일련의 결과를 생성할 수 있어야 한다. 둘째, 결과는 반드시 예측 불가능해야 한다. 이를 반드시 만족해야 한다.
6.11 미디안(median)
미디안이란 n개의 서로 다른 키가 있을 때, 키 중에서 반은 그보다 작고, 반은 그보다 큰 키를 가리킨다. 예를 들어 1 7 10 13 30이 있을 때, 10이 미디안이다.
6.12 밀러-래빈의 무작위적 소수검사(miller-rabin randomized primality test)
소수검사문제를 푸는 데 전형적으로 사용되었던 효율적인 알고리즘으로, 소수검사를 푸는데 가장 효율적이 다차시간 알고리즘을 발견하지 못했던 때에 이용되었던 방법이다.
7.1 반대자 논법(adversary argument)
트리에서 최대키와 최소키를 모두 찾는 데 필요한 최악의 경우 비교횟수 하한을 구하는데 이용하는 방법으로
7.2 방향그래프(directed graph/digraph)
그래프에서 정점과 정점을 잇는 이음선에 방향이 있는 그래프를 방향 그래프라고 한다.
7.3 버블정렬(bubble sort)
Bubble Sort는 가장 기본적이고 초보적인 Sorting 방법으로써, 서로 인접한 데이터들을 뒤에서부터 자리바꿈하면서 정렬하는 방법이다. (Selection Sort는 앞에서부터 정렬한다.)
효율성은 떨어지나, 구현이 간단하여 속도가 별로 중요하지 않은 경우에 널리 쓰이는 방법이다.
7.4 베이시안 네트워크(bayesian network)
베이시안 네트워트는 질병과 증상 사이에 존재하는 확률적 관계를 나타내는 표준이 된다. 베이시안 네트워트의 응용으로, 특정 질병의 집합에서 환자가 걸린 질병만을 포함하는 사전확률을 구하는 효율적인 알고리즘들이 존재한다.
7.5 변환 알고리즘(transformation algorithm)
결정문제 A를 풀려고 하고, 결정문제 B를 푸는 알고리즘이 있다고 가정하자. 그리고 문제 B를 푸는 알고리즘이 y에 대해서 “예”라고 답하면 문제 A에 대한 답도 “예”가 되도록, 문제 A의 모든 사례 x에서 문제 B의 사례 y를 만들어내는 알고리즘을 작성할 수 있다고 가정하자. 이러한 알고리즘은 변환 알고리즘이라고 한다.
7.6 별모양 네트워크(star-connected network)
별모양 네트워크는 프로세서 하나가 중앙 프로세서 역할을 한다. 즉, 다른 프로세서는 모두 그 중앙 프로세서로 연결하는 링크가 있다.
7.7 병렬 RAM(PRAM)
PRAM(상변환 메모리)은 비휘발성 메모리의 한 종류이다. PRAM은 열을 가함에 따라 비정질상태와 결정질상태로 바뀌는 칼코게나이트 유리의 독특한 특성을 이용하여 데이터를 저장한다. PRAM은 차세대 메모리 기술 중 하나로 현재 비휘발성 메모리 시장의 대부분을 차지하고 있는 플래시 메모리를 대체할 수 있을 것으로 기대된다.
7.8 병렬 컴퓨터(paralled computer)
동시에 동작하는 복수의 마이크로프로세서를 사용하는 컴퓨터. 병렬 컴퓨터용으로 작성된 프로그램은 작업(task)을 동시에 처리하는 복수의 처리 장치에 골고루 분담시킴으로써 처리 속도를 향상시키고 단위 시간당 작업량을 증가시킬 수 있다. 수천 개 규모의 마이크로프로세서를 사용하는 컴퓨터 시스템을 초병렬 컴퓨터(massively parallel computer)라고 한다.
7.9 보간 검색(interpolation search)
보간 검색은 찾으려는 레코드가 있음직한 부분의 키를 택하여 검색하는 방식이다.
선정 레코드 번호 = {(찾으려는 키 값(추측) - 최소키 값)/9최대키 값 - 최소키 값)} x 레코드 수
찾으려는 레코드 근처에서부터 찾아가기 때문에 검색시간이 빠르지만, 예측을 해야 하므로 실제로는 프로그래밍이 불가능하다.
7.10 보강된 보간검색(robust interpolation search)
최악의 보간검색-mid가 계속해서 low가 되는 경우-은 모든키와 비교하게 되어, 순차검색이 되어 버린다. mid-low와 high-mid가 항상 gap보다는 크도록 변수 gap을 정하여 이러한 단점을 보완한 검색을 보강된 보간검색이라고 한다.
7.11 보조정리(lemma)
다른 명제를 증명하기 위해 사용되는 보조적인 명제이다.
7.12 복잡도 카테고리(complexity category)
알고리즘의 일반적인 시간복잡도의 나열이다. 종류는 다음과 같다.
⊝(lg n) ⊝(n) ⊝(n lg n) ⊝(n²) ⊝(n³) ⊝(2ⁿ)
크기비교는 다음과 같다.
Θ(lg n) < Θ(n) < Θ(n lg n) < Θ(n²) < Θ(n³) < Θ(2ⁿ)
7.13 복잡도 함수(complexity function)
시간 복잡도의 함수이다. 일반적으로, 음이 아닌 정수가 주어지면 음이 아닌 실수를 내주는 함수가 될 수 있다.
7.14 복호화(decryption)
암호화가 되어있는 문자를 보통의 평문으로 바꿔주는 절차이다.
7.15 분기한정 가지치기 너비우선검색
트리의 너비우선탐색을 이용하여 검색하는 방법이다.
7.16 분기한정 가지치기 최고우선검색
유망한 마디들의 한계 값을 비교하여, 그 중에서 가장 좋은 한계 값을 가진 마디의 자식마디를 방문한다. 이렇게 하면 미리 정한 순서대로 마디를 기계적으로 방문하는 것보다 종종 더 빨리 최적 해에 도달할 수 있다. 이 방법을 분기한정 가지치기 최고우선탐색이라고 한다.
7.17 분기한정법(branch-and-bound)
분기한정 알고리즘은 어떤 마디가 유망한지를 결정하기 위해서 그 마디에서 수를 계산한다. 이 수는 그 마디 아래로 확장하여 구할 수 있는 해답 값의 한계를 나타낸다. 그 한계 값이 그때까지 찾은 최고 해답 값보다 더 좋지 않으면, 그 마디는 유망하지 않다. 그렇지 않으면, 그 마디는 유망하다. 최적 값은 무제에 따라서 최대 값이 될 수도 있고, 최소 값이 될 수도 있다.
7.18 분배에 의한 정렬(sorting by distribution)
= 기수정렬
7.19 분할정복(divide and conquer)
분할 정복법은 문제의 사례를 2개 이상의 더 작은 사례로 나눈다. 이 작은 사례는 주로 원래 문제에서 그대로 따온다. 작은 사례에 대한 해답을 바로 얻을 수 있으면, 원래 문제의 해답은 이 해답들을 통합하여 구할 수 있다. 작은 사례가 아직 너무 커서 해답을 바로 구하지 못한다면, 그보다 더 작은 사례로 나눌 수 있다. 이렇게 사례를 나누는 과정은 해답을 바로 구할 수 있을 만큼 충분히 작아질 때까지 계속된다. 이러한 과정을 통한 이 방법은 하향식 접근방법이다.
7.20 비결정적 알고리즘(nondeterministic algorithm)
추측단계를 논하는 알고리즘으로, 이 단계에서는 문제의 사례를 가지고 단순히 임의의 문자열 S를 만들어낸다. 이 문자열은 그 사례에 대한 해답으로 추측한 것으로 생각할 수 있다. 그러나 그냥 전혀 관계없는 무의미한 문자열일 수도 있다.
7.21 비내림차순(nondecreasing order)
↔ 내림차순
7.22 비방향(undirected)
그래프의 이음선에 방향이 없으면 비방향이라고 한다.
7.23 비방향 그래프(undirected graph)
이음선에 방향이 없는 그래프를 말한다.
7.24 비순환적(acyclic)
비방향 그래프에서 한 정점에서 출발하여 그 정점으로 되돌아가는 경로를 단순순환경로라고 하는데, 이러한 단순순환경로가 없는 그래프를 비순환적이라 한다.
거대한 데이터베이스의 레코드의 키를 한꺼번에 모두 컴퓨터의 고속메모리에 올려놓을 수 없는 경우가 종종 있다. 그러므로 검색을 수행하기 위해서 보조기억장치인 디스크에 접근해야 할 필요가 있다. 이 때 좀 더 용이한 추가와 삭제를 위해 고안한 알고리즘이 B-트리 알고리즘이다.
7.27 빠른 정렬(Quicksort)
빠른 정렬은 배열을 두 부분으로 분할한 다음, 각 분할된 부분을 재귀적으로 정렬하여 정렬을 수행한다는 점에서 합병정렬과 비슷하다. 그러나 빠른 정렬은 배열을 분할할 때 어떤 기준 아이템보다 작은 아이템들은 모두 그 앞부분에 위치시키고, 그 기준 아이템보다 크거나 같은 아이템들은 모두 그 뒷부분에 위치시킨다.
7.28 비뚤어진 트리(swewed tree)
이진검색트리에서 키가 동적으로 추가되고 삭제될 때, 결과트리가 항상 균형을 이루는 것은 아니다. 키가 한쪽 방향으로만 증가할 수도 있는데 이와같이 생성된 트리를 비뚤어진 트리라고 한다.
8.1 사례(instance)
문제가 파라미터를 가짐으로써 어떤 한 부류의 문제들을 나타내고, 그 파라미터에 어떤 값을 대입하면 그 부류에 속한 하나의 문제가 된다. 이렇게 파라미터에 지정하는 특정한 값을 문제의 사례라고 한다.
8.2 3-2 트리
B-트리에서 가장 간단한 트리를 3-2트리라고 하는데, 이 트리의 특성은 다음과 같다.
-각 마디에는 키가 하나 또는 둘 있다.
-내부마디에 키가 하나 있으면, 2개의 자식마디가 있고, 내부마디에 키가 둘 있으면, 3개의 자식마디가 있다.
-어떤 주어진 마디의 왼쪽 부분트리의 모든 키들은 그 마디에 저장되어 있는 마디보다 작거나 같다.
-어떤 주어진 마디의 오른쪽 부분트리의 모든 키들은 그 마디에 저장되어 있는 마디보다 크거나 같다.
-마디에 키가 둘 있으면, 그 마디의 중간 부분트리의 모든 키들은 왼쪽 키보다는 크거나 같고, 오른쪽 키보다는 작거나 같다.
-모든 잎마디는 수준이 같다.
8.3 삽입정렬(insertion sort)
삽입정렬 알고리즘은 이미 정렬된 배열에 레코드를 삽입하여 정렬하는 알고리즘이다.
시간 복잡도로 (n^2)을 갖는다.
8.4 상용대수(common algorithm)
어떤 수 x의 상용대수는 logx로 표시하며, x가 10의 몇 승이 되는 지를 나타낸다.
8.5 상자채우기 문제
크기가 다음과 같은 nro의 아이템이 있다고 하자.
s1,s2,s3,......
여기서 s(i)의 범위는 0과 1사이이다. 그리고 여러 상자에 아이템을 채운다고 가정하자. 여기서 각 상자의 용량은 1이다. 이 문제는 아이템을 모두 채우는 데 필요한 상자의 최소개수를 구하는 문제이다.
8.6 상태공간 트리(state space tree)
자료의 값들을 트리의 형태로 나타내는 것을 말한다.
8.7 상호보완 문제(complementary problem)
상호보완 문제란 원래 문제가 “아니오”라고 대답하면 “예”라고 대답하고, “예”라고 대답하면, “아니오”라고 대답하는 문제이다.
8.8 상호연결 네트워크
상호연결 네트워크는 크게 정적과 동적의 두 가지 부류로 나눌 수 있다. 정적 네트워크는 메시지 전달구조를 구축하는 데 전형적으로 사용되고, 동적 네트워크는 공유된 주소 저장장소 구조를 구축하는 데 전형적으로 사용된다.
8.9 선택과정(selection procedure)
탐욕적 알고리즘에서 가장 좋은 것(최적의 것)을 선택하는 과정을 선택과정이라 한다.
8.10 선택정렬(selection proceduresort)
실제 프로그래밍에 많이 사용되는 간단한 정렬 방법으로 첫 번째 키부터 기준키로 설정하며, 기준키로 설정된 값과 두 번째 위치, 세 번째 위치, … n 번째 위치의 값과 비교하면서 정렬한다. 가장 작은 인자를 찾아서 제일 앞에 놓고, 이 다음 작은 인자를 찾아 앞에 놓는 방법을 반복한다.
8.11 선형탐사법(linear probing)
해시에서 키들의 충돌이 일어났을 때의 해결방법으로, 현재 삽입하려는 키의 해시값에 의한 버킷에 이미 다른 레코드가 들어있다면 다음의 버킷에 새로운 레코드를 기입하는 방법이다.
8.12 셔우드 알고리즘(Sherwood algorithm)
셔우드 알고리즘은 결정적 알고리즘이 최악의 경우보다는 평균의 경우 훨씬 빠르게 수행될 때 유용하다. 이 알고리즘에서는 특정 입력에 대한 기준점이 재귀호출에서 low나 high에 계속 가깝게 나올 때, 최악의 경우 2차시간을 이축할 수 있다.
8.13 소수(prime number)
1보다 큰 수중에서 양의 약수가 1뿐인 정수를 말한다.
8.14 소수분포함수(prime distribution theorem)
소수분포함수 ㅠ(n)은 n보다 작거나 같은 소수의 개수이다.
8.15 수학적 귀납법(mathematical induction)
자연수 n에 관한 어떤 명제P(n)이 임의의 자연수에 대하여 성립하는 것을 증명하려면, (1) P(1)이 성립한다. (2) 면제 P(k)가 성립한다고 가정한다면, P(k+1)도 성립한다.를 과정에 의해 증명한다.
8.16 순수 2차 함수
시간복잡도가 순수한 2차항으로만 이루어진 것이다.
그래프에서 어떤 정점에서 그 정점 자신으로 가는 경로를 순환이라 한다.
8.18 시간복잡도 분석
입력크기의 값에 대해서 단위연산을 몇 번 수행하는지를 구하는 것이다.
8.19 신장트리(spanning tree)
어떤 그래프 g 의 모든 이음선을 제거한 상태에서 어떤 이음선이든 하나씩 놓으면서 버텍스들을 연결해갈 때 트리형태로(루프가 없는 상황)로 모든 버텍스가 사이에 연결(path)가
존재하도록 이음선을 놓을 수 있다. 이렇게 만들어진 모든 그래프를 어떤 그래프 g에 대한 spanning tree(신장트리)라고 한다.
8.20 쌍방합병(two-way merge)
쌍방합병이란 2개의 정렬된 배열을 하나의 정렬된 배열로 합하는 것을 의미한다. 합병정렬 알고리즘에서 사용하는 방법이다.
동시 써넣기, 동시 읽기의 약자이다. 두 프로세서가 동시에 읽거나 쓸때, 그것의 우선순위를 결정하는 알고리즘이다.
9.1 알고리즘(algorithm)
어떤 기법을 한 문제에 적용하게 되면 그 문제에 대한 답을 찾는 단계적인 절차가 나온다. 이러한 단계적인 절차를 그 문제에 대한 알고리즘이라고 한다.
9.2 RSA(Rivest-Shamir-Adelmen) 공개키 암호체계
Rivesrt, Shamir, Adeiman 등 3인이 공동 개발한 RSA법을 사용한 암호 알고리즘으로 공개키 암호체계의 사실상의 세계 표준이다. 2개의 상이한 소수 p,q를 이용하여 암호화 키(n,e)와 복호화 키(n.d)를 생성하며 암호화 키는 공개키, 복호화 키는 비밀키로 관리한다.
9.3 암호 알고리즘
정보 시스템 내부에 보관되거나 통신망을 통하여 전송되는 정보의 훼손, 변조, 유출 등을 방지하기 위해 정보를 암호화와 복호화하는 과정에서 사용되는 함수
9.4 암호문(ciphertext)
암호화 된 정보를 말한다.
9.5 암호학(cryptpography)
암호학은 한사람이 다른 사람에게 보낼 메시지를 암호화하여, 그 메시지를 가로챈 사람이 그 메시지를 복호화할 수 없게 만드는 것과 관계가 있는 학문 분야이다.
9.6 암호화(encryption)
정보를 보낼 때나 받을 때, 그 정보의 비밀성을 보장하기 위하여 해독할 수 없도록 다른 형태의 정보로 변환하는 것으로, 키에 의해서 암호화가 되거나 복호화가 되며, 사용된 키 외애는 해독 할 수 없도록 하여, 정보의 안전성을 확보하는 과정이다.
단일명령흐름, 다중데이터 흐름을 나타내는 구조로, SIMD 구조에서는 같은 명령이 중앙제어장치의 제어 하에 모든 처리장치에 의하여 동기적으로 실행된다. 모든 프로세서가 각 주기마다 하나의 명령을 반드시 실행해야 하는 것은 아니고, 어떤 프로세서도 어느 주기에서든지 연결이 끊어져도 된다.
단일명령흐름, 단일데이터흐름 컴퓨터라고 하며, 직렬 컴퓨터라고도 한다. 이 모델은 중앙처리장치라고 하는 하나의 프로세서와 메모리로 구성되어 있다. 이 모델은 단일 순서의 명령을 취하고, 단일 순서의 데이터를 가지고 동작한다.
9.9 AVL-트리
각 노드의 왼쪽 서브트리의 높이와 오른쪽 서보 트리의 높이 차이가 1이하인 이진탐색트리
비결정적 다차의 약자로, NP는 다차시간 비결정적 알고리즘으로 풀 수 있는 모든 결정 문제의 집합이다.
9.11 NP-난해(NP-hard)
NP-완전 문제는 모두 NP-난해문제이다. 또한 NP-완전 문제에 상응하는 최적화 문제는 모두 NP-난해이다.
9.12 NP-동일(NP-equivalent)
문제가 NP-난해이면서 NP-용이이면 NP-동일이라고 한다.
9.13 NP-완전(NP-complete)
외판원 문제와 수천 개의 다른 문제들 중에서 하나만이라도 풀 수 있는 효율적인 알고리즘을 구한다면, 다른 모든 문제를 푸는 효율적인 알고리즘도 존재한다는 견지에서 이러한 문제들은 어려운 정도가 같다. 이러한 알고리즘을 결코 찾을 수 없었지만, 찾기가 불가능하다고 증명하지도 못했다. 이러한 흥미 있는 문제들을 NP-완전이라고 한다.
9.14 NP-용이(NP-easy)
문제가 NP-완전 문제가 축소 가능할 때, 문제가 NP-용이하다고 한다.
다중명령흐름, 다중데이터 흐름 컴퓨터로, MIMD 컴퓨터는 각 프로세서에 운영체제와 프로그램을 둘 다 저장한다.
9.16 열린해시법(open hashing)
해싱에서 충돌을 해결하는 가장 좋은 방법 중 하나로, 이 방법은 열린 주소 찾기라고도 한다. 열린 해시법은 각 해시값마다 바구니를 하나씩 만들고, 그 값으로 해시되는 모든 키는 그 값에 딸린 바구니에다 넣는다. 열린해시법은 연결된 리스트로 보통 구현된다.
9.17 0-1 배낭 채우기 문제(0-1 Knapsack problem)
0-1 배낭 채우기 최적화 문제는 배낭에 넣을 아이템의 무게가 가치를 안다고 가정하고, 가치의 합이 최대가 되도록 아이템을 배낭에 어떻게 채울지를 알아내는 문제이다. 여기서 배낭의 최대용량은 W이다.
9.18 올림수(ceiling)
실수 x보다 크거나 같은 가장 작은 정수를 나타낼 때, 그 정수를 ⌈x⌉라 표시하고 ⌈x⌉는 x의 올림수라 한다.
9.19 완전2차함수(complete quadratic function)
순수 2차항만으로 이뤄져 있지 않고, 2차항과 1차항의 조합으로 이워져 있는 함수를 말한다.
9.20 완전연결 네트워크(completely connected network)
각 프로세서가 다른 모든 프로세서와 직접 연결되어 있는 구조이다. 따라서 송신 프로세서는 다른 수신 프로세서에 직접 연결된 링크를 통하여 메시지를 보낼 수 있다. 링크의 개수는 프로세서의 개수에 대하여 2차가 되므로, 이러한 유형의 네트워크는 매우 비싸다.
9.21 외부검색(external search)
거대한 데이터베이스의 레코드의 키를 한꺼번에 모두 컴퓨터의 고속메모리에 올려놓을 수 없는 경우가 종종 있다. 그러므로 검색을 수행하기 위해서 보조기억장치인 디스크에 접근해야 할 필요가 있다. 이러한 검색을 외부검색이라 한다.
9.22 외부경로길이(EPL : external path length)
트리의 외부경로길이는 뿌리마디에서 잎마디로 가는 모든 경로의 총 길이이다.
잎마디에 도달하기 위해서 결정트리에서 비교하는 횟수는 잎마디로의 경로의 길이가 된다.
9.23 외판원 문제(Traveling salesperson problem)
외판원 문제(Traveling salesperson problem) 또는 순회 외판원 문제는 조합 최적화문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다.
그 정의를 말하자면, 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서는 무엇인지를 구하는 것이다.
9.24 우선순위 대기열(priority queue)
우선순위 대기열은 빈도수에 따른 요소들의 나열로, 우선순위가 가장 높은 요소가 항상 다음에 제거된다.
9.25 원소(element)
집합을 이루는 하나하나의 요소이다.
9.26 유망함수(promising function)
되추적은 막힌 곳으로 이르는 마디라는 사실을 알면, 그 마디의 검색을 중단하고 그 마디의 부모마디로 돌아가서 다음 자식마디의 검색을 계속하는 프로시저이다. 마디를 방문할 때 그 마디가 해답이 될 가능성이 없는 것으로 결정되면, 그 마디를 유망하지 않다, 그렇지 않으면 유망하다고 한다. 이와 같이 유망한지 아닌지를 판단해주기 위해 사용하는 함수를 유망함수라고 한다.
9.27 유클리드 알고리즘
A 와 B 의 최대공약수를 구할때, A > B 이라고 하면, A = a * g , B = b * g 에서, C = A - B = (a - b) * g 라 두면, 큰 수인 A , B 의 최대공약수를 구하는 것보다는 작은 수인 B, C 의 최대공약수를 구하는 것이 쉽다는 알고리즘이다.
9.28 의사다차시간(pseudopolynomial-time)
최악의 경우 시간복잡도의 상한이 크기와 절대크기로 모두 다차함수가 되는 알고리즘을 의시다차시간이라 한다.
9.29 이분검색(binary search)
먼저 정렬된 배열의 가운데 아이템 검색한 키 x를 비교하여 x의 위치를 잡는다. 만약 그들이 같으면, 알고리즘은 종료된다. 그렇지 않으면, 배열은 두 개의 부분배열로 분리되며, 그 중 하나는 가운데 아이템의 왼쪽 부분에 위치한 아이템을 모두 포함하고, 다른 하나는 오른쪽 부분에 위치한 아이템 모두 포함한다. 만약 x가 가운데 아이템보다 작으면, 알고리즘은 가운데 아이템보다 작은 아이템들의 부분배열에 적용된다. 그렇지 않으면, 그보다 큰 아이템들의 부분배열에 적용된다. 즉, x를 해당 부분배열의 가운데 아이템과 비교할 때 만약 그들이 같으면 알고리즘을 종료하고, 그렇지 않으면 그 부분을 제외한 다른 부분을 나눠서 다시 알고리즘을 적용한다. 이 알고리즘은 x를 찾거나, x가 그 배열에 없음이 확실할 때까지 계속된다.
9.30 이음선(edge/arc)
그래프에서 정점과 정점을 잇는 선을 이음선이라고 한다.
9.31 이중해시법(double hashing)
이중 해시법으로 알려져 있는 재해시 설계법은 해시에서 충돌이 일어날 경우 2번째 해시함수를 사용하는 방법이다.
9.32 이진 코드(binary code)
컴퓨터는 0과 1만을 인식한다. 이처럼 0과 1로만 표현하는 것을 이진코드라 하면, 컴퓨터 내부적으로 이용하는 코드이다.
9.33 이진검색 트리(binary search tree)
이진검색 트리는 순서가능집합에 속한 아이템으로 구성된 이진 트리인데, 다음 조건을 만족한다.
1. 각 마디는 하나의 키만 가지고 있다.
2. 주어진 마디의 왼쪽 부분트리에 있는 키는 그 마디의 키보다 작거나 같다.
3. 주어진 마디의 오른쪽 부분트리에 있는 키는 그 마디의 키보다 크거나 같다.
9.34 2-트리(2-tree)
잎마디가 아닌 모든 마디가 정확히 자식마디를 2개 갖는 이진트리를 2-트리라고 한다.
9.35 2차시간 알고리즘(quadratic-time algorithm)
이차항의 시간복잡도를 가진 알고리즘을 2차시간 알고리즘이라고 한다.
(x+y)ⁿ을 정리했을 때, 각 항의 계수에 해당한다.
9.37 인접행렬(adjacent matrix)
그래프에서, v1에서 v2로 가는 이음선이 있는 경우, v2는 v1에 인접해 있다고 하기 때문에, 이 때의 배열은 그래프의 인접행렬이라고 한다.
9.38 1차시간 알고리즘(linear-time algorithm)
1차항의 시간복잡도를 가진 알고리즘을 1차시간 알고리즘이라고 한다.
9.39 임계값(threshold)
하나의 변수 x가 어느 값이 되었을 때 특이한 상태나 급격한 변화가 일어나 임계 상태에 있을 때의 x값이다.
9.40 입력크기(input size)
보통 배열에 속한 아이템의 개수 n을 말한다.
9.41 잎마디(leaf)
트리에서 자식마디가 없는 마디이다.
10.1 자연대수(natural logarithm)
logℯⅹ를 ln x로 표시하고 x의 자연대수라고 한다.
10.2 자유트리(free tree)
일반적인 tree(트리)를 말한다.
10.3 재귀 크리(recursion tree)
재귀적 방법에 의해 구현되는 알고리즘을 한 눈에 알아보기 위해, 접근하기 쉬운 트리로 표현한 것을 말한다.
10.4 재현식(recurrence equation)
재귀호출 방법에 의해서 구해지는 시간복잡도의 일반식을 말한다.
10.5 저밀도 그래프(spare graph)
연결 그래프에서 이음선의 개수가 정점의 개수의 범위에 대한 값의 하한과 가까운 그래프를 나태내면 저밀도 그래프라고 한다.
10.6 적정성 점검(feasibility check)
탐욕적 알고리즘에서 선택과정 후에 얻어지는 결과가 실제의 해답을 초과하는지 점검하는 단계이다.
10.7 전치순열(transpose)
일반적인 순열을 반대로 전환해서 표현한 식이다.
10.8 전치코드(prefix code)
길이가 변하는 이진 코드의 특수형태의 하나로 전치코드가 있다. 전치코드에서는 한 문자의 코드워드가 다른 문자의 코드워드의 앞부분이 될 수 없다. 예를 들어, 01이 ‘a'의 코드워드라면 011은 ’b'의 코드워드가 될 수 없다.
10.9 점근적인 상한(asymptotic upper bound)
big O는 함수의 궁극적인 상태만 고려하기 때문에 함수의 점근적인 상태를 나타낸다고 말한다. big O는 함수의 점근적인 상한을 준다고 한다.
10.10 점근적인 하한(asymptotic lower bound)
점근적인 상한과 같은 개념으로, Ω는 점근적인 하한을 나타낸다.
10.11 정렬 작업(sorting task)
임의의 순서로 나열된 레코드의 정렬 작업은 키의 값을 기준으로 한 순서로 그 레코드를 다시 나열하는 것이다.
10.12 정수론(Number theory)
정수론은 정수의 성질과 관계가 있는 수학의 한 분야이다.
정수론적 알고리즘은 정수가 포함된 문제를 푸는 알고리즘이다. 예를 들어, 두 정수의 최대공약수를 찾는 알고리즘은 정수론적 알고리즘이라고 할 수 있다.
10.14 정적 상호연결 네트워크(static interconnection network)
정적 상호연결 네트워크는 프로세서 사이에 직접 연결하는 링크가 있는데, 때로는 직접 네트워크라고 한다. 완전연결 네트워크, 별모양 네트워크, 한 장 네트워크 등이 이에 속한다.
10.15 정적검색(static searching)
정적검색은 한번에 모든 레코드가 파일에 저장되고, 추후에 레코드를 추가하거나 삭제할 필요가 없는 경우 행해지는 검색이다. 정적검색이 적절한 경우의 예는 운영체제명령문에 의해서 수행되는 검색이다.
10.16 정점(vertex)
그래프를 그림으로 표현할 경우의 원(circle)으로 일반적으로 item을 일컫는다.
10.17 정지문제(Halting problem)
다루기 힘들다고 증명된 문제 중에 결정 불가능한 문제가 있다. 이 결정 불가능한 문제 중에 가장 널리 알려진 것이 정지문제로, 이 문제는 임의의 알고리즘과 임의의 입력을 입력으로 받아서 주어진 알고리즘에 주어진 입력을 적용시켰을 때, 알고리즘의 수행이 멈추는지를 결정하는 문제이다.
10.18 제어 명령문(control instructions)
제어명령문이란 루프를 제어하기 위한 색인 증가 명령문 같은 명령문을 말한다.
10.19 제자리정렬(in-place sort)
제자리정렬은 입력을 저장하는 데 필요한 장소 이외의 추가적인 저장장소를 사용하지 않는 정렬 알고리즘이다.
조건부 확률은 확률적 추론에서 어떤 확률에 대하여 조건을 걸어, 특정 확률로 계산하게 하는 것이다.
경우의 수에 대한 내용으로, 서로 다른 n개에서 중복 없이 r개를 선택하는 방법이다.
10.22 주소전달 파라미터(reference parameter)
프로시저를 사용한 알고리즘의 경우는 파라미터를 주소전달 파라미터를 사용하여 결과 값을 손실 없이 넘겨준다. 주소전달 파라미터는 파라미터들이 같은 주소를 사용하는 것을 말한다.
10.23 직관적 귀납법(constructive induction)
시간복잡도의 재현식을 풀기위해 도입하는 귀납법이다.
10.24 직접 네트워크(direct network)
= 정적 상호연결 네트워크
10.25 짝지움(matching)
특정한 집합에 속하는 정점들을 각 정점이 정확하게 다른 하나의 정점과 싸이 되도록 짝을 맞춘다. 이런 식으로 정점의 쌍을 만드는 것을 특정집합의 짝지움이라고 한다.
11.1 차대키(second-largest key)
차대키란 최대키-팀의 토너먼트전이라고 가정하면, 우승팀-를 제외한 나머지 키들 중에서 가장 큰 키를 말한다. 토너먼트 게임이라고 생각하면, 차대키는 결승전에서 최대키에게 패배한 2등의 키(팀)을 말한다.
11.2 총 마디거리(total node distance : TND)
트리에서 모든 마디에 대한 마디거리의 합을 말한다.
11.3 최선의 경우 시간복잡도(best-case time complexity)
단위연산을 수행하는 최소횟수를 구하는 것으로, 어떤 알고리즘이 주어지면, B(n)을 입력크기 n에 대해서 그 알고리즘이 수행할 단위연산의 최소횟수로 정의한다.
11.4 최소비용 신장 트리(minimum spanning tree)
신장트리 (spanning tree) 어떤 그래프 G의 신장 트리 ST(G)는 G의 부분 그래프로서 G의 모든 정점을 포함하여, 임의 두 정점 사이에 경로가 존재하는 트리이다.
최소비용 신장 트리(minimum cost spanning tree) 가중치 그래프에서 이음선의 가중치의합이 최소가 되는 신장 트리이며, 최소 비용 신장트리는 그리디(Greedy) 알고리즘을 통해 구할 수 있다.
11.5 최악의 경우 시간복잡도(worst-case time complexity)
단위연산이 수행되는 최대 횟수를 고려하는 것이다. 어떤 알고리즘이 주어지면, W(n)을 입력크기 n에 대해서 그 알고리즘이 수행할 단위연산의 최대 횟수로 정의한다.
11.6 최적(optimal)
보통 이진검색 트리는 키의 값에 따라서 검색할 수 있는 레코드도 포함되어 있다. 우리의 목표는 이진검색 트리에서 키를 찾는 데 걸리는 평균시간이 최소가 되도록 키를 잘 정리하는 것에 있다. 이런 식으로 정리된 트리를 최적이라고 한다.
11.7 최적순서(optimal sequence)
스케줄 짜기에서 작업하는 순서에 따라 달라지는 총 이익을 최대로 하는 적절한 순서를 찾는 게 중요하다. 그러한 순서를 최적 순서라 한다.
11.8 최적 일주여행경로(optimal tour)
방향그래프의 주어진 정점에서 출발하여, 그래프에 있는 각 정점을 정확하게 한번씩만 방문하고, 출발한 정점으로 돌아오는 최단경로를 찾을 때, 이러한 경로를 최적 일주여행경로라고 한다.
11.9 최적 임계값(optimal threshold value)
분할과 호출 시 걸리는 시간의 적절성에
대한 것으로, 최적 임계값으로 정한 n값보다 더 작은 사례에 대해서는 계속 분할하는 것보다 다른 알고리즘을 호출하여 사용하는 편이 최소한 빠르고, 더 큰 사례에 대해서는 계속 분할하는 편이 더 빠르게 되는 사례크기가 바로 임계값이 된다.
11.10 최적의 원칙(principle of optimality)
어떤 문제 사례에 대한 최적 해가 그 사례를 분할한 부분사례에 대한 최적 해를 항상 포함하고 있으면, 그 문제는 최적의 원칙이 성립된다고 한다.
11.11 최적 집합(optimal set of jobs)
스케줄 짜기에서 최적순서에 속한 작업의 집합을 최적집합이라 한다.
11.12 최적화 문제(optimization problem)
어떠한 특정 문제를 푸는 데 있어서 가장 적절한 문제로, 최단경로 문제가 이에 속한다.
그 사례의 해답은 해답후보 중에서 최적인 값이 된다.
11.13 충돌(collision)
= 해시 충돌
12.1 코드워드(code word)
코드화 방식에서 언급되는 용어로 코드워드는 유일한 이진 문자열을 말한다. 코드화 방식은 이 코드워드를 사용해서 각 문자를 표현한다.
12.2 쿠퍼의 알고리즘
확률적 추론 알고리즘 중에서 분기한정 가지치기 최고우선검색 알고리즘을 통해 확률적 추론 문제를 푸는 것으로, 쿠퍼에 의해 고안됐다.
12.3 크로스바 스위치 네트워크(crossbar switching network)
크로스바 스위치 네트워크는 pro 프로세사가 스위치의 격자를 사용하여 m개의 메모리 뱅크에 연결되어 있는 구조로, 격자의 각 위치에 스위치가 있다. 예를 들어 프로세서3이 현재 메모리 뱅크2에 접근할 수 있다면, (3,2)의 자리에 스위치가 켜진다.
12.4 크루스칼 알고리즘(Kruskal's algorithm)
크루스칼 알고리즘은 최소비용 신장 트리 문제를 풀기위한 알고리즘이다. 각 정점마다 하나씩 그 정점만 포함하는 V의 서로소 부분집합들을 만드는 것으로 시작한다. 그리고 나서 가중치가 작은 것부터 차례로 이음선을 검사한다. 만약 어떤 이음선이 서로소 부분집합들에 있는 두 정점을 연결하면, 그 이음선을 추가하고, 구 부분집합을 하나로 합친다. 간선의 개수를 E, 점의 개수를 V라고 하면 이 알고리즘은 O(
ElogV)의 시간복잡도를 가진다.
12.5 큰 O(big O)
알고리즘의 시간복잡도를 말한다. Worst case일 경우의 시간복잡도이다.
레코드의 순서집합의 원소인 키는 레코드를 식별할 유일한 식별자이다. 키 레코드에 속하는 원소들은 서로 독립적인 내용을 포함한다.
13.1 탐욕적 알고리즘
탐욕적 알고리즘은 일련의 선택을 하여 해답에 도달하는 데, 선택할 때마다 당시 가장 최고인 것처럼 보이는 것을 택한다. 즉, 각 선택은 국부적으로는 최적이다. 전체적으로 최적인 해답을 얻는 것이 희망이지만, 항상 그렇게 되지는 않는다. 따라서 알고리즘이 항상 최적의 해답을 주는지 반드시 확인해야 한다.
차대키를 찾기 위해 이용하는 방법이다. 최대키가 아닌 다른 키와 비교해서 패배한 키는 차대키가 될 수 없다. 즉, 토너먼트 방법은 패배하면 탈락하는 토너먼트 경기에서 사용한 방식을 본떴기 때문에 그렇게 명명 되었다.
튜플은 수학에서 기본적으로 사물의 유한한 순서, 또는 순서를 가진 집합을 표현하는 용어이다. 일반적으로 n개의 요소를 가진 튜플을 n-튜플이라고 한다.
트리의 깊이는 그 트리에 있는 모든 마디의 깊이 중 최대값이다.
문제에 특정한 값이 지정되어 있는 않은 변수를 말한다.
비방향 그래프에서 각 정점이 다른 모든 정점에 인접해 있는 경우를 말한다.
14.3 평균의 경우 시간복잡도
어떤 알고리즘이 주어지면, A(n)을 입력크기 n에 대해서 그 알고리즘이 수행할 단위연산의 평균횟수로 정의한다. 그때의 A(n)이다.
그래프에서 2개의 이음선이 서로 교차하지 않도록 그린 그래프를 평면그래프라고 한다.
어떤 프로그램이 원하는 특정 작업을 처리할 수 있는 고급 언어 프로그램의 한 부분 또는 부프로그램의 한 형태이다.
14.6 프림의 알고리즘(Prim's algorithm)
프림 알고리즘(Prim's algorithm)은 가중치가 있는 연결된 무향 그래프의 모든 꼭짓점을 포함하면서 각 변의 비용의 합이 최소가 되는 부분 그래프인 트리, 즉 최소 비용 걸침 나무를 찾는 알고리즘이다. 간선의 개수를 E, 정점의 개수를 V라고 하면 이 알고리즘은 이진 힙을 이용하여 자료를 처리하였을 때를 기준으로 O(E log V)의 시간복잡도를 가진다.
14.7 플로이드 알고리즘
플로이드 알고리즘은 최단거리 경로를 구하는 또 다른 방식의 알고리즘이다. 다익스트라의 최단거리 알고리즘은 그리디 알고리즘을 이용한데 반해, 플로이드의 최단거리 알고리즘은 동적계획법을 이용한다. 이 알고리즘을 사용하면 모든 노드에서 자신을 제외한 다른 모든 노드로 가는 최단거리 경로를 얻을 수 있다.
1, 1, 2, 3, 5, 8, 13,…을 이른다.
병렬 RAM을 말한다. 병렬 RAM에 대한 내용은 앞에 언급되어 있다.
하노이탑 문제는 3개의 말뚝과 크기가 다른 디스크 n개로 구성되어 있다. 목표는 3개 중 한 말뚝에 크기가 감소하는 순서로 쌓여있는 디스크를 다른 말뚝에 옯기는 것이다. 여기서 남은 하나의 말뚝을 임시말뚝으로 사용한다. 문제를 풀 때는 다음 규칙을 반드시 준수해야 한다. (1) 3개의 말뚝 이외에는 디스크를 놓을 수 없다. (2) 한 번에 하나의 디스크만 옮길 수 있고, 말뚝의 맨 위에 있는 디스크만 옯길 수 있다. (3) 큰 디스크를 작은 디스크 위에 올려놓을 수 없다.
10∼1,000대의 처리기를 병렬로 동작시키는 컴퓨터 구조. 소결합 다중 처리기라고도 한다. 처리기는 각각의 기억 장치를 가지고 있으며, 통신 채널에 의해 처리기를 모두 연결하고 있다. 예를 들면, 3차원 하이퍼큐브는 8개의 처리기를 가지고 있는데 각각 3회선의 통신 채널을 가지고 있다. 즉, 정육면체의 각 정점에 처리기가 있고, 변(邊)이 통신 회선으로 되어 있다고 할 수 있다
집합 A가 아래로 유계일 때는 A의 하계 안에 최대인 것이 존재한다. 이 수를 A의 하한(nfimum) 또는 최대하계라고 한다.
d차 한정 네트워크에서는 각 프로세서가 최대로 d개의 다른 프로세서에 연결되어 있다.
두 개의 정렬된 파일을 하나의 큰 정렬된 파일로 합병한다. 합병 정렬은 퀵정렬과 마찬가지로 분할 정복 방식의 알고리즘이다. 두 부분의 배열의 크기가 동일해야 한다.
소수(여기서 소수는
솟수를 의미한다.)가 아닌 1보다 큰 정수를 의미한다.
문제의 사례를 지정한 문제를 가지고 질문한 것에 대한 답이다.
탐욕적 알고리즘에서 가장 좋은 동전을 선택하는 선택과정고 적정한지의 적정성 점검 이후에, 탐욕적 알고리즘에 의해 나온 답과 실제의 답이 맞는지 알아보는 과정이 해답점검이다.
연결된 그래프가 각 정점을 정확히 한번만 경유하는 경로인 한 circle(순환)을 아일랜드의 수학자 Hamilton (Sir William Rowan Hamilton, 1805 - 1865)의 이름을 따서 Hamilton 순환 (Hamiltonian cycle) 이라고 부르며, Hamiltion 순환을 갖는 모든 그래프를 Hamilton 그래프(Hamiltonian graph)라고 한다.
15.10 해밀튼 회로 결정 문제
해밀튼 회로결정 문제는 연결된 방향 그래프에 최소한 하나의 여행경로가 존재하는지 결정하는 문제이다.
해시는 Hash Table이라는 기억공간을 할당하고, 해시 함수(Hash Function)를 이용하여 레코드 키에 대한 Hash Table 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식이다.
해시에서 최소한 2개의 키가 하나의 인덱스로 해시될 경우를 말한다.
컴퓨터 암호화 기술의 일종으로 요약함수 ·메시지다이제스트함수(message digest function)라고도 하는데 주어진 원문에서 고정된 길이의 의사난수를 생성하는 연산기법이며 생성된 값은 '해시값'이라고 한다.
데이터의 효율적인 저장을 위해 데이터를 압축하는 문제를 해결하는 방법으로, 데이터 파일을 코드화한다.
허프만 코드에 대한 알고리즘이다. 여기서는 우선순위 대기열을 사용하여, 우선순위 대기열에서는 우선순위가 가장 높은 요소가 항상 다음에 제거된다. 이 경우, 우선순위가 가장 높은 요소는 파일에서 빈도수가 가장 낮은 문자이다. 우선순위 대기열은 힙으로 구현한다.
트리에서 두 노드의 부모노드가 같으면, 그 두 노드는 형제노드라고 한다.
하나의 사건이 일어날 수 있는 가능성을 수로 나타낸 것으로 같은 원인에서 특정의 결과가 나타나는 비율을 뜻한다. 알고리즘에서 확률은 확률적 추론에 대한 알고리즘에서 사용한다.
몬테칼로 알고리즘을 말한다. 확률적 알고리즘은 다음 실행할 명령이 때로는 어떤 확률분포에 따라서 무작위로 결정된다. 결정적 알고리즘의 반대말이다.
어떤 발견에 대한 가장 그럴듯한 해석을 찾아내는 것은 인공지능과 전문가 시스템에서 중요한 문제이다. 예를 들어 의학에서 증상에 가장 맞는 병명을 알아내려고 한다든지, 전자회로에서 고장 난 지점이 어디인지를 예측하려고 한다든지, 자동차의 고장을 야기할 확률이 가장 높은 부분을 찾는다든지 하는 문제들을 들 수 있다. 이와 같이 발견에 대한 가장 그럴듯한 설명을 찾아내는 과정을 확률적 추론이라고 한다.
꽉 찬 이진트리구조로 최대힙과 최소힙으로 나뉜다. 최대힙의 경우 각 노드의 값은 자신의 자식의 값보다 크거나 같다. 힙의 최대값이 루트노드에 자리하게 된다.
힙에서 각 마디에 저장된 값은 그의 자식마다에 저장된 값보다 크거나 같다. 이를 힙 성질이라고 한다.
Heap 정렬은 Max Heap이라는 자료구조를 이용한 정렬방식으로 정렬하고자하는 레코드값들을 Heap이라는 특수한 구조에 저장한 다음 정렬 후 root부분을 추출하고, 다시 재정렬후 root부분을 추출하는 것을 반복함으로서 정렬된 레코드를 얻어내는 방식이다.