1.2 프로시저와 프로세스
1.2.1. 되돌거나 반복하는 프로세스
ex) 선형 재귀 프로세스
(define (factorial n) => (factorial 4)
(if (= n 1) (* 4 (factorial 3) )
1 (* 4 (* 3 (factorial 2) )
(* n (factorial (- n 1) ) ) ) ) (* 4 (* 3 (* 2 (factorial 1) )
(* 4 (* 3 (* 2 1 )
(* 4 (* 3 2)
(* 4 6)
== 24
선형 반복 프로세스
(define (factorial n) => (factorial 4)
(define (iter product counter) (iter 1 1 4)
(if (> counter n) (iter 1 2 4)
product (iter 2 3 4)
(iter (* counter product) (iter 6 4 4)
(+ counter 1) ) ) ) (iter 24 5 4)
(iter 1 1) )
* 되도는 프로시저: 자기 자신을 불러쓴다.
되도는 프로세스: 계산을 반복한다.
1.2.2. 여러 갈래로 되도는 프로세스
피보나치 수열
ex)
(define ( (fib n) // Fib(n)에 비례하여 자라남
( (= n 0) 0)
( (= n 1) 1)
(else (+ (fib (- n 1) )
(fib (- n 2) ) ) ) ) )
(define (fib n) // n에 비례하여 자라남
(fib-iter 1 0 n) )
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1) ) ) )
연습 : 돈 바꾸는 방법
ex) 1달러를 50센트, 25센트, 10센트, 5센트, 1센트 동전으로 바꾸는 법
(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-of-coins)
(cond ( (= kinds-of-coins 1) 1)
( (= kinds-of-coins 2) 5)
( (= kinds-of-coins 3) 10)
( (= kinds-of-coins 4) 25)
( (= kinds-of-coins 5) 50) ) )
1.2.3. 프로세스가 자라나는 정도
자람 차수
==> 1.2.1 되도는 프로세스 : 계산 단계가 R(n)만큼 늘어나고 기억공간도 R(n)으로 늘어났다.
반복하는 프로세스 : 계산 단계가 R(n)만큼 늘어났지만 기억공간은 R(1)으로 고정됐다..
1.2.4. 거듭제곱
(define (expt b n)
(if (= n 0) =>선형 재귀 프로세스
1
(* b (expt b (- 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) ) ) )
(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.2.5. 최대 공약수
유클리드 알고리즘
ex) 206과 40의 최대 공약수는?
GCD(206, 40) = GCD(40, 6) (define (gcd a b)
= GCD(6, 4) => (if (= b 0)
= GCD(4, 2) a
= GCD(2, 0) (gcd b (remainder a b) ) ) )
= 2
// 알고리즘의 중요성: 컴퓨터가 확실히 빠른 연산을 하지만 그 전에 인간의 수학적,논리적 알 고리즘이 뒷받침되지 않으면 컴퓨터가 할 수 있는 것이 없다.
* 라메의 정리: 유클리드의 알고리즘으로 GCD를 구하는 데 k단계를 거치는 경우, 두 수 가운 데 작은 수는 k번째 피보나치 수보다 크거나 같아야 한다.
==> 유클리드 알고리즘의 자람차수를 구하는 데 사용
gcd 프로시저 중 작은 값을 n.
계산 단계가 k단계 ==> n >= Fib(k)~pi^k / root 5
k에 관한 식으로 정리
==> log ((root 5)*n) >= k
= R(log n)
1.2.6. 연습 : 소수찾기
약수 찾기
(define (prime? n)
(define (smallest-divisor)
(find-divisor n 2) )
(define (find-divisor test-divisor)
(cond ( (> (square test-divisor) n) n)
( (divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1) ) ) ) )
(define divides? a b)
(= (remainder b a) 0) )
(= n (smallest-divisor n) ) )
페르마 검사: n이 소수고, n > a > 0 (a는 정수)라면, a^n은 a modulo n으로 맞아떨어진다.
(a modulo n = a % n)
(define (expmod base exp m)
(cond ( (= exp 0) 1)
( (even? exp)
(remainder (square (expmod base (/ exp 2) m) )
m) )
(else
(remainder (* base (expmod base (- exp 1) m) )
m) ) ) )
// 거듭제곱된 값을 modulo하는 프로시저
이용된 것: 1.2.4의 3번째 식
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a) )
(try-it (+ 1 (random (- n 1) ) ) ) )
(define (fast-prime? n times)
(cond ( (= times 0) true)
( (fermat-test n) (fast-prime? n (- times 1) ) )
(else false) ) )
//여기서 배운 점: 프로세스를 만들 때 문장을 분석하는 것이 중요하다!!
페르마 검사와 식을 비교해서
a modulo n == 첫번째식
으로 맞아떨어진다 == 두번째식
n을 설정 == 세번째식
확률을 바탕으로 하는 알고리즘
사실상 페르마검사는 완벽한 소수 검사법이 아니다. 하지만 확률적으로 꽤나 괜찮은 검사법으로 인정받고 있기 때문에 쓰이고 있다.(과학과 공학의 차이)
1.3 차수 높은 프로시저로 요약하는 방법
=> 보통의 데이터처럼 사용되는 프로시저
1.3.1. 프로시저를 인자로 받은 프로시저
ex)
(define (<name> a b)
(if (> a b)
0 ==> 수열의 덧셈(시그마)의 틀이 되는 프로시저
(+ (<term> a)
(<name> (<next> a) b) ) ) )
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b) ) ) ) ==> 적분
(define (integral f a b dx)
(define (add-dx x) (+ x dx) )
(* (sum f (+ a (/ dx 2.0) ) add-dx b)
dx) )
1.3.2. lambda로 나타내는 프로시저
//특별한 형태
(lambda (<formal-parameter>) <body>)
ex)
(define (plus4 x) (+ x 4) ) == (define plus4 (lambda (x) (+ x 4) ) )
//프로시저 안에 임시로 쓰고 싶은 프로시저가 있을 때 사용하면 유용할 듯
let으로 갇힌 변수 만들기
(let ( (<var1> <exp1>) (define (f x y)
(<var2> <exp2>) ==> (let ( ( a (+ 1 (* x y) ) )
. . . (b (- 1 y) ) )
(<varn> <expn>) ) (+ (* x (square a) )
<body> ) (* y b)
(* a b) ) ) )
( (lambda (<var1>. . .<varn>) (define (f x y)
<body>) ==> (let ( (a (+ 1 (* x y) ) )
<exp1>) (b (- 1 y) ) )
... (+ (* x (square a) )
<expn>) (* y b)
(* a b) ) ) )
1.3.3. 일반적인 방법을 표현하는 프로시저
이분법으로 방정식의 근 찾기
=어떤 너비를 반으로 나누는 방법
(define (search f neg-point pos-point) ) )
(let ( (midpoint (average neg-point pos-point) ) )
(if (close-enough? neg-point pos-point)
midpoint
(let ( (test-value (f midpoint) ) )
(cond ( (positive? test-value)
(search f neg-point midpoint) )
( (negative? test-value)
(search f midpoint pos-point) )
(else midpoint) ) ) ) ) )
(define (close-enough? x y)
(< (abs (- x y) ) 0.001) )
(define (half-interval-method f a b)
(let ( (a-value (f a) )
(b-value (f b) ) )
(cond ( (and (negative? a-value) (positive? b-value) )
(search f a b) )
( (and (negative? b-value) (positive? a-value) )
(search f b a) )
(else
error "Values are not of opposite sign" a b) ) ) ) )
함수의 고정점 찾기
(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2) ) tolerance) )
(define (try guess) ) )
(let ( (next (f guess) ) )
(if (close-enough? guess next)
next
(try next) ) ) )
(try first-guess) )
1.3.4. 프로시저를 만드는 프로시저
뉴튼 방법 => f(x) = x - (g(x)/Dg(x))
Dg(x) = (g( x + dx ) - g(x)) / dx (미분)
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx) ) (g x) )
dx) )
(define dx 0.00001)
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ( (deriv g) x) ) ) ) )
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess) )
요약과 일등급 프로시저
일등급 : 가장 제약이 적다
1.변수의 값이 될 수 있다
2.프로시저 인자로 쓸 수 있다.
3.프로시저의 결과로 만들어질 수 있다.
4.데이터 구조 속에 집어넣을 수 있다.
댓글 없음:
댓글 쓰기