1.2.3 프로세스가 자라나는 정도 (임시)

Structure and Interprecation Of Computer Programs - Chapter 1.1

MIT 컴퓨터 공학 1학년 교재로 사용된다는 SICP. (Structure and Interprecation of Computer Programs)

번역본까지 출판되어 잘 팔리고 있는 책.

문제가 되지 않는 선에서 간략히 필자의 노트 필기 차원에서 여기에 정리함.


책에서는 Lisp 으로부터 파생된 (방언이라 표현하던데) scheme 으로 예제들이 정리가 되어있는데,

필자는 Scala 로 풀어보았음. - scala 소개는 본 블로그의 scala 문법 참고. 


초반부 - Lisp 소개와, scheme 의 기본 문법소개, 그리고 전위 연산 표기 소개등.


정의대로 계산법 (normal-order evaluation), 인자 먼저 계산법 (applicative_order evaluation)

def sum_of_square(a: Int, b: Int) = {

a*a + b*b 

}

sum_of_square(5+5, 2+3)

와 같이 작성했을때 


정의대로 계산법은 

1. (5+5)*(5+5) + (2+3)*(2+3)

2. 10*10 + 5*5 

3. 100 + 25

4. 125 

와 같이 좁혀지며 계산되며


인자 먼저 계산법은 

1. 10*10 + 5*5

2. 100 + 25

3. 125 

와 같이 계산된다.


예제 1.3

세 숫자중 2개의 큰 숫자를 제곱하여 합하라



예제 1.5

정의대로 계산법과 인자 먼저 계산법에서의 다음 연산의 차이

(define (p) (p))

(define (test x y)

 (if (= x 0)

 0 y))

Then he evaluates the expression 

(test 0 (p))







1.1.7 - Square Roots by Newton's Method


어떤 수 x 의 제곱근을 구하는 방법으로, 뉴튼법이 있다.

일단 어떤 적당한 값으로 나눠보고 (x / guess) , 이 값을 제곱했을때 값과 x 의 차이가 오차범위 이내이면 이 값을 제곱근으로 리턴하고,

그렇지 않으면 나눈 결과 값과 추측값의 평균값을 구한다. ( (x / guess + guess) / 2 ) 

이 평균값을 다시 추측값으로 하여 전 과정을 오차범위 이내일때까지 반복한다.

-> 장황하지만 간단히 얘기해서, 어떤 값으로 나눠본 결과가 터무니 없으면 그 어떤값과의 평균값으로 보정하는 과정을 반복하는 것이다.

-> 정확한 값이라면 (x/guess + guess) / 2 는 

와 같이 전개되어 결국 원하는 값이 된다.


스칼라로 표현하면

def newton = {

def sqrt(x: Int) = {

def iter_sqrt(guess: Float, x: Int): Float = {

def improve(guess: Float): Float = {

println("guess : " + (x / guess + guess)/2)

(x / guess + guess)/2

} // improve

def good_enough(guess: Float):Boolean = {

def pow(a: Float) = {

a*a

}

if (Math.abs(pow(guess) - x) < 0.001) true else false

}

if (good_enough(guess))

guess

else

iter_sqrt(improve(guess), x)

} //iter_sqrt

iter_sqrt(1, x)

}

sqrt(2)

}                                             //> newton: => Float

newton                                    //> guess : 1.5

                                                  //| guess : 1.4166667

                                                  //| guess : 1.4142157

                                                  //| res3: Float = 1.4142157

와 같이 된다.



예제 1.6  new-if 로 scheme 의 if cond 를 다음과 같이 직접 작성했다.

(define (new-if predicate then-clause else-clause)

(cond (predicate then-clause)

(else else-clause))) 

만약 이 new-if 를 newton's method 에 적용한다면 ?




예제 1.7 뉴튼법은 큰 숫자나 작은 숫자엔 적용하기 어렵다. 그 예를 들어 과정을 설명하고, 개선해보라.


예제 1.8  세제곱근을 구하는 공식은 (x/y^2 + 2y)/3 과 같다. 작성해보아라.