Microsoft PowerPoint - IntroAlgDs-10-4.pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - IntroAlgDs-10-4.pptx"

ゆりからぶり
5 years ago
Views:

1 アルゴリズムとデータ構造入門-１ 2010年10月12日 Procedures as Black Black- 大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野 Linear Recursion and Iteration 復習 htt://winnie.kuis.kyoto-u.ac.j/~okuno/lecture/10/introalgds/ okuno@i.kyoto-u.ac.j okuno@nue.org y j g Tree Recursion 復習 TAの居室は TA の居室は10 10号館４階奥乃１研２研号館４階奥乃１研２研 Exonentiation Ex ti ti M1) 奥乃研音楽G M1) 奥乃研ロボット聴覚G 1 手続きが再帰的とは構文上から定義続きが的構文上から定義構定義自分の中で自分を直接間接に呼び出す再帰的手続きの実行再帰プロセスで実行反復プロセスで実行線形再帰プロセスは線形反復プロセスに変換可能 tail recursion 末尾再帰的末尾再帰的 tail 再帰プロセスでは deferred oeration用にプロセスを保持する必要ありスペスペース量が余分に必要ス量が余分に必要 Scheme のループ構造はsyntactic sugar do, reeat, until, for, while 13 条件式の一般形; cond は特殊形式 (secial form) (cond (<1> <e11> <e <e1m>) 2 適用順序作用順序 Alicative order 今まで見てみた置換モデルの評価順序今まで見てみた置換モデルの評価順序別の順序: 正規順序 normal-order 仮パラメータをすべて置換してから簡約する (f 5) ((sum-of-squares ( a 1) (* a 2)) 5) (sum-of-squares (sum of squares ( 5 1) (* ( 5 2)) (( (square x) (square y)) ( 5 1) (* 5 2)) ( (square ( 5 1)) (square (* 5 2)) ( ((* x x) ( 5 1)) ((* x x) (* 5 2)) ( (* ( 5 1) ( 5 1)) (* (* 5 2) (* 5 2))) ( (* ( 6 6) (* ( 10 10)) ( ) 136 2回同じものを計算絶対値をcase analysis (場合分けで定義 cond if の実行は cond, の実行は置換モデルで特別扱い form 特殊形式 Secial (<P2> <e21> <e2k>) 1. (define (abs x) (<n> <en1> <en>) ) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x)) )) 式の対 (<> <e> <e>) : 節 clause <> : 述語 redicate 述語の値 true #t か false #f. 2.(define (abs x) 3.(define (abs x) <e> : 帰結式 consequent exression 特別の<>: else #t を返す節の評価はｐ節の評価はが#tなら<e> >が順に評価される. が順に評価される一旦述語が#tを返すとそれ以降の節は評価されない 14 (cond ((< x 0) (- x)) ((>= x 0) x) )) ((> (cond ((< x 0) (( x)) (else x) )) 15 if : Syntax sugar 糖衣 (or (> x 0) (= x 0)) 4.(define (abs x) (if (< x 0) (- x) ( x )) 16

2 (and <e 1 > <e n >) 論理積 ( 左から評価 ) 1 n (or <e 1 > <e n >) 論理和 ( 左から評価 ) (not <e>) 論理否定例 : 5 < x < 10 (and (> x 5) (< x 10)) (define (>= x y) (or (> x y) (= x y)) ) (define (>= x y) (not (< x y)) ) 17 式 ( 演算子被演算子 ) oerator oerands 式の記法 3 前置記法 (refix notation, Pollish notation, ポーランド記法 ) 3 * 4 5 中置記法 (infix notation) 3 (4 * 5) 後置記法 (ostfix notation, reverse Pollish notation 逆ポーランド記法) * 木表現はどれも同じ木の辿り方前順走査 (re-order traversal) ノード左部分木右部分木 3 * 4 5 間順走査 (in-order tr.) 左部分木ノード右部分木 * 後順走査 (ost-order tr.) 左部分木右部分木ノード * Java プログラムのデモ htt://winnie.kuis.kyoto-u.ac.j/~okuno/lecture/10/introalgds/ Examle: Square Roots by Newton's Procedures as Black Linear Recursion and Iteration Tree Recursion Exonentiation 21 is the such that y and x y x y (define (sqrt-iter x) (if (good-enough? x) (sqrt-iter (imrove x) x) )) (define (imrove x) (average (/ x )) ) (define (average x y) (/ ( x y) 2) ) 2 0 (define (good-enough? x) (< (abs (- (square ) x)) 0.001) (define (sqrt x) (sqrt-iter 1.0 x)) 22 is the such that y and x y x 2 y 0 (define (imrove x) (average (/ x )) ) (sqrt 2.0) (sqrt-iter ) (sqrt-iter ) (sqrt-iter ) (sqrt-iter ) (sqrt-iter ) x/gu uess s x 宮田君による 23

3 (define (sqrt x) q 1.0 x) ) (sqrt-iter と定義すれば (sqrt 9) Procedures as Black Black- (sqrt ( )) Linear Recursion and Iteration Tree Recursion (sqrt ( (sqrt 2) (sqrt 3))) (sqrt (sqrt 1000)) Exonentiation Ex ti ti Square の定義 Sqrtの手続き分解手続き抽象化 1.内部実装(imlementation)の隠蔽 (define (square x) (* x x)) (define (square x) (ex (double (log x))) ) (define (double x) ( x x)) sqrt 外部からは隠蔽 sqrt-iter sqrt iter 2.局所名(local names)の隠蔽 good-enough square abs x2 e 2 ln x (define (square x) (* x x)) (define (square y) (* y y)) imrove average b bound d (define (sqrt-iter x) 束縛 (if (good-enough? (good enough? x) (sqrt-iter (sqrt iter (imrove x) x) )) (define (good-enough? x) (< (abs (( (square ) x)) ) 001) (define (sqrt x) (define (good-enough? ) (< (abs (- (square ) x)) 0.001) ) (define (imrove ) (average ( g g ( (/ x g )) )) ) (define (sqrt-iter ) (if (good (good-enough? enough? ) (sqrt-iter (sqrt iter (imrove )) )) (sqrt-iter 1.0) ) (define (good-enough? v target) (< (abs (- (square v) target)) 0.001) 束縛変数仮パラメータは手続きで束縛自由変数束縛 catureされていない束縛な自由変数有効範囲 scoe 変数の束縛されている式の範囲 29 静的有効範囲 lexical scoing 31

4 ハノイの塔を解こう. 1. 一度には1 枚の円盤しか動かせない. 2. 小さい円盤の上には大きな円盤は置けない. (define (move-tower size from to extra) (cond ((= size 0) #true) (else (move-tower (- size 1) from extra to) (rint-move from to) (move-tower (- size 1) extra to from)) )) (define (rint-move from to) (newline) (dislay move to disk from ) (dislay from) (dislay to ) (dislay to) ) Java で実行 32 (define (solve-tower-of-hanoi size from to) (move-tower size from to (- 6 from size)) ) 33 n 1, if m 0 Ack ( m, n ) Ack ( m 1,1), if n 0 Ack( m 1, Ack( m, n 1)), otherwise (define (ack m n) (cond ((= m 0) ( n 1)) ((= n 0) (ack (- m 1) 1)) (else (ack (- m 1) (ack m (- n 1)) )))) (ack 0 2) Ackermann (ack 1 2) (ack 2 2) (ack 3 2) Ackermann 関数は線形再帰ではない! Ackermann 関数のファイルを作成せよ. ack.scm 2. Ackermann 関数を実行し, 出力結果を求めよ. (ack 0 2), (ack 1 2), (ack 2 2), (ack 3 2) 3. 教科書練習問題 Ex Program ファイルとレポート (df) を SICP-4@zeus.kuis.kyoto-u.ac.j に送付 5. 随意次の一般式を求めよ. 理由, 計算過程明記のこと. (ack 0 n) n1,(ack 1 n)?, (ack 2 n)?, (ack 3 n)?, (ack 4 n)? (otherwise 回答は減点 ) ドルの両替の方法は何通り? 2. 50セント (half dollar),25 セント (quarter),10 セント (dime), 5セント (nickel), 1セント (enny) 3. 一般化 : 分割数を求める 40 使える硬貨をある順番で並べておくと n 種類の硬貨で金額 a の両替の場合の数は 1. 先頭の種類を除いたすべての硬貨を使って金額 a を両替する場合の数 2. 先頭の種類の硬貨 ( 額面 d) とすると,a-d の額を全 n 種の硬貨を使って両替する場合の数 3. 初期値 : a=0 の時 1,a<00 の時かn=0 の時 0 分割統治法 (divide-and-conquor) 41

(define (count-change 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

5 (define (count-change 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) )) 43 c i1 s (define (adder x y c) (define (carry x y c) (if (or (and (= x 1) (= y 1)) (and (= y 1) (= c 1)) (and (= c 1) (= x 1)) ) 1 0 )) (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 0) (if (= y 0) z (if (= z 0) 1 0)) (if (= y 0) (if (= z 0) 1 0) z) )) c i (carry, 桁上げ ) x y 44 What is this instrument? タイガー計算機 Procedures as Black Linear Recursion and Iteration Tree Recursion htt:// Exonentiation 46 R(n) はステップ数あるいはスペース量 For all n > n 0 R(n) が (f(n)) 上下限 k1 f ( n) R( n) k 2 f ( n) R(n) が (f(n)) R ( n ) k f ( n ) 上限 R ( n ) k f ( n ) 下限 R(n) が (f(n)) 47 (1) : constant growth 25 (n) : linear growth (b n ) : exonential growth (log ( g n) ) : logarithmic growth 20 A 15 (n m ) : ower law growth 10 B 下記はどの曲線? 1. y=x 2. y = x 2 3. y=logx 4. y = x log x C D

6 トップダウン (to-down) 式で計算線形再帰 (define (factorial n) (if (<= n 0) 1 (* n (factorial (- n 1))) )) Procedures as Black Linear Recursion and Iteration Tree Recursion Exonentiation 49 ボトムアップ (bottom-u) 式で計算線形反復 (define (fact n) (define (iter roduct counter) (if (> counter n) roduct (iter (* counter roduct) ( counter 1) ))) (iter 1 1) ) 50 手続き再帰型 (factorial n) 繰り返し型 (fact n) テーブル参照型 fact テーブル参照型 fact ステップ数各手続きが呼ばれた回数スペース遅延演算の個数 n n! (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else ( (fib (- n 1)) (fib (- n 2)) )))) トップダウン (to-down) 式に計算木構造再帰 (define (fib-iter n) (define (iter a b count) (if (= count 0) b (iter ( a b) a (- count 1)) )) (iter 1 0 n) ) ボトムアップ (bottom-u) 式に計算 - 線形再帰だが線形反復プロセス 57 練習問題 : 表を埋めてください手続き再帰型 (fib n) 繰り返し型 (fib-iter n) テーブル参照型 fib ステップ数各手続きが呼ばれた回数スペースス遅延演算の個数 Procedures as Black Linear Recursion and Iteration Tree Recursion テーブル参照型 fib n fib(n) Exonentiation 65

7 1.2.4 Exonentiation ( 冪乗 ) (define (ext b n) (if (= n 0) 1 (* b (ext b (- n 1))) )) Linear recursive rocess (n) stes, (n) sace (define (ext b n) (define (iter counter roduct) (if (= counter 0) roduct (iter (- counter 1) (* b roduct)) )) (iter n 1) ) Linear iterative rocess (n) stes, (1) sace b n =b b* * b =b* c = c Exonentiation (define (fast-ext b n) (cond ((= n 0) 1) ((even? n) (square (fast-ext b (/ n 2)))) (else (* b (fast-ext b (- n 1))) )) (define (even? n) (= (remainder n 2) 0) ) recursive rocess (log n) stes, (log n) sace 67 Exonentiation ( べき乗 ) [Knuth: Comuter Algorit [Knuth: Comuter Algorithms] Power Tree [Knuth: Comuter Algorithms] X より 2 進数を 4 回左シフト 1. まず,1 を SX,0 を S S で置換 2. 次に, 先頭の SX を除く. 3. 得られた S と X を Square x をかけると読む. 例 : X SX S SX SX SX 2. SSXSXSX 3. X 2 X 4 X 5 X 10 X 11 X 22 X

Microsoft PowerPoint - IntroAlgDs pptx

Microsoft PowerPoint - IntroAlgDs pptx アルゴリズムとデータ構造入門 -4 202 年 0 月 23 日大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野 http://wiie.kuis.kyoto-u.ac.jp/~okuo/lecture/0/itroalgds/ okuo@i.kyoto-u.ac.jp,okuo@ue.org TAの居室は文学部東館 4 階奥乃研,2 研 if mod( 学籍番号の下 3 桁,3)