[컴퓨터 프로그램의 구조와 해석] 1.2 프로시저와 프로세스

어떤 일을 하기 위해 어떤 프로세스를 밟아야 할지 미리 정해 놓으려고 짜는게 프로그램이다.

여러가지 프로시저(절차)가 만들어 내는 프로세스(과정)를 미리 그려낼 수 있어야힌다. 

 

프로시저: 한 컴퓨터 프로세스가 어떻게 나아가는지 지난일을 발판 삼아 다음으로 해야 할 일을 밝힌 것.

 

단순한 프로시저가 만들어 내는 프로세스 가운데 자주 나타나는 몇가지 꼴(shape)을 살펴보자.

 

1.2.1 되돌거나(recursion)복하는(iteration) 프로세스

-선형 재귀 프로세스(linear recursive process)(되도는 프로세스)

: 바로 연산을 하지 않고 미루어 놓아 식이 늘어나다 미뤄둔 연산을 하며 줄어듬. 

 

되도는 프로세스는 프로세스 안에 상태변수도 없을뿐더러 뒤로 미뤄 둔 연산의 끈을 이어가며 '어디까지 계산했는지' 알아내려면 실행기 속에 숨은 정보가 더 들어 있어야함. 끈이 길수록 그런 정보가 더 많아짐. 

 

   -되도는 프로세스: 프로시저를 정의한 글(식)이 그렇다는 게 아니라 진짜 계산이 그런 꼴로 펼쳐진다는 뜻.

   -되도는 프로시저:프로시저를 정의하는 글(식) 속에서 자신을 불러 쓴다는 뜻

 

프로시저와 프로세스가 헷갈리는 까닭?

보통 널리쓰는 언어 번역기,실행기( Ada,C,Java 같은) 내부에서 되도는 프로시저를 해석할 때, 그 프로세스가 반복하는 것인지 따져보지 않고 프로시저를 불러 쓰는 횟수에 비례하는 만큼 기억 공간을 쓰도록,곧 되도는 프로세스만 내놓게끔 처리하기 때문.

그런 언어에서는 do,repeat, untill, for,while같은 반복하는 특별한 형태를 써야만 반복 프로세스 나타낼 수 있음.

 

-선형 반복 프로세스(linear iterative process)(반복하는 프로세스)

:정해진 상태변수(state variable)가 있어 반복할 때마다 바뀌는 계산 상태를 간추려서 기록해둘 수 있고, 계산단계가 넘어갈 때마다 상태변수 값을 고쳐 쓰는 규칙이 있음. 때에 따라 계산을 끝낼 조건을 따지는 마무리 검사 과정도 있음.

이 책에서 쓰는 Scheme처리기계는 정해진 기억 공간만 써서 돌아가게 할 수 있음. 이를 꼬리에서 되돌아가도록 실행기를 만들었다고 함(꼬리 되돌기 tail_recursive).

 

반복하는 프로세스에서는 프로그램 변수가 프로세스 단계마다 어떤 상태에 있는지 정확하게 나타내기 때문에, 계산을 잠시 멈추더라도 세 변수 값을 알기만 하면 실행기가 곧바로 계산을 이어갈 수 있다.

 

1.2.2 여러 갈래로 되도는 프로세스

피보나치(Fibonacci)수열: 앞에 나온 두 수를 더해 그 다음 수를 정하는 수열.

ex) 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

 

Fib(n)

n=0 이면 0,   n=1 이면 1

그 밖의 경우면 Fib(n-1)+Fib(n-2)

 위 정의를 프로시저로 만들면 되도는 프로시저가 만들어짐. 보통 이런 프로세스는 나무꼴로 펼쳐지고 단계마다 가지가 둘씩 갈라져 나온다. 같은 계산을 쓸데없이 반복하기 때문에 피보나치 수열을 구하기에는 별로 좋지 않은 방법이다.

그렇다고 여러 갈래로 되도는 프로세스가 안무 쓸모없는 것이라고 말하면 안된다. 여러 갈래로 되도는 규칙이 잘 맞을 때도 있다. 

1.2.3 프로세스가 자라나는 정도

앞에서 나온 문제들을 보면 어떤 프로세스냐에 따라 계산 자원을  쓰는 크기가 달라지는데 그 차이를 견주고 싶을 때, 프로세스가 자라나는 정도(자람차수)라는 개념을 씀. 입력의 크기에 따라 프로세스가 쓰는 자원양을 어림잡아 말함.

 

문제의 크기를 매개변수 n이라 할 때, n만큼 큰 문제를 푸는데 드는 자원양을 R(n)이라 하자.n에 매이지 않은 상수k1과 k2가 다음 조건을 만족 한다면 R(n)은Θ(f(n))차수로 자라난다고 하고 R(n)=Θ(f(n)) 이라고 쓰며 'theta of f(n)'라 읽는다.

 

-되도는 프로세스에서 사다리곱을 구하는 경우, 계산 단계가 n에 비례하여 늘어났고 프로세스가 거쳐야 할 단계는 Θ(n)만큼 늘어나고 계산에 필요한 기억 공간도  Θ(n)으로 자라남.

-반복하는 프로세스에서 사다리곱을 구하는 경우,  단계가 Θ(n)만큼 늘어나는 것은 되도는 프로세스와 같음.

but 기억공간은 Θ(1) 곧 늘거나 줄지 않음.

-여러갈래로 되도는 프로세스로 피보나치 수를 구하는데 드는 계산 단계는 Θ(Φ^n), 기억 공간은 Θ(n)으로 커짐. Φ는 황금비를 말함.

 

로그 자람차수: 문제크기가 두 배로 늘어도 정한만큼 자원을 씀.

1.2.4 거듭제곱

거듭제곱: 같은 수를 여러번 곱하는 문제. 밑수 b,0보다 큰 정수 n을 인자로 받아 b^n을 구하는 프로시저.

 

이 프로시저를 만드는 방법

-선형 재귀 프로세스

재귀규칙 b^n= b*b^n-1  ,   b^0=1 을 사용하여 프로시저 만들기. Θ(n)계산 단계를 거치며  Θ(n)만큼 기억 공간 사용.

-선형 반복 프로세스

 Θ(n)계산 단계를 거치지만 기억 공간은  Θ(1)사용.

-계속 제곱하는 방법

지수 n이 2의 거듭제곱일 때만 맞아떨어지기 때문에 모든 거듭제곱에서 같은 효과를 보려면 규칙을 바꿔야한다.

n이 짝수: b^n=(b^n/2)^2

n이 홀수: b^n=b*b^n-1

위 방법의 프로시저가 펼쳐내는 프로세스의 계산단계(시간)와 필요한 공간은 n의 로그로 자라남. 자람차수는 Θ(log n)이다.

n이 커질수록 자람차수 Θ(log n)과 Θ(n)의 차이는 엄청나게 벌어짐.

1.2.5 최대 공약수

정수 a와 b의 최대 공약수(GCD)란, 두 수를 나머지 없이 잘라 나눌 수 있는 가장 큰 정수를 말함.

a와 b로 나눈 나머지가 r일 때 a와 b의 최대공약수가 b와 r의 최대 공약수와 같다는 사실에 바탕을 둔다.

GCD(a,b)=GCD(b,r)

a와 b의 GCD를 구하는 문제는 그보다 적은 b와 r의 GCD를 구하는 문제로 줄어드는 과정을 밟아간다.

GCD(206, 40)=GCD(40, 6)

                        =GCD(6, 4)

                        =GCD(4, 2)

                        =GCD(2, 0) = 2

0보다 큰 정수 둘을 받아서 이런 과정을 되풀이하면 언제나 둘째 수가 0이 됨. 이때 첫 수가 GCD이다.

이렇게 GCD를 구하는 방법을 유클리드 알고리즘 (Euclid's Algorithm)이라 함.

반복하는 프로세스로 펼쳐지면 밟아야 할 단계의 수가 로그 비례로 자라남. 라메의 정리를 바탕으로 유클리드 알고리즘 차수를 구할 수 있다. 

라메의 정리(Lames Teorem): 유클리드의 알고리즘으로 GCD를 구하는데 k단계를 거치는 경우, 두 수 가운데 작은 수는 k번째 피보나치 수보다 크거나 같아야 함.

 

1.2.6 연습: 소수찾기

정수 n이 소수인지 알아보는 방법

- 약수찾기

n의 약수 가운데(1보다 큰)가장 작은 약수를 구하기. 2부터 이어지는 정수를 차례로 살펴서 n의 약수가 되는지 따져보는 방법.

n이 소수가 아니라면 루트 n보다 작거나 같은 약수가 꼭 있다는 사실에 바탕을 둔다. 

1부터 루트 n 사이 값만 따지면 됨으로 계산 단계: Θ루트 n 

- 페르마 검사

Θ(log n) 차수로 소수를 찾는 방법은 '페르마의 작은 정리'라고 하는 이론에서 이끌어낸 알고리즘.

페르마의 작은 정리: n이 소수고 a가 n보다는 작고 0보다는 큰 정수라면 a^n은 a modulo n으로 맞아떨어진다.

두 수를 n으로 나눈 나머지가 같은 때 그 두 숫자는 modulo n으로 맞아떨어진다고 함. 

a를 n으로 나눈 나머지를 a modulo n의 나머지라 하거나 짧게 a modulo n이라함.

수 n이 있을때 a<n인 수 a를 제멋대로 골라 a^n modulo n의 나머지를 얻는다. 그 값이 n이 아니면 n은 소수가 아니고 a가 맞으면 n은 소수일 확률이 높다. 페르마 검사를 하려면 어떤 수를 거듭제곱하여 구한 값을 다시 다른 수로 modulo하는 프로시저가 필요.

페르마 검사(Ferma test): 수 많은 a값을 고르고 따져보면서 n이 소수일 확률을 끌어올리는것. 어림잡은 답만 나옴.

어떤 수 n이 페르마 검사를 모두 거쳤다고 해도 n이 소수라고 잘라 말하지 못함. 그저 확률이 높은 뿐. 

n이 페르마 검사를 끝내지 못했다면 틀림없이 소수가 아님.

- 확률을 바탕으로 하는 알고리즘

틀린 답을 내지 않도록 페르마 검사를 조금 고쳐 만든 알고리즘. 페르마 검사처럼 a<n인 수를 골라 n과 a에 얽힌 어떤 조건을 따져보고 n이 소수인지 알아보는 방법을 쓴다 but n이 소수가 아닐 때에는 a<n인 정수 중 조건을 만족하는 경우가 거의 없다는 사실을 밝힐 수 있음.

페르마 검사를 거쳐 간다면 n이 소수일 확률은 반이 넘음. 검사를 두번 하면 확률은 4/3보다 크고 이런 검사를 되풀이해 잘못될 확률을 바라는 만큼을 낯출 수 있음.

확률 알고리즘(probablistic algorithm): 틀릴 확률이 줄어든다고 증명할 수 있는 검사방법