Microsoft PowerPoint - IntroAlgDs-05-5.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - IntroAlgDs-05-5.ppt"

くにひとかなり
4 years ago
Views:

1 アルゴリズムとデータ構造入門 25 年月日アルゴリズムとデータ構造入門. 手続きによる抽象の構築.3 Formulating Astractions with Higher-Order Procedures ( 高階手続きによる抽象化 ) 奥乃博. 3,5,7で割った時の余りが各々,2,3という数は何か? 月日本日のメニュー.2.6 Example: Testing for Primality.3. Procedures as Arguments.3.2 Constructing Procedures Using `Lamda'.3.3 Procedures as General Methods.3.4 Procedures as Returned Values 2 Greatest Common Divisors ( 最大公約数 ) ユークリッドの互除法 GCD( ) = GCD(, a mod ) (define (gcd a ) (if (= ) a (gcd (remainder a )) )) 3

2 Chinese Remainder Theorem 連立次合同式 x (mod d ) x 2 (mod d 2 ) x t (mod d t ) の場合 d, d 2, d t が互いに素であれば n = d d 2 d t を法としてただ一つの解があるまず n/d i = n i とおけば d i と n i は互いに素であるから n i x i (mod d i ) の解 x i を求めることができるここで x n x + 2 n 2 x t n t x t (mod n ) とすればこの x は明らかにもとの合同式をすべて満足する 5 Chinese Remainder Theoremの例 x mod 5 は? 3 * 5 * 7 = 5 x (mod 3) x 2 (mod 5) x 3 (mod 7) 35*2 (mod 3) 2* (mod 5) 5* (mod 7) より x mod 5 *35*2 +2*2*+3*5* mod 5 =57 mod 5 52 mod 5 6 Lame の定理 GCD( ) ( ただし < a ) の計算にk step 必要なら Fi(k ) 例えば GCD(m, n) ( ただし n < m ) がk step かかるとすると n Fi(k ) Φ k / 5 n ( 5) φ φ = + Fi( n) 2 5 つまりステップ数は n の対数的に増加 Θ(log n) steps 7 2

3 Order of Growth: Examples 手続き factorial fact-iter テーブル参照型 fact fi fi-iter テーブル参照型 fi ステップ数 Θ() Θ(φ n ) Θ() スペース Θ() Θ() 8 Testing for Primality (define (smallest-divisor n) (find-divisor n 2) (define (find-devisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor ) )) )) (define (divides? a ) (= (remainder a) ) ) (define (prime? n) (= n (smallest-divisor n)) ) Improvement y HGO (define (smallest-divisor n) (find-divisor n 3) (define (find-devisor n test-divisor) (cond ((> (square test-divisor) n) n) ((divides? test-divisor n) test-divisor) (else (find-divisor n (+ test-divisor 2) )) )) (define (divides? a ) (= (remainder a) ) ) (define (prime? n) (if (even? n) 2 (= n (smallest-divisor n)) )) 3

4 The Fermat Test a p- mod p if p が素数 (prime) (define (expmod ase exp m) (cond ((= exp ) ) ((even? exp) (remainder (square (expmod ase (/ exp 2) m)) m) ) (else (remainder (* ase (expmod ase (- exp ) m)) m) )) (define (fermat-test n) (define (try-it a) (= (expmod a n n) a) ) (try-it (+ (random (- n )))) (define (fast-prime? n times) (cond ((= times ) true) ((fermat-test n) (fast-prime? n (- times ))) (else false) )) 2 Proailistic Algorithms( 確率的アルゴリズム ) Carmichael numers: 56, 5, 72, 2465, a 56 =a 2 a a 6 a 2 mod 3, a mod, a 6 mod 7 a 56 mod 56 = 3 * * 7 Fermat s testはエラーの機会を任意に小さくできる proailistic algorithm 必要条件のみ満足 Algorithm: Wilson s test p is a prime precisely when (p-)! - mod p 必要十分条件 3 Discussion: Fermat s or Wilson s?. 単純な素数判定 : 2. Fermat s test: p が素数なら a < p,a (p-) mod p 3. Wilson s test: p が素数である必要十分条件は (p-)! - mod p ちなみに n! ~(2πn) ½ (n/e) n 4 4

5 .3. Procedures as Arguments (define (sum-integers a ) (if (> a ) (+ a (sum-integers (+ a ) )) )) i (define (sum-cues a ) a (if (> a ) (+ (cue a) (sum-cues (+ a ) )) )) i 3 (define (cue x) (* x x x)) a (define (pi-sum a ) (if (> a ) (+ (/. (* a (+ a 2))) (pi-sum (+ a 4) )) )) (define (<name> a ) (if (> a ) (+ (<term> a) (<name> (<next> a) )) )) i 2) a ( i Procedures as Arguments (define (<name> a ) (if (> a ) (+ (<term> a) (<name> (<next> a) )) )) (define (sum term a next ) (if (> a ) i (+ (term a) (sum term (next a)next )) )) (define (inc n) (+ n )) (define (sum-cues a ) (sum cue a inc ) ) (define (identity x) x) (define (sum-integers a ) i+ (sum identity a inc ) ) = next( i) cue( i) f ( i) i i+ 7 Pi-Sum (Pi/8) の計算方法 i = a, πnext πterm ( i ) ( i) (define (pi-sum a ) (define (pi-term x) (/. (* x (+ x 2))) ) (define (pi-next x)(+ x 4) ) (sum pi-term a pi-next ) ) 8 5

6 積分 (integral) の計算方法 ( f ( i) i = a, + Δ x Δ x (define (integral f a dx) (define (add-dx x) (+ x dx)) (* (sum f (+ a (/ dx 2.)) add-dx ) dx )) 9 Ex..3 Product (define (product term a next ) (if (> a ) (* (term a) (product term (next a)next )) )) (define (product-cues a ) (product cue a inc ) ) (define (product-integers a ) (product identity a inc ) ) i+ next( i) i f ( i) i+ 2 i 3 Ex..32 Accumulation (define (sum term a next ) (if (> a ) (+ (term a) (sum term (next a) next )) ) (define (product term a next ) (if (> a ) (* (term a) next( i) (product term (next a) next )) ) (define (<cominer> <name> <term> a <next> ) (if (> a ) <null-value> (<cominer> (<term> a) (<name> <term> (<next> a) <next> )) )) 2 next( i) f ( i) f ( i) 6

7 Ex..32 Accumulation (define (<cominer> <name> <term> a <next> ) (if (> a ) <null-value> (<cominer> (<term> a) (<name> <term> (<next> a) <next> )) )) (define (accumulate cominer null-value term a next ) (if (> a ) null-value (cominer (term a) (accumulate cominer null-value term (next a) next )))) 22 lamda: Anonymous procedure (define (fact n) (if (= n ) (* n (fact (- n ))) )) は次の式と等価 (define fact (lamda (n) (if (= n ) (* n (fact (- n ))) ))) 24 Lamda as anonymous procedure (lamda (x) (+ x 4)) ((lamda (x) (+ x 4)) 5) (define (pi-sum a ) (define (pi-term x) (/. (* x (+ x 2))) ) (define (pi-next x)(+ x 4) ) (sum pi-term a pi-next ) ) (define (pi-sum a ) (sum (lamda (x) (/. (* x (+ x 2)) a (lamda (x) (+ x 4)) )) 25 7

8 Using let to create local variales (define (f x y) (define (f-helper a ) (+ (* x (square a)) (* y ) (* a ) )) (f-helper (+ (* x y)) (- y) )) Local Variales with let (define (f x y) (define (f-helper a ) (+ (* x (square a)) (* y ) (* a ) )) (f-helper (+ (* x y)) (- y) )) (define (f x y) (let ((a (+ (* x y))) ( (- y)) ) (+ (* x (square a)) (* y ) (* a ) ))) (define (f x y) ((lamda (a ) (+ (* x (square a)) (* y ) (* a ) )) (+ (* x y)) (- y) )) (let ((<v > <e >) (<v 2 > <e 2 >) (<v n > <e n >) ) <ody> ) シンタックスシュガー 27 scope of variales (let ((x 7)) (+ (let ((x 3)) (+ x (* x )) ) x) ) (let ((x 5)) (let ((x 3) (y (+ x 2)) ) (* x y) )) Sustition model 28 8

9 scope of variales (let ((x 7)) (+ (let ((x 3)) (+ x (* x )) ) x) ) x = 7 x = 3 -> 33 x = 7 -> 4 (let ((x 5)) (let ((x 3) (y (+ x 2)) ) (* x y) )) x = 5 x = 3 y = 7 -> Procedures as General Methods Finding roots of equations y the half-interval method ( 区間二分法 ) (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)))))) 32 Finding roots of equations y the half-interval method (define (close-enough? x y) (< (as (- x y)).)) (define (half-interval-method f a ) (let ((a-value (f a)) (-value (f ))) (cond ((and (negative? a-value) (positive? -value)) (search f a )) ((and (negative? -value) (positive? a-value)) (search f a)) (else (error "Values are not of opposite sign" a )) ))) L: 開始時の区間長 T: 誤差許容度ステップ数 :Θ(log(L/T)) 33 9

10 Finding fixed points of functions( 不動点 ) X が不動点 f(x) = x (define tolerance.) (define (fixed-point f first-guess) (define (close-enough? v v2) (< (as (- v v2)) tolerance)) (define (try guess) (let ((next (f guess))) (if (close-enough? guess next) next (try next)))) (try first-guess)) 34 Finding fixed points of functions( 不動点 ) (fixed-point cos.) (fixed-point (lamda (y) (+ (sin y) (cos y))) y*y=x y=x/y と書くと Looking for a fix-point of the function y -> x/y (define (sqrt x) (fixed-point (lamda (y) (/ x y)).)) 35 月日本日のメニュー.2.6 Example: Testing for Primality.3. Procedures as Arguments Intermission.3.2 Constructing Procedures Using `Lamda'.3.3 Procedures as General Methods.3.4 Procedures as Returned Values 42

11 What is this instrument? A traditional roller-lader? A traditional inliner skate? Aacus 算盤 ( そろばん ) そろわん 43 Aacus & Binary Adder (2 進加算器 ) c i (carry, 桁上げ ) c i+ x + s y (define (adder x y c) (define (carry x y c) (if (or (and (= x ) (= y )) (and (= y ) (= c )) (and (= c ) (= x )) ) )) (define (sum x y c) (xor x y c) ) (cons (sum x y c) (carry x y c)) ) (define (xor x y z) (if (= x ) (if (= y ) z (if (= z ) )) (if (= y ) (if (= z ) ) z) )) 44 宿題 : 月 7 日午後 5 時締切 lamda を組合わせて手続きをくみ上げる宿題は次の問 : Ex..2,.23,.25,.29,.3,.3,.32,.33,.34,.35. 実行時間の測定は (time (f a)) 45

Microsoft PowerPoint - IntroAlgDs-05-4.ppt

Microsoft PowerPoint - IntroAlgDs-05-4.ppt アルゴリズムとデータ構造入門 2005 年 0 月 25 日アルゴリズムとデータ構造入門. 手続きによる抽象の構築.2 Procedures and the Processes They generate ( 手続きとそれが生成するプロセス ) 奥乃博. TUT Scheme が公開されました. Windows は動きます. Linux, Cygwin も動きます. 0 月 25 日本日のメニュー.2.