Slides

アルゴリズムとデータ構造入門
第7回教科書1.3節後半&レポート解説
担当：馬谷誠二（[email protected]）
2
本日の内容
§1.3.3 汎用メソッドとしての手続き
§1.3.4 返り値としての手続き
レポート解説
不動点の計算
関数 f の不動点
f(x) = x を満たすような x
不動点を求める方法
f(x), f(f(x), f(f(f(x))), … をclose-enough?になるまで
繰り返す
Schemeコード
(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))
3
4
不動点としての平方根
•  x の平方根を y とする
y2 = x → y = x/y
•  じゃあ，平方根を
の不動点として求めよう
(define (sqrt x) (fixed-point (lambda (y) (/ x y)) 1.0))
．．．上手くいかない．たとえば√2だと，1.0, 2.0, 1.0, 2.0, 1.0, …
→ 振幅を狭くしてみよう（average damping，平均緩和法）
(define (sqrt x) (fixed-point (lambda (y) (average y (/ x y))) 1.0))
5
§1.1.7の平方根プログラムとの比較
今回のコード
(define (sqrt x) (fixed-point (lambda (y) (average y (/ x y))) 1.0))
§1.1.7のコード
まったく同じことをしているが，
(define (sqrt-iter guess x) 明らかに上の方が解りやすい
(if (good-enough? guess x) guess (sqrt-iter (improve guess x) x)))
(define (improve guess x) (average guess (/ x guess)))
(define (sqrt x) (sqrt-iter 1.0 x))
6
§1.3.4 返り値としての手続き
（あらたに生成した）手続きを返す手続き
例：平均緩和法
(define (average-damp f) (lambda (x) (average x (f x))))
((average-damp square) 10) ⇒ 55
•  sqrtの改訂
(define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))
•  手法をより明確に表現
•  再利用性： cube-root
(lambda (y)
(/ x (square y)))
7
ニュートン法(1)
定義
g(x) を微分可能な関数とする．方程式 g(x) = 0 の解は：
の不動点である（Dg は
g の導関数）．
微分演算子D （高階手続き）
(define dx 0.00001)
(define (deriv g) (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
((deriv (lambda (x) (* x x x)) 5) ⇒ 75.00014999664018
8
ニュートン法(2)
Schemeコード
(define (newton-transform g) (lambda (x) (- x (/ (g x) ((deriv g) x))))) (define (newtons-method g guess) (fixed-point (newton-transform g) guess))
例： sqrt
(define (sqrt x) (newtons-method (lambda (y) (- (square y) x)) 1.0))
数値微分を使っている点に注意．平均緩和法は記号微分に相当
さらなる抽象化（一般化）
9
平方根を求める2つの方法
1.  平均緩和法 + 不動点
(define (sqrt x) (fixed-point (average-damp (lambda (y) (/ x y))) 1.0))
2.  ニュートン法（これも不動点）
(define (newtons-method g guess) (fixed-point (newton-transform g) guess))
(define (sqrt x) (newtons-method (lambda (y) (- (square y) x)) 1.0))
あきらかに共通点 (define (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess))
(define (sqrt x) ;; 1の方法
(fixed-point-of-transform (lambda (y) (/ x y))
average-damp 1.0))
10
第一級手続き
第一級（first class）：プログラム中でできることのランク
1.  変数定義により名前をつけられる
(define cube (lambda (x) (* x x x)))
2.  手続きに引数として渡せる
(sum cube 1 inc 100)
3.  手続きの評価結果として返せる
(define (average-damp f) (lambda (x) (average x (f x))))
4.  データ構造の中に含められる
(define (foo f) (cons (deriv f)
(deriv (deriv f))))
11
ここからレポート解説
•  webページでの公開はしません
•  欲しい人には印刷したものを配布しますので，教員 or TA に
リクエストしてください
•  他の問題についても模範回答を知りたければ，遠慮なくリクエ
ストしてください
正解率の低かった問題
•  (10/7課題 Ex1.3)
•  10/14課題 (Ex1.7), 問題4
•  10/28課題問題1, 問題2
と，昨日締切の中から
•  11/4課題問題3
12
10/14課題 Ex1.7
good-enough?を改良せよ．
(和文) good-enough?を実装するもう一つの方法は，ある繰返
しから次へのguessの変化に注目し，変化が予測値に比べ非
常に小さくなった時に止めるのである．
13
10/14課題 Ex1.7
good-enough?を改良せよ．
(和文) good-enough?を実装するもう一つの方法は，ある繰返
しから次へのguessの変化に注目し，変化が予測値に比べ非
常に小さくなった時に止めるのである．
(原文) … watch how guess changes from one iteration to
the next and to stop when the change is a very small
fraction of the guess …
14
10/14課題問題4
if が cond の特殊ケースであるのと同様に，and ならびに
or が cond (あるいは if)の特殊ケースであることを表す等式
を示せ．
(and <e1> … <en>): 特殊形式
• 
• 
• 
式⟨eｉ⟩を左から右へ一つずつ評価
ある⟨eｉ⟩の評価の結果が#fなら, and式の値は#f．
残りの⟨ei+1⟩ … は評価しない
すべての⟨ei⟩が真に評価されれば, and式の値は最後の式の値
(if <e1>
(if <e2>
... (if <en> <en> #f) ...
#f)
#f))
;; (if en-1 en #f)も可
15
10/28課題問題1
1.  教科書の脚注37に書いてあること（fast-exptの乗算
回数は
以下である）をきちんと証明せよ．
(define (square x) (* x x))
(define (fast-expt b n) (cond ((= n 0) 1)
((= n 1) b) ((even? n)
(square (fast-expt b (/ n 2))))
; (1)
(else (* b (fast-expt b (- n 1)))))) ; (2)
乗算回数：
(1) が実行される回数 + (2) が実行される回数
16
より高速な方法(2)
計算量
•  簡単な場合：
•  一般の場合：
・の個数 = log2 n
Θ(log n) → 脚注37（レポート課題）
n を2進数で表したときの1の個数を x とする．fast-exptにより
実行される乗算の回数は：
例: n = 13 (1101) の場合，x = 3 で上式の値は 3 + 3 – 1 = 5
ヒント： 2で割る = 1ビット右へシフト
奇数から1を引く = 最下位ビットをクリア
17
(fast-expt b 13)
(2)
⇒ (* b
(fast-expt b 12))
(1)
⇒ (* b (square (fast-expt b
(1)
⇒
...
(fast-expt b
3) ...
(2)
⇒
...
(fast-expt b
2) ...
(2)
⇒
...
(fast-expt b
1) ...
⇒
...
b
6)))
...
18
(fast-expt b 1101)
(2)
⇒ (* b
(fast-expt b 1100))
クリア
(1)
⇒ (* b (square (fast-expt b 110)))
シフト
(1)
⇒
...
(fast-expt b 11) ...
シフト
(2)
⇒
...
(fast-expt b 10) ...
クリア
(2)
⇒
...
(fast-expt b 1)
...
シフト
⇒
...
b
...
1101
2i
i ビット
(1)の回数 = i
(2)の回数 = i ビット中の1の個数
したがって，(1) + (2) 19
10/28課題問題2
,
，
（もパラメータ）を計算する
手続きをそれぞれ書け．また，それぞれの計算量も求めよ．
1. 
• 
• 
は正整数，　は2以上の整数とする
もちろん，JAKLD組込みの手続きlogを使用してはいけない
方針
すなおに解釈すると：
という条件を満たすような整数
x を見つければ良い．
x を 0 から順に試してみよう（線形探索）．
20
(define (linear-floor-log0 b n)
(define (iter x)
(if (> (fast-expt b x) n)
(- x 1)
(iter (+ x 1))))
(iter 1))
•  一応正解だが，実行効率があまり良くない（O((log n)2)）
•  (fast-expt b x) を毎回呼び出さなくても，蓄積引数を
一つ追加するだけで bx を求めることができる（Θ(log n)）
(define (linear-floor-log b n)
(define (iter x prod)
;; prod = b^x
(if (> prod n)
(- x 1)
(iter (+ x 1) (* prod b))))
(iter 1 b))
21
（別解）脚注37がヒント
= 入力 n を b 進数表現したときの桁数 - 1
例:
１００１００１１　（＝　１４７）
７　（２７　＝　１２８）
(define (linear-floor-log-down b n)
(define (iter cnt quot)
(if (< quot b)
cnt
(iter (+ cnt 1) (quotient quot b))))
(iter 0 n))
•  上からの線形探索
とも思える
•  Θ(log n)
(define (linear-floor-log b n)
(define (iter x prod)
;; prod = b^x
(if (> prod n)
(- x 1)
(iter (+ x 1) (* prod b))))
(iter 1 b))
22
11/4課題問題3
さらに，同様の方法によって
を求める手続きを書け．
また，前回レポートの必須問題2において自分の書いた
を求める手続きと計算時間を比較せよ．
(define (floor-log b n)
(define (search low high)
(let* ((mid (quotient (+ low high) 2))
(mid-expt (fast-expt b mid)))
(cond ((< n mid-expt)
; 左不成立
(search low mid))
((<= (* b mid-expt) n) ; 右不成立
(search (+ mid 1) high))
(else mid))))
(search 0 n))
23
二分探索（binary search）
•  ソートされたデータ列 A[i]
1
A 2
2
3
4
5
6
7
8
8
13 15 30 37 42 50
O(log n)
•  一方，前から順に探していくのを線形探索（linear search）
•  計算オーダは O(n)
•  より広い意味で用いることもある
•  計算オーダは
•  ちょうど良いあたりの半分で領域を分ける
•  二つのどちらに含まれているか判定して再帰
を見つかるまで繰り返す探索方法
24
計算量
少しごまかしてる
とすると
なので
とすると
すなわち
従って
．同様にして
25
補足
(define (floor-log b n)
(define (search low high)
(let* ((mid (quotient (+ low high) 2))
(mid-expt (fast-expt b mid)))
(cond ((< n mid-expt)
(search low mid))
((<= (* b mid-expt) n)
(search (+ mid 1) high))
(else mid))))
(search 0 n))
•  線形探索の
Θ(log n) より遅い（！）
•  この二分探索が遅い理由
1.  searchの初期値が悪い
2.  反復毎のfast-expt呼出し
26
フェーズ1：
0
を
になるまで繰り返す
n/4
n/2
n
O(log n)回
0
h
フェーズ2：本当の（？）二分探索
2h
O(log log n)回
27
補足
•  現実的には，入力
n の上限は決まっている
たとえば，32ビット符号なし整数なら，232 –
1
→ (search 0 32) で十分
(define (floor-log b n)
(define (search low high)
(let* ((mid (quotient (+ low high) 2))
(mid-expt (fast-expt b mid)))
(cond ((< n mid-expt)
(search low mid))
((<= (* b mid-expt) n)
(search (+ mid 1) high))
(else mid))))
(search 0 32))
さらに補足
b を固定すれば（あまりスマートなコードに見えないが）
fast-expt 呼出しをなくすことも可能
(define (floor-log-base2 n)
(if (>= n 16)
; 2^4
(if (>= n 64)
; 2^6
(if (>= n 128) ; 2^7
7
6)
(if (>= n 32)
; 2^5
5
4))
(if (>= n 4)
; 2^2
(if (>= n 8)
; 2^3
3
2)
(if (>= n 2)
; 2^1
1
0))))
→ 計算量：
O(log log n)
28
29
おわりに
•  授業への感想，意見，コメント等あれば，課題提出システムに
コメントをお願いします．
•  11/18課題として，空のレポート課題をつくっておきます．
•  それでは，2章以降を楽しんで学んでください．

Download Report