Microsoft PowerPoint - IntroAlgDs-10-2.pptx

(1)

アルゴリズムとデータ構造入門-１ 2010年10月12日大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野知能メディア講座音声メディア分野 http://winnie.kuis.kyoto-u.ac.jp/~okuno/Lecture/10/IntroAlgDs/ okuno@i.kyoto-u.ac.jp，okuno@nue.orgy jp g TA TAの居室はの居室は1010号館４階奥乃１研，２研号館４階奥乃１研，２研（M1)奥乃研・音楽G （M1) 奥乃研・音楽G （M1) 奥乃研・ロボット聴覚G 1

• 1-1-5 The Substitution Model for Procedure Application

Procedure Application

• 1-1-6 Conditional Expressions and Predicates （復習）

• 1-1-7 Example: Square Roots by 1 1 7 Example: Square Roots by Newton's Method

1 1 8 Procedures as Black Box • 1-1-8 Procedures as Black-Box

Abstractions

• 1.2.1 Linear Recursion and Iteration • 1 2 2 Tree Recursion 3 1.2.2 Tree Recursion • 式（_{expression ）は単純なものから構築．} ほぼすべての式は値値（ ll ）を持 • ほぼすべての式は，値値（valuevalue）を持つ. • 式は評価評価（evaluateevaluate）されて値を返す． • すべての値には型型（typetype）がある． 4 11 ii （式式） 1. 1. expressionsexpressions （式式） •• primitivesprimitives（基本式基本式）と •• combinationscombinations（合成式合成式）で構成 2.

2. means of combination .. means of comb nat on means of combination （合成法means of comb nat on （合成法合成法）合成法） 3.

3. Means of abstractionMeans of abstraction（抽象化法抽象化法）

44 CC ti ti dd bj t bj t (手続きの作成法手続きの作成法) 4.

4. Creating procedure objectsCreating procedure objects (手続きの作成法手続きの作成法) 5. 以上が言語構文 (language syntax)，構築子

（l ）

（language constructs） 6.

6. Viewing the rules of evaluation from a Viewing the rules of evaluation from a gg computational perspective computational perspective (計算という観点か計算という観点からの評価法らの評価法₎ 5 7. これが言語意味論（language semantics）

•• SelfSelf--evaluating primitivesevaluating primitives（評価すると自分自身の値が返る）

– Numbers （数）： 38, 3.80, 1.4141, 2.3e-4, 3/5 – Strings （文字列）： “moji”, “a”Strings （文字列）： moji , a

– Booleans （論理式）： #t, #f B ilt

B ilt i di d （組込み手続き） •• BuiltBuilt--in procedurein procedure（組込み手続き）

– 基本オブジェクト（primitive objects）の処理 – Numbers（数）：+, -, *, /, <, =, <=, …

– Strings（文字列）： string-length, string=?Strings（文字列）： string length, string ? – Booleans（論理式）： and, or, not, xor, nand N f b il

N f b il i di d

7 •• Names for builtNames for built--in proceduresin procedures

– + ＋という組込み手続き • Primitives を使って式を合成 ( 3 5) • (+ 3 5) （演算子引数．．．）評価法 • 評価法 1. 部分式（subexpressions）を評価し，値を得る.部分（ p ）を評価，値を得る 2. 演算子（operator）に引数（arguments）を適用．続き適続き適う –

– procedure applicationprocedure application （手続き適用手続き適用）という

(2)

• (* 5 5) • (* 38 38) • (* 389.2 389.2)( 389. 389. ) Abstraction of values • (define foo 389.2) • (* foo foo) • (* foo (+ foo 5) 123) Combination Combination • (+ 3 (* 53 12.4) 9) Abstraction of combinationsf (define (square x) (* x x)) • 正書法は下記 • 正書法は下記 (define square (lambda (x) (* x x)) ) 9 • 最初のは簡便記法： Syntax sugar （糖衣錠のこと） • 階乗の定義（その１） (define (factorial n) (if (<= n 0) (if (< n 0) 1 (* n (factorial (- n 1))) )) (* n (factorial (- n 1))) )) To define n!, if it is non-positive, return 1

otherwise, multiply it by (n-1)! • どう実行されるか。Substation model で実行 17 • 積は factorialの呼ばれる回数 factorialの呼ばれる回数

n回 for n! (time complexity) 未実行の * の量

(factorial 6) _未実行の _の量

最大 n回 for n! (space complexity)

(* 6 (factorial 5)) (* 6 (* 5 (factorial 4))) ( 6 ( ( ( 3)))) (* 6 (* 5 (* 4 (factorial 3)))) (* 6 (* 5 (* 4 (* 3 (factorial 2))))) (* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1)))))) ( 6 ( 5 ( ( 3 ( ( acto a )))))) (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))))) (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 1)))))) (* 6 (* 5 (* 4 (* 3 (* 2 1))))) (* 6 (* 5 (* 4 (* 3 2)))) (* 6 (* 5 (* 4 6))) (* 6 (* 5 (* 4 6))) (* 6 (* 5 24)) (* 6 120) 21 720 階乗の定義（その２） fi ! ! 1 * 2 * * To define n!, n! = 1 * 2 * ・・・ * n

product = counter * product t t 1 counter = counter + 1

(define (fact n) (f t it 1 1 ) ) (fact-iter 1 1 n) )

(define (fact-iter product counter max-count) (if (> counter max-count)

(if (> counter max count) product

(fact-iter (* counter product) (+ counter 1) max-count) )) どう実行されるか。Substation model (置換モデル) で実行 22 (f t 6) (fact 6) (fact-iter 1 1 6) (fact-iter 1 2 6) (fact-iter 2 3 6) f t から ( ) (fact-iter 6 4 6) (fact iter 24 5 6) fact から fact-iter へ 自動変換が可能 (fact-iter 24 5 6) (fact-iter 120 6 6) (fact-iter 720 7 6) 720 fact-iter の呼ばれる回数 回 f ! (ti l it )

n回 for n! (time complexity) 未実行の演算の量はない余分な仮パラメータ 23 余分な仮パラメータ２個 (space complexity) (define (fact n)

(define (iter product counter) (if (> counter n)

product

(iter (* counter product) (+ counter 1) ))) (iter 1 1) ) • 手続きiterは， fact の中で有効。 仮パラメタ d t t は it の中で有効 • 仮パラメータ product,counterは，iterの中で有効 • 外部からは （information hiding）g • これはオブジェクト指向の１つの特徴． 25

(3)

(define (f n) (if (<= n 0) 1 (* (f (- n 1)) n) )) • このプログラムは次の翻訳 n! = (n-1)! * n • 下記のfactorialとの違いは下記のfactorialとの違いは (define (factorial n) (if (<= n 0) (if (< n 0) 1 (* n (factorial (- n 1))) )) 26 ( n (factorial ( n 1))) )) (f 6) (* (f 5) 6) (* (* (f 4) 5) 6) (* (* (* (f 3) 4) 5) 6) (* (* (* (* (f 2) 3) 4) 5) 6) (* (* (* (* (f 2) 3) 4) 5) 6) (* (* (* (* (* (f 1) 2) 3) 4) 5) 6) (* (* (* (* (* (* (f 0) 1) 2) 3) 4) 5) 6) ( ( ( ( ( ( (f 0) 1) 2) 3) 4) 5) 6) (* (* (* (* (* (* 1 1) 2) 3) 4) 5) 6) (* (* (* (* (* 1 2) 3) 4) 5) 6) (* (* (* (* 2 3) 4) 5) 6) (* (* (* 6 4) 5) 6) (* (* 24 5)) (* 120) 720 27 720

SC> (time (null? (factorial 5000)))( ( ( ))) total time: 0.729999999999563 secs user time: 0.690993 secs

t ti 0 system time: 0 secs #f

SC> (time (null? (f 5000)))( ( ( ))) total time: 1.34000000000015 secs user time: 1.321901 secs

SC> (time (null? (fact 5000)))( ( ( ))) total time: 0.720000000001164 secs user time: 0.701008 secs

28

• トップダウン（トップダウン（top-down）式で計算–線形再帰top down）式で計算線形再帰

(define (factorial n) (if (<= n 0) (if (< n 0) 1 (* n (factorial (- n 1))) )) ( ( ( ))) )) • ボトムアップ（bottom-up）式で計算–線形反復p (define (fact-iter n)

(define (iter product counter)p (if (> counter n)

product

(iter (* counter product) (+ counter 1) ))) 29 (iter 1 1) ) • n!はただし n n n 12 1 1 12 1     n e e n n n n          2 ! • スターリング級数は       n       _ _ _ _ _        ₂ ₃ ₄ _ 2488320 1 51840 1 288 1 12 1 1 2 ! n n n n e n n n n  • 対数をとると          ₃ ₅ ₇ 1680 1 1260 1 360 1 12 1 ) 2 ln( 2 1 ln ! ln n n n n n n n n n  for n>>0

l

!

l

30

n

!

 ln



ln

• ウサギのつがい１（二羽）の数２３３４ • 内部反射回数５６ 31

(4)





0 ,

if

n

 0











th

i

2

1 if

1

0 if

,

1 ,

0 )

fib(

)

fib(

n

fib(n)



fib(n



1 )



fib(n



2 )

,

otherwise

(define (fib n) ( d (( 0) 0) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)) )))) 33 i i i

a

b

a

_1





a

₀



₁

i i

a

b

_1



₀

0



b

ただし，

n

b

n

fib

(

)



0 (define (fib-i n)

(define (iter a b count) (define (iter a b count)

(if (= count 0) b b (iter (+ a b) a (- count 1)) )) (it 1 0 ) ) 34 (iter 1 0 n) ) (define (fib-i n)

(define (iter a b count)

木構造再帰

(define (iter a b count)

(if (= count 0) b (iter (+ a b) a (- count 1)) )) (iter 1 0 n) ) ブロック構造を使わないと，ブロック構造を使わないと， (define (fib-i n) (define (fib i n) (fib-iter 1 0 n)

(define (fib-iter a b count) (if (= count 0)

b

(fib-iter (+ a b) a (- count 1)) )) 35 (fib iter (+ a b) a ( count 1)) ))

• Fibonacci数の漸化式 • ビネの公式

0



F

1



1 F

n2



F

n



F

n1 • ビネの公式





_

 

1

5 _



n

_

 

1

5 _



n

1 











_























 



n

F

2

5

1

2

5

1

5

1

• 帰納法で証明せよ．













黄金比（

黄金比（Golden Ratio

Golden Ratio））

1. n = 0, 1 を検証 2 kのとき成立を仮定し k+1で成立を示す

黄金比（

黄金比（Golden Ratio

Golden Ratio））

2. kのとき成立を仮定し，k+1で成立を示す

コンピュータ将棋「あらか

2010

2010」」

清水市代女流王将破る

(10/11, (10/11, 東大東大)) • 情報処理学会の「トッププロ棋士に勝つ将棋プロジェクト」特製システム • 阿伽羅（あから）は10の224乗という数を表し、将棋の局面の数がこの数に近いことに因んで命名されたドウ部 • ハードウエア部－東京大学クラスターマシン：

-Intel Xeon 2.80GHz, 4 cores 109台 -Intel Xeon 2.40GHz, 4 cores 60台

合計16 台 6 6 合計169台 676 cores －バックアップマシン：４プログラムそれぞれについて1台ずつ

-CPU: Xeon W3680 3.33GHz 6cores -Memory: 24GB (DDR3 UMB ECC 4GBx6)

※ 使用ハードウェアは当日変更される可能性もあります。（2010年10月6日追記） • ソフトウエア部－構成：国内トップ４プログラムによる多数決合議法多数決合議法（4つのプレイヤープログラムに局面を渡し指し手を受け取りもっとも多い手を指し手として返す）ラムに局面を渡し、指し手を受け取り、もっとも多い手を指し手として返す） - 合議マネージャ：開発：電気通信大学伊藤研究室＆保木邦仁 - プレイヤー１：「激指」開発：激指開発チーム（鶴岡慶雅、横山大作） - プレイヤー２：「GPS将棋」開発：チームGPS（田中哲朗、金子知適ほか） プレイヤー３：「Bonanza」開発：保木邦仁 38 - プレイヤー３：「Bonanza」開発：保木邦仁 - プレイヤー４：「YSS」開発：山下宏

THE POWER OF LOGARITHM

計算尺（slide rule, slipstick）対数による積の計算乗算→対数→加算累乗→対数→乗算累乗対数乗算 230 _はいくら 210 _{→対数→10log2 →3 01} 2 →対数→10log2 →3.01 210 ₁₀3 _→1K 230 ₁₀9 _→1G 230 ₁₀9 _→1G 音楽のピッチ音の知覚音の知覚 40

(5)

Slide Rule Slide Rule  アポロ13 ク決隊 41  ミクロの決死隊  タイタニック Scale Label Value Relative to C/D A X2 K X3 KZ X x 360 R 1 / X R1 R2 Square root of X B X2 C X L log X Lg log X Ln ln X R1, R2 Square root of X S sin X Sh1, Sh2 sinh X CF X x pi CF/M X x loge10 CI 1 / X Ln ln X LL0 e0.001x LL1 or ZZ1 e0.01x , Sq1, Sq2 Square root of X SRT sin X, tan X / CIF 1 / (pi x X) D X LL2 or ZZ2 e0.1x LL3 or ZZ3 ex , ST sin, tan X T tan X, cotan X DF X x pi DF/M X x loge10 LL00 or LL/0 e‐x LL01 or LL/1 e‐0.1x T1, T3 tan X, cotan X T2 tan X, cotan X DFM X x loge10 DI 1 / X DIF 1 / (pi x X) LL02 or LL/2 e‐0.01x LL03 or LL/3 e‐0.001x Th tanh X V Volts DIF 1 / (pi x X) E ex H ‐ M log X P Square root of (1‐X2) W1, W2 Square root of X Z X H1, H2 Square root of (1+X2₎ HC ‐ p% ‐ P1, P2 Square root of (1‐X2) ZZ1, ZZ2, ZZ3 ex

大きな数・小さな数

deca da ×101 _deci _d _×₁₀-1 deca da 10 hecto h ×102 kil K ×103 deci d 10 centi c ×10-2 illi ×103 kilo K ×103 mega M ×106 milli m ×10-3 micro μ ×10-6 giga G ×109 tera T ×1012 nano n ×10-9 pico p ×10-12 tera T ×10 peta P ×1015 E ×1018 pico p ×10 femto f ×10-15 ×1018 exa E ×1018 zetta Z ×1021 atto a ×10-18 zepto z ×10-21 43 yotta Y ×1024 _yocto _y _×₁₀-24

101 _{ten or decad} ₁₀21 _sextillion

102 _{hundred or hecatontad} 103 _{thousand or chiliad} 1024 _septillion 10 thousand or chiliad 104 _myriad 5 1033 _decillion 105 _{lac or lakh} 106 _million 1063 _vigintillion 10303 _centillion 107 _crore 108 _myriamyriad 10100 _googol 10googol _googolplex 10 myriamyriad 109 _{milliard or billion} 10googol _googolplex 1012 _trillion 1015 _quadrillion 10N _{N plex} 10-N _{N minex} 44 q 1018 _quintillion

88plex 無量大数 20plex 垓 4minex 絲(糸)

224plex 阿伽羅 88plex 無量大数 80plex 不可思議 72 l 那由他 20plex 垓 16plex 京 12 l 兆 4minex 絲(糸) 5minex 忽 6 i 微 72plex 那由他 64plex 阿僧祇 12plex 兆 8plex 億 6minex 微 7minex 纎(繊) 56plex 恒河砂 48plex 極 4plex 萬(万) 3plex 千 8minex 沙 9minex 塵 48plex 極 44plex 載 l 3plex 千 2plex 百 1 l 十 9minex 塵 10minex 埃 11 i 渺 40plex 正 36plex 澗 1plex 十 0plex 一 11minex 渺 12minex 漠 32plex 溝 28plex 穣 1minex 分 2minex 厘 13minex 模糊 14minex 逡巡 45 28plex 穣 24plex 杼(禾偏) 2minex 厘 3minex 毫(毛) 14minex 逡巡 15minex 須臾 1minex 分 13minex 模糊 2minex 厘 3minex 毫(毛) モウ 14minex 逡巡シュンジュン 15minex 須臾シュユ毫( ) ウ 4minex 絲(糸) シ 5minex 忽コツ須臾シ 16minex 瞬息シュンソク 17minex 弾指ダンシ 5minex 忽コツ 6minex 微ビ 17minex 弾指ダンシ 18minex 殺那 7minex 纎(繊)セン 8minex 沙シャ 19minex 六徳リットク 20minex 虚 8 e 沙シャ 9minex 塵ジン 10 i 埃アイ 20minex 虚 21minex 空 22 i 清 10minex 埃アイ 11minex 渺ビョウ 22minex 清 23minex 浄 46 12minex 漠バク

(6)

Fibonacci数の漸化式 1 線形差分方程式の解法

0



F

1



1 F

n2



F

n



F

n1 1. 線形差分方程式の解法 1) 特性方程式を作成・解を求める． 2) その根をα，βとすると元の差分方程式の解は と表せる n n _D C F     と表せる。ただし，C, D は定数 n C D F     3) 初期値等から、定数項の値を求める 2 母関数（_{generating function）の解法} 2. 母関数（_{generating function）の解法} • 漸化式： , , • 般的な解法 1 1 a a21 an2anan1 0 1 2a a  a • 一般的な解法 1. 方程式の根をφ，ψとすると 0 1 2   n n n a a a 0 1 2_{ t}_ _ t 一般項はと表せる。ただし A B は定数である n n n a A B ただし、A, B は定数である。 2. 初期値等から、定数項の値を求める。 • 1より _1 ₅   1 5 , • ２より 2  1 B A 1   a



_n n



1 2  49



n n



n a    5 1 B A 2 2 2     a • フィボナッチ数列： 0 1 1 2 3 5 8 • フィボナッチ数列： 0, 1, 1, 2, 3, 5, 8, … 0 0 F F11 Fn2FnFn1 5 4 3 2 • 母関数 yF0F1xF2x2F3x3F4x4F5x5 6 5 4 3 2 _F_x _F_x _F_x _F_x x F x F xy       3 2 3 2 1 2 0 1 0 5 4 3 2 1 0 ) 1 ( ) ( ) ( ) (F F x F F x F F x F xy y x F x F x F x F x F x F xy                   左辺 5 3 4 2 3 1 2 0 ) 1 ( x F x F x F x F x x y         右辺左辺 2 4 3 3 2 2 1 0 2₍ ₎ y x x x F x F x F x F x x         　　　 2 ) 1 ( xy x x y y x x       　　　 2 1 x x x y      • 部分分数への分解 _            x x x x x     1 1 1 1 1 1 2 x x 両辺を比べて ( +β) 1 β 1 2 2 ₁ ₍ ₎ 1xx    xx • 両辺を比べて (α+β)=1, α β=-1 • これは _t2_{ t}_1_0 の解 • 級数展開をすると 1 ... 1 1 _ _ _ 2_ 3_ 4_ 5_ 6_ x x x x x x x



 





1 ... 1 ...



1 3 3 2 2 2 2 2 2 _ _ _ _ _     x x x x y       の係数はボナチ数 ... 3 3 3 2 2 2           x x x y             • xn の係数はフィボナッチ数F_n • xn _{の係数はフィボナッチ数}_F n        n n n F • 一方，   5 1 2 5 1 ,                             n n n F 2 5 1 2 5 1 5 1   2   2  5 (define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2)) ))))

木構造再帰

53

(7)

(fib-i 6) (iter 1 0 6)

(define (fib-i n) (define (iter a b count)

(iter 1 0 6) (iter 1 1 5) (it 2 1 4) ( ( ) (if (= count 0) b (iter (+ a b) a ( t 1) ))) (iter 2 1 4) (iter 3 2 3) (- count 1) ))) (iter 1 0 n) ) (iter 5 3 2) (iter 8 5 1) (iter 13 8 0) 8

Linear iterative proces

Linear iterative process

(線形反復プロセス

線形反復プロセス)

54

(線形反復プロセス

線形反復プロセス)

• C(n):n に対して fib の呼ばれる回数

C(0)=C(1)=1

• C(0)=C(1)=1

• n 2 に対して C(n)=C(n-1)+C(n-2)+1

対し

( ) (

) (

)

• C(2)=3, C(3)=5, C(4)=9, C(5)=15, …

• 一般に、

C(k) > 2

k/2

C(n) を求める

1. F(n)=C(n)+1 とおくと

( ) ( )

お

2. F(n)=F(n-1)+F(n-2) for n 2

55

3. F(0)=2, F(1)=2

• n 2 に対して C(n)=C(n-1)+C(n-2)+1 • F(n)=C(n)+1 とおくと • F(n)=C(n)+1 とおくと • F(n)=F(n-1)+F(n-2) for n 2 • F(0)=2, F(1)=2 ψ は _t2 _t 1 0 の根 n n n F( ) A B • _F₍_n₎__A_ __B_ , φ，ψ は _t2_{ t}_1_0 の根  2 1 1 A    _B_₁ 1 _ 2_ 5 5 1 A  _ 5 5 1 B   ) ( 2 2 2 ) (_n _ n_ n_ n1_ n1 F     2 1 1 ) ( 5 5 5 ) (n   F     1 ) ( 5 2 ) (_n _ n1_ n1 _ C   59 Fib(n) は _a _ 1



_n__n



• Fib(n) は an



 



5 5 1 ₀₆₂₀ • より 2 5 1   0.620 • 従って、fib(n) は n に最も近い整数 n a  5 1  60 1 繰り返し版階乗のプログラムのフイルを作成せよ 1. 繰り返し版階乗のプログラムのファイルを作成せよ． fact.scm 2. 階乗のプログラムを実行し，出力結果を求めよ． 1. (load “fact.scm”) 1. (load fact.scm ) 2. (fact “100+ご自分の学籍番号の下1桁”) 3 階乗のプグラムの説明と出力結果を l で作成 3. 階乗のプログラムの説明と出力結果を latexで作成 し，_{pdfをレポートとする．（紙でも可）} 4. Program ファイルとpdf を

SICP-2@zeus kuis kyoto-u ac jpに送付

SICP-2@zeus.kuis.kyoto-u.ac.jpに送付

63 （otherwise 回答は減点）

1 C d P t i で & t 1. Command Prompt, cygwin で copy&paste 2. Shell の機能を使う

3. Output file を明示的に使用

 (define out (open-output-file ”outfile.txt”))

out 同じファイル名のファイルがあると上書き out 同じファイル名のファイルがあると上書き  out

#<port to outfile>

 (display (fact 7) out) 結果を“outfile.txt”に書き込む( p y ( ) ) 5040

 (newline out) #t

 (close output port out)  (close-output-port out)

4. call-with-output-file Output file の非明示的使用

 (call with output file ”fact101 txt”  (call-with-output-file fact101.txt

(lambda (out) (newline out) (display (fact 101) out)

64

(display (fact 101) out) (newline out) ))