1.2.3 프로세스가 자라나는 정도
  • Order of growth, 자람차수 : 입력의 크기에 따라 프로세스가 쓰는 자원양이 자라나는 정도
  • Θ(f(n)), theta of f(n) : n 알맞게 큰값, 그에 대해 처리되는 함수 f(n) 이 있을 때 f(n) 의 theta 만큼 단계 또는 기억 공간이 필요하다는 것을 표기
  • Θ(1)
  • Θ(n), Θ(2n), Θ(100n) 과 같이 단순상수는 큰 영향이 없음 (간추려 말할 수 있다). 즉, 자람 차수는 프로세스가 쓰는 자원 양을 어림잡아 나타내는 것일 뿐이다.
  • Θ(n^2) 등등의 형을 띄는 단계로 표현 할 수 있다.
  • 로그,logarithmic 자람 차수 Θ(log n) 띄는 알고리즘을 보자.

- 연습문제 1.15
;;EXERCISE 1.15
(define (cube x) (* x x x))

(define (p x) 
  (display "; call p\n")
  (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
   (if (not (> (abs angle) 0.1))
       angle
       (p (sine (/ angle 3.0)))))
  • "충분히 작은 각"을 만족하는 상황을 식으로 풀어보면
  • -0.1 <= a(1/3)^n <= 0.1
  • 위 식을 정리하면 (log 표기를 정확히 어떻게 해야하는지 모르겠네요;;)
  • n = log(3, 10 * a)


1.2.4 거듭제곱
같은 수를 여러번 곱하는 (거듭제곱) 문제의 재귀 규칙을 간단히 보면,
  • b^n = b * ( b ^ (n - 1) )
  • b^0 = 1
이 규칙에 따른 프로시저는 아래와 같이 계산단계, 기억공간 모두 Θ(n)
;; Linear recursion
;; Θ(n), Θ(n)
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))
이를 되도는 프로세스로 표현하면 각각 Θ(n), Θ(1) 만큼 사용한다.
;; Linear iteration
;; Θ(n), Θ(1)
(define (expt b n)
  (expt-iter b n 1))

(define (expt-iter b counter product)
  (if (= counter 0)
      product
      (expt-iter b
                (- counter 1)
                (* b product)))) 
하지만 단계를 절반씩 잘라나가는 아래 규칙을 참조하면 log n 단계로 줄일 수 있을 것이다.
(8번 곱해야할 과정을 3번으로 줄였다)
  • b^2 = b * b
  • b^4 = (b^2 * b^2)
  • b^8 = (b^4 * b^4)

규칙을 다듬어서 지수 n 이 짝수, 홀수일 경우로 나누어 생각하면 아래의 프로시저를 생각할 수 있다.
;; Logarithmic iteration
(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

(define (even? n)
  (= (remainder n 2) 0))

- 연습문제 1.16
;; EXERCISE 1.16
(define (proc-expt b n)
  (define (iter b n a)
    (cond ((= n 0) a)
          ((even? n) (iter (square b) (/ n 2) a))
          (else (iter b (- n 1) (* a b)))))
  (iter b n 1)
)

- 연습문제 1.17
;; EXERCISE 1.17
(define (custom-mult a b)
  (if (= b 0)
      0
      (+ a (custom-mult a (- b 1)))))

(define (double x)
  (* x 2))
(define (halve x)
  (/ x 2))

(define (fast-mult a b)
  (cond ((or (= a 0) (= b 0)) 0)
        ((= b 1) a)
        ((even? b) (double (fast-mult a (halve b))))
        (else (+ a (fast-mult a (- b 1))))))

; (fast-mult 3 5)
; (+ 3 (fast-mult 3 4))
; (+ 3 (double (fast-mult 3 2)))
; (+ 3 (double (double (fast-mult 3 1))))
; (+ 3 (double (double 3)))
; (+ 3 (double 6))
; (+ 3 12)

- 연습문제 1.18
;; EXERCISE 1.18
(define (proc-mult b n)
  (define (iter b n a)
    (cond ((= n 0) a)
          ((even? n) (iter (double b) (halve n) a))
          (else (iter b (- n 1) (+ a b)))))
  (iter b n 0)
)
신고

1.2 프로시저와 프로세스

;
;; 어떤 문제를 풀기 위해 어떤 식으로 프로그래밍 언어를 써야 하는지 모르는 상태다.
;; 어떤 프로시저를 정의해야 하는데 프로시저를 돌릴 때 어떤 결과가 나오는지 미리 그려낼 줄 아는 경험 부족한 상태.
;; 프로시저: 한 컴퓨터 프로세스가 어떻게 나아가는지 밝힌 것.
;; 프로시저가 만들어내는 프로세스의 몇가지 꼴(shape)의 보기를 들것이다.
;

1.2.1 되돌거나 반복하는 프로세스

;
;; 되도는 프로세스 recursion
;;  - 연산을 바로 수행하지 못하고 뒤로 미루는(deferred operation) 모양
;; 반복하는 프로세스 iterative
;;  - 상태변수 존재. 계산의 크기가 늘어나지 않는다.
;; 되도는 프로세스와 되도는 프로시저
;;  - 프로시저는 되도는 모양이더라도(자신을 다시 호출) 프로세스는 그렇지 않을 수 있다. - linera iterative process
;; tail recursion : 꼬리에서 자기 자신을 다시 호출하면서 recursive process가 안되도록 하는 것.
;;  - http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Tail-recursive_functions

;; fact(n) = n * (n -1) * (n-2) * ... * 2 * 1
(define (fact1 n)
  (if (= n 1)
      1
      (* n (fact1 (- n 1)))))

;; recursive process
;; (fact1 4)
;; (* 4 (fact 3))
;; (* 4 (* 3 (fact 2)))
;; (* 4 (* 3 (* 2 (fact 1))))
;; (* 4 (* 3 (* 2 1)))
;; (* 4 (* 3 2))
;; (* 4 6)
;; 24

;; iterative process
;; product < counter * product
;; counter < counter - 1
(define (fact2 n)
  (define (iter p c)
    (if (= c 1)
      p
      (iter (* p c) (- c 1))))
  (iter 1 n))

;; (fact2 4)
;; (iter 1 4)
;; (iter 4 3)
;; (iter 12 2)
;; (iter 24 1)
;; 24

;; ex 1.9

;; (+ 4 5)
;; (inc (+ 3 5))
;; (inc (inc (+ 2 5)))
;; (inc (inc (inc (+ 1 5))))
;; (inc (inc (inc (inc (+ 0 5)))))
;; (inc (inc (inc (inc 5)))))
;; (inc (inc (inc 6)))
;; (inc (inc 7))
;; (inc 8)
;; 9

(define (inc a)
  (+ a 1))

(define (dec a)
  (- a 1))

(define (plus-1 a b)
  (if (= a 0)
      b
      (inc (plus-1 (dec a) b))))

;; (plus-1 2 3)
;; (inc (plus-1 1 3))
;; (inc (inc (plus-1 0 3)))
;; (inc (inc 3))
;; (inc 4)
;; 5

(define (plus-2 a b)
  (if (= a 0)
      b
      (plus-2 (dec a) (inc b))))
;; (plus-2 2 3)
;; (plus-2 1 4)
;; (plus-2 0 5)
;; 5

;; ex 1.10
;; 애커만 함수 http://en.wikipedia.org/wiki/Ackermann_function
;; primitive recursive function은 아니지만 total computable function
;; primitive recursive function은 항상 total computable function이다.
;; A(x, y)
;; 0                      if y = 0
;; 2 * y                  if x = 0
;; 2                      if y = 2
;; A(x - 1, A(x, y - 1))
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

;; (A 0 n) : (* 2 n)
;; (A 1 n) : (exp 2 n)
;; (A 2 n) : n = 1 이면 1
;;           n > 1 이면 (exp 2 (exp 2 (exp 2 ... 2))) -> n번 반복
;; (A 3 n) : n = 1 이면 1
;;           n > 1 이면 ???
;

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

;
;; 피보나치 수열 f(n) = f(n-1) + f(n-2), f(0) = 0, f(1) = 1
;;
;; 0 -> 0
;; 1 -> 1
;; recursive process
(define (fib1 n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib1 (- n 1)) (fib1 (- n 2))))))

;; fib1 -> n -> pi^n / root(5)

;; f(n) = f(n-1) + f(n-2)
;; iterative process
(define (fib2 n)
  (define (iter a b c)
    (if (= c 0)
        b
        (iter (+ a b) a (- c 1))))
  (iter 1 0 n))
;; (fib 4)
;; (iter 1 0 4)
;; (iter 1 1 3)
;; (iter 2 1 2)
;; (iter 3 2 1)
;; (iter 5 3 0)
;; 3

;; 돈 바꾸는 방법 ??? - review 할 때 다시 얘기해 봅시다.
;; 받은 돈을 동전으로 바꾸는 방법
;; 10 센트
;; 1 센트 * 10
;; 5 센트 * 2
;; 5 센트 + 1 센트 * 5

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount (- kinds-of-coins 1))
                 (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))

(define (first-denomination kinds)
  (cond ((= kinds 1) 1)
        ((= kinds 2) 5)
        ((= kinds 3) 10)
        ((= kinds 4) 25)
        ((= kinds 5) 50)))

;; ex 1.11
(define (F1 n)
  (if (< n 3)
      n
      (+ (F1 (- n 1)) (* (F1 (- n 2)) 2) (* (F1 (- n 3)) 3))))

;; a < a + 2*b + 3c
;; b < a 
;; c < b
(define (F2 n)
  (define (iter x y z count)
    (if (< count 3)
        x
        (iter (+ x (* y 2) (* z 3)) x y (- count 1))))
  (iter 2 1 0 n))

;; f(0) = 0
;; f(1) = 1
;; f(2) = 2
;; f(3) = f(2) + 2f(1) + 3f(0) = 4

;; ex 1.12
;; pascal's triangle,
;; p(r, c) = p(r-1, c-1) + p(r-1, c)
;; p(r, 1) = 1, p(r, r) = 1
(define (pt r c)
  (cond ((or (= c 1) (= r c)) 1)
        ((or (< c 0) (< r 0) (> c r)) 0)
        (else (+ (pt (- r 1) (- c 1))
                 (pt (- r 1) c)))))
;
저작자 표시 비영리
신고

  • 맞바꿈 방법으로 답이 나오지 않는 경우가 있다. (2010-11-30)
  • 3.5절에서는 차례열의 표현 방식을 이리저리 바꾸어서, 끝없는 차례열을 나타낼 수 있게끔 신호 처리 패러다임의 표현력을 늘려 보자. (2011-01-18)

신고

티스토리 툴바