Section 1. 1
알고리즘의 분석을 (특별히는 effective한지를 알아내는 분석?) 하는 방법 중에 하나로 computational method를 소개함.
(O는 원래 
임)
- Q는 부분집합 I와 부분집합 O를 포함하는 집함(I와 O에 해당하지 않는 영역도 있음).
- f는 정의역과 치역이 모두 Q인 함수
- q is in O 이면, f(q) = q
Computational sequence 는 x0, x1, 처럼 차례로 입력되는 집합인듯?
여기까지의 특징은 x in I 이면, f(x)는 in I 일 수도 있고 in O일 수도 있음.
Computational sequence, x를 사용해서 f(x)를 반복적으로 계산하면,
f(x) in O 가 나옴. 이 때를 f(x_k) 라고 하면 (의
x_{k+1}=f(x_k) 이지만, 위 3번에 의해 x_{k+1} = x_k 가 되므로 더이상 계산할 필요 없이 종료.
따라서 (여기서는) 최소 k를 구하는게 목적.
/////////////////////////////////////////////////////////////////////////////////////////
이 방법은 Q가 무한이 될 경우 손으로 계산할 수 없을 만큼 방대해질 수 있다.
이 때문에 이 방법을 다르게 사용하기 위해 다음의 예를 제시한다.
A는 문자가 들어있는 집합.
A*는 A로 만들 수 있는 모든 문자열들의 집합(공집합도 포함 - 그 이유는 n의 조건이 n>=0 이기 때문임).
(여기서 A*를 도입하는 이유는, 1, 2, 3, .... 처음의 computational method처럼의 엄청나게 많은 state를 하나씩 따라가는게 아니라(손으로 하기에 너무 많을 수 있음), state라는 것을 A*라는 substring으로 도입하는 것임. 따라서 많은 상태가 축약 될 수 있음.)
N이 양의 정수라 할 때, Q = (
, j) 로 정의됨.
이 때 j = 0 이면 I, j = N 이면 O 임. (이 때문에 Q가 I와 O에 속하지 않는 다른 부분도 있다는 것을 알게 됨)
일단 처음에 했던 3번 정의에 의해 j = N일 경우는 명확하게,
f((, N)) = (, N) 가 됨.
f(, j)=(, a_j)
이 말은 뛰어넘을 상태가 없다는 것으로 추측 됨. a_j 는 j에 대한 다음 상태를 뜻하는 듯.
f(, j)=(
, b_j)
이 말은 뛰어넘을 상태가 있다는 것으로 추측 됨. b_j 는 j에 대한 다음 상태를 뜻하는 듯.
하지만 
가 변환 된 것에 주의.
여기서, a_j, b_j, 같은 것들을 모두 함수 f에 의해 정의 되어 있음.
결론 & 정리
Computation Method란 quadruple을 사용한 알고리즘 분석 방식임.
첫번째 부분은 1.1E를 어떻게 이 방식으로 분석하는지에 대한 소개이며, 두번째 부분은 이 방식이 비효율적일 경우 어떻게 대처하는지에 해결할 수 있는지에 대한 설명임.
PS. 스터디 노트에 담겨진 모든 글들은 모든 것을 완벽하게 확실히 하기 보다는 책에 그대로 적혀저 있는 것들,
최대한 반복해서 본 후 나름대로 했던 추측을 포함합니다. 따라서 잘못된 정보가 있을 수 있으며, 지적은 얼마든지 환영입니다.
최근 덧글