BLOG ARTICLE Announce/Chapter.1 | 19 ARTICLE FOUND
- 2010.12.10 7, 8일차
- 2010.12.07 6일차
- 2010.12.06 5일차
- 2010.12.02 4일차 - 1.2.3 ~ 1.2.4 - 요약
- 2010.11.30 3일차 - 1.2 - 요약
- 2010.11.30 4일차
- 2010.11.29 3일차
- 2010.11.25 2일차
- 2010.11.18 1일차
시간: 2010.12.9 PM 6:30
<복습>
<복습>
범위: 1.2.5 ~ 1.2.6
발표: 유승근
<진도>
범위: 1.2.6 연습문제
발표: 정다정
시간: 2010.12.7 PM 6:30
<복습>
<복습>
범위: 1.2.3 ~ 1.2.4
발표: 유훈종
<진도>
범위: 1.2.5 ~ 1.2.6
발표: 이준
1.2.3 프로세스가 자라나는 정도
- 연습문제 1.16
- 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번으로 줄였다)
(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))
;; 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 PM 6:30
<복습>
범위: 1.1.7 ~ 1.1.8
발표: 이준
<진도>
범위: 1.2.1 ~ 1.2.2
발표: 유승근
시간: 2010.11.25 PM 6:30
<복습>
범위: 1.1.1 ~ 1.1.6
발표: 전현철
<진도>
범위: 1.1.7 ~ 1.1.8
발표: 유훈종
- 시간: 2010.11.23 PM 6:30
- 범위: 1.1.1~1.1.4 ( + 1.1.5~1.1.6 )
- 발제: 정다정 ( + 유승근 )