Microsoft PowerPoint - IntroAlgDs pptx

Size: px

Start display at page:

Download "Microsoft PowerPoint - IntroAlgDs pptx"

あかりさだい
4 years ago
Views:

1 アルゴリズムとデータ構造入門年 0 月 23 日大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野 okuo@i.kyoto-u.ac.jp,okuo@ue.org TAの居室は文学部東館 4 階奥乃研,2 研 if mod( 学籍番号の下 3 桁,3) 0 if mod( 学籍番号の下 3 桁,3) if mod( 学籍番号の下 3 桁,3) 2 数学的準備 --6 Coditioal Expressios ad Predicates --7 Example: Square Roots by Newto's Method --8 Procedures as Black-Box Abstractios.2. Liear Recursio ad Iteratio ( 復習 ).2.2 Tree Recursio ( 復習 ).2.3 Growth of Order.2.4 Expoetiatio 2! は! 2 e e ただしスターリング級数は! 2 e 対数をとると l! l l(2) for >>0 7 l! l 3

2 Fiboacci 数の漸化式 F0 0 ビネの公式 F F F 2 F F 黄金比 (Golde Ratio) 帰納法で証明せよ.. = 0, を検証 2. k のとき成立を仮定し,k+ で成立を示す Fiboacci 数の漸化式 F 0 0 F F 2 F F. 線形差分方程式の解法 ) 特性方程式を作成解を求める. 2) その根をα,βとすると元の差分方程式の解は F C D と表せるただし, C, D は定数 3) 初期値等から定数項の値を求める 2. 母関数 (geeratig fuctio) の解法 C(): に対して fib の呼ばれる回数 C(0)=C()= 2 に対して C()=C(-)+C(-2)+ C(2)=3, C(3)=5, C(4)=9, C(5)=5, 一般に C(k) > 2 k/2 C() を求める. F()=C()+ とおくと 2. F()=F(-)+F(-2) for 2 3. F(0)=2, F()=2 2 2

3 2 に対して C()=C(-)+C(-2)+ F()=C()+ とおくと F()=F(-)+F(-2) for 2 F(0)=2, F()=2 さあ解いてみてください is the such that ad x y y x y (defie (sqrt-iter guess x) (if (good-eough? guess x) guess (sqrt-iter (improve guess x) x) )) (defie (improve guess x) (average guess (/ x guess)) ) (defie (average x y) (/ (+ x y) 2) ) (defie (good-eough? guess x) (< (abs (- (square guess) x)) 0.00) (defie (sqrt x) (sqrt-iter.0 x)) is the such that y ad x y x 2 y 0 (defie (improve guess x) (average guess (/ x guess)) ) (sqrt 2.0) (sqrt-iter.0 2.0) (sqrt-iter.5 2.0) (sqrt-iter ) (sqrt-iter ) (sqrt-iter ) x/guess guess x 宮田君による 28 3

4 (defie (sqrt x) (sqrt-iter.0 x) ) と定義すれば, (sqrt 9) (sqrt ( )) (sqrt (+ (sqrt 2) (sqrt 3))) (sqrt (sqrt 000)) 30 Sqrt の手続き分解外部からは隠蔽 sqrt sqrt-iter 手続き抽象化 good-eough improve square abs average 32 Square の定義. 内部実装 (implemetatio) の隠蔽 (defie (square x) (* x x)) (defie (square x) (exp (double (log x))) ) (defie (double x) (+ x x)) 2. 局所名 (local ames) の隠蔽 (defie (square x) (* x x)) (defie (square y) (* y y)) x e 2 2 l x 33 4

00) 束縛変数 : 仮パラメータは手続きで束縛自由変数 : 束縛 capture されていない有効範囲 (scope) 変数の束縛されている式の範囲 34 (defie (sqrt x) (defie (good-eough? guess) (< (abs (- (square guess) x)) 0.

5 boud ( 束縛 ) (defie (sqrt-iter guess x) (if (good-eough? guess x) guess (sqrt-iter (improve guess x) x) )) (defie (good-eough? guess x) (< (abs (- (square guess) x)) 0.00) (defie (good-eough? v target) (< (abs (- (square v) target)) 0.00) 束縛変数 : 仮パラメータは手続きで束縛自由変数 : 束縛 capture されていない有効範囲 (scope) 変数の束縛されている式の範囲 34 (defie (sqrt x) (defie (good-eough? guess) (< (abs (- (square guess) x)) 0.00) ) (defie (improve guess) (average guess (/ x guess)) ) (defie (sqrt-iter guess) (if (good-eough? guess) guess (sqrt-iter (improve guess)) )) (sqrt-iter.0) ) 静的有効範囲 (lexical scopig) 36 ハノイの塔を解こう.. 一度には枚の円盤しか動かせない. 2. 小さい円盤の上には大きな円盤は置けない. Java で実行 37 5

6 (defie (move-tower size from to extra) (cod ((= size 0) #true) (else (move-tower (- size ) from extra to) (prit-move from to) (move-tower (- size ) extra to from)) )) (defie (prit-move from to) (ewlie) (display move top disk from ) (display from) (display to ) (display to) ) (defie (solve-tower-of-haoi size from to) (move-tower size from to (- 6 from to)) ) 38, if m 0 Ack( m, ) Ack( m,), if 0 Ack( m, Ack( m, )), otherwise (defie (ack m ) (cod ((= m 0) (+ )) ((= 0) (ack (- m ) )) (else (ack (- m ) (ack m (- )) )))) (ack 0 2) Ackerma 関数は線形再帰ではない! (ack 2) (ack 2 2) (ack 3 2) 39 練習問題 (ack 0 2) (ack 2) (ack 2 2) (ack 3 2) 計算過程を書くこと. 以下随意課題. (ack 0 ) + ( 理由も ) 2. (ack )? ( 理由も ) 3. (ack 2 )? ( 理由も ) 4. (ack 3 )? ( 理由も ) 5. (ack 4 )? ( 理由も ) 40 6

7 . Ackerma 関数のファイルを作成せよ. ack.scm 2. Ackerma 関数を実行し, 出力結果を求めよ. (ack 0 2), (ack 2), (ack 2 2), (ack 3 2) 3. 教科書練習問題 Ex.5( 置換プロセスを明記のこと ) 4. Program ファイルとレポート (pdf) を SICP-4@zeus.kuis.kyoto-u.ac.jp に送付 5. 随意次の一般式を求めよ. 理由, 計算過程明記のこと. (ack 0 ) +,(ack )?, (ack 2 )?, (ack 3 )?, (ack 4 )? (otherwise 回答は減点 ) 43. ドルの両替の方法は何通り? セント (half dollar),25 セント (quarter),0 セント (dime), 5 セント (ickel), セント (pey) 3. 一般化 : 分割数を求める 44 使える硬貨をある順番で並べておくと種類の硬貨で金額 a の両替の場合の数は. 先頭の種類を除いたすべての硬貨を使って金額 aを両替する場合の数 + 2. 先頭の種類の硬貨 ( 額面 d) とすると,a-dの額を全種の硬貨を使って両替する場合の数 3. 初期値 : a=0 の時,a<0 の時か =0 の時 0 分割統治法 (divide-ad-coquor) 45 7

(defie (cout-chage amout) (cc amout 5) ) (defie (cc amout kids-of-cois) (cod ((= amout 0) ) ((or (< amout 0) (= kids-of-cois 0)) 0) (else (+ (cc amout (- kids-of-cois )) (cc (- amout (first-deomiatio

8 (defie (cout-chage amout) (cc amout 5) ) (defie (cc amout kids-of-cois) (cod ((= amout 0) ) ((or (< amout 0) (= kids-of-cois 0)) 0) (else (+ (cc amout (- kids-of-cois )) (cc (- amout (first-deomiatio kids-of-cois)) kids-of-cois ))))) (defie (first-deomiatio kids-of-cois) (cod ((= kids-of-cois ) ) ((= kids-of-cois 2) 5) ((= kids-of-cois 3) 0) ((= kids-of-cois 4) 25) ((= kids-of-cois 5) 50) )) 47 c i+ s + c i (carry, 桁上げ ) x y (defie (adder x y c) (defie (carry x y c) (if (or (ad (= x ) (= y )) (ad (= y ) (= c )) (ad (= c ) (= x )) ) 0 )) (defie (sum x y c) (xor x y c) ) (cos (sum x y c) (carry x y c)) ) (defie (xor x y z) (if (= x 0) (if (= y 0) z (if (= z 0) 0)) (if (= y 0) (if (= z 0) 0) z) )) 48 What is this istrumet? タイガー計算機

Microsoft PowerPoint - IntroAlgDs-13-4.pptx

Microsoft PowerPoint - IntroAlgDs-13-4.pptx アルゴリズムとデータ構造入門 - 年月 9 日大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野 http://wiie.kuis.koto-u.c.jp/~okuo/lecture//itroalgds/ okuo@i.koto-u.c.jp,okuo@ue.org TAの居室は総合研究 7 号館階 8 号室奥乃研 (M 奥乃研音楽情報処理 G (M 奥乃研ロボット聴覚 G