Microsoft PowerPoint - IntroAlgDs-05-6.ppt

Size: px

Start display at page:

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

ほだかいとえ
5 years ago
Views:

データによる抽象の構築 Building Abstractions with Data 奥乃博.

1 アルゴリズムとデータ構造入門 005 年月 8 日アルゴリズムとデータ構造入門.5 Formulating Abstractions with Higher-Order Procedures. データによる抽象の構築 Building Abstractions with Data 奥乃博. 世の中のシステムは楽観主義 (optimistic) と悲観主義 (pessimistic) の中庸 (trade-off) で設計されている祝京大チーム年連続世界大会出場 Let s Play JMC with your num. (define (jmc n) (if (> n 00) (- n 0) (jmc (jmc (+ n ) )))) 各自次の式を求めよ (jmc (modulo 学籍番号 00)) 4

2 月 8 日本日のメニュー.3.3 Procedures as General Methods.3.4 Procedures as Returned Values Building Abstractions with Data. Introduction to Data Abstraction.. Example: Arithmetic Operations for Rational Numbers Procedures as General Methods Finding roots of equations by 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)))))) 6 Finding roots of equations by the half-interval method (define (close-enough? x y) (< (abs (- x y)) 0.00)) (define (half-interval-method f a b) (let ((a-value (f a)) (b-value (f b))) (cond ((and (negative? a-value) (positive? b-value)) (search f a b)) ((and (negative? b-value) (positive? a-value)) (search f b a)) (else (error "Values are not of opposite sign" a b)) ))) L: 開始時の区間長 T: 誤差許容度ステップ数 : Θ(log(L/T)) 7

Finding fixed points of functions( 不動点 ) (define tolerance 0.

v v) (< (abs (- v v)) tolerance)) (define (try guess) (let ((next (f guess)))

guess next) next (try next)))) (try first-guess)) Xが不動点 x = f(x) f ( x), f ( f (

3 Finding fixed points of functions( 不動点 ) (define tolerance ) (define (fixed-point f first-guess) (define (close-enough? v v) (< (abs (- v v)) tolerance)) (define (try guess) (let ((next (f guess))) (if (close-enough? guess next) next (try next)))) (try first-guess)) Xが不動点 x = f(x) f ( x), f ( f ( x)), f ( f ( f ( x))), 8 Finding fixed points of functions( 不動点 ) (fixed-point cos.0) (fixed-point (lambda (y) (+ (sin y) (cos y))) 0. ) 9 (fixed-point cos.0)& (fixed-point cos.0) 3

such ocillations: Redefine a new function y a (fixed-point (lambda (y) (average y (/

4 不動点が求まらない場合がある (fixed-point (lambda (y) (/ x y)).0)) y a x y (sqrt ) を実行すると (y y y ) x 3 Average damping ( 平均緩和法 ) One way to control such ocillations: Redefine a new function y a (fixed-point (lambda (y) (average y (/ x y))).0) ) Average damping ( 平均緩和法 ) x y + y 5 Fixed Point with Average Damping y a x y + y Average damping 平均緩和法 6 4

5 月 8 日本日のメニュー.3.3 Procedures as General Methods.3.4 Procedures as Returned Values Building Abstractions with Data. Introduction to Data Abstraction.. Example: Arithmetic Operations for Rational Numbers Procedures as Returned Values (fixed-point (lambda (y) (average y (/ x y))).0)) 平均緩和法を不動点の観点から眺めると (define (average-damp f) (lambda (x) (average x (f x)))) ((average-damp square) 0) (fixed-point (average-damp (lambda (y) (/ x y))).0)) averagedamp で統一的に捉えることが可能 (define (cube-root x) (fixed-point (average-damp (lambda (y) (/ x (square y)))).0)) 8 Newton's method & differentiation (define (deriv g) (lambda (x)(/ (- (g (+ x dx)) (g x)) dx)) ) (define dx ) y = x g( x) (define (cube x) (* x x x)) ((deriv cube) 5) g ( x) (define (newton-transform g) ニュートン法 (lambda (x)(- x (/ (g x) ((deriv g) x)))) ) (define (newtons-method g guess) (fixed-point (newton-transform g) guess) ) (newtons-method (lambda (y) (- (square y) x)).0)) 0 5

6 更なる抽象化 first-class procedures (define (fixed-point-of-transform g transform guess) (fixed-point (transform g) guess) ) st method (fixed-point-of-transform (lambda (y) (/ x y)) average-damp.0 )) nd method (fixed-point-of-transform (lambda (y) (- (square y) x)) newton-transform.0 )) 手続きの構築で何ら差別がない First-class citizen ( 第級市民 ) 第級市民の権利と特権変数で名前をつけることができる. 手続きへ引数として渡すことができる. 手続きの結果として返すことができる. データ構造の中に含めることができる. Microsoft Longhorn will make RAW first class citizen. The Inquirer, Wed. Jun-8, 手続き ( 関数 ) への演算 : 導関数 (define dx 0.000) (define (ddx f x) (/ (- (f (+ x dx)) (f x)) dx) ) (ddx square 3) 我々はもっとスマートだった! 導関数という考え方を採用 (define (deriv f) (lambda (x) (/ (- (f (+ x dx)) (f x)) dx) )) ((deriv square) 3) ((deriv (deriv square)) 3) (define (new-ddx f x) ((deriv f) x) ) 4 6

7 手続き ( 関数 ) の合成 : 高階導関数この考え方を発展させ高階導関数が構築できる (define (compose f g) (lambda (x) (f (g x)) )) (define nd-deriv (compose deriv deriv)) ((nd-deriv square) 3) もちろん手続きの合成も ((compose square sqrt) 7) 7.0 ((nd-deriv cos) pi) (define 3rd-deriv (compose deriv nd-deriv)) ((3rd-deriv sin) pi) ((4th-deriv cos) pi) 補足 : Fixed Point (define (jmc n) (if (> n 00) (- n 0) (jmc (jmc (+ n ))) )) (fixed-point jmc )? (Y F) = (F (Y F)) Y operator ( 不動点となる手続きを作成 ) (Y jmc) = (F (Y jmc)) = (lambda (n) (if (> n 00) (- n 0)?) ) 6 Fixed Point Operator F (define (Y F) (lambda (s) (F (lambda (x) (lambda (x) ((s s) x))) (lambda (s) (F (lambda (x) ((s s) x)))) ))) 再帰呼び出しに無名手続きを使いたい (Y F) = (F (Y F)) 詳しくは Church numeral の項で説明 7 7

8 What is this instrument? 計算尺対数による積の計算乗算対数加算累乗対数乗算 30 はいくら 0 対数 0log K G 9 大きな数小さな数 deca hecto da h 0 0 deci centi d c kilo K 0 3 milli m 0-3 mega giga M G micro nano μ n tera T 0 pico p 0 - peta exa P E femto atto f a zetta Z 0 zepto z 0 - yotta Y 0 4 yocto y ten or decad 0 0 hundred or hecatontad 0 3 thousand or chiliad 0 4 myriad 0 5 lac or lakh 0 6 million 0 7 crore 0 8 myriamyriad 0 9 milliard or billion 0 trillion 0 5 quadrillion 0 8 quintillion 0 sextillion 0 4 septillion decillion vigintillion centillion 0 00 googol 0 googol googolplex 0 N N plex 0 -N N minex 3 8

9 ギリシャ文字88plex 80plex 7plex 64plex 56plex 48plex 44plex 40plex 36plex 3plex 8plex 4plex 無量大数不可思議那由他阿僧祇恒河砂極載正澗溝穣杼 ( 禾偏 ) 0plex 6plex plex 8plex 4plex 3plex plex plex 0plex minex minex 3minex 垓京兆億萬 ( 万 ) 千百十一分厘毫 ( 毛 ) 4minex 5minex 6minex 7minex 8minex 9minex 0minex minex minex 3minex 4minex 5minex 絲 ( 糸 ) 忽微纎 ( 繊 ) 沙塵埃渺漠模糊逡巡須臾 33 minex minex 3minex 4minex 5minex 6minex 7minex 8minex 9minex 0minex minex minex 分厘毫 ( 毛 ) モウ絲 ( 糸 ) シ忽コツ微ビ纎 ( 繊 ) セン沙シャ塵ジン埃アイ渺ビョウ漠バク 3minex 4minex 5minex 6minex 7minex 8minex 9minex 0minex minex minex 3minex 模糊逡巡シュンジュン須臾シュユ瞬息シュンソク弾指ダンシ殺那六徳リットク虚空清浄 34 A B G D E Z Y Q I K L M a b g d e z h q i k l m alpha beta gamma delta epsilon zeta eta theta iota kappa lambda mu N X O P R S T U F C Y W n x o p r s t u f c y w nu xi omicron pi rho sigma tau upsilon phi chi psi omega 35 9

10 月 8 日本日のメニュー.3.3 Procedures as General Methods.3.4 Procedures as Returned Values Building Abstractions with Data. Introduction to Data Abstraction.. Example: Arithmetic Operations for Rational Numbers 36 第章データによる抽象の構築第章は手続き抽象化基本手続き合成手続き手続き抽象化例 : Σ, Π, accumulate, filtered-accumulate 第章はデータ抽象化基本データ構造 (primitive data structure/object) 合成データオブジェクト (compound data object) データ抽象化で手続きの意味 (semantics) が拡大加算 (+) 基本手続き : 整数 + 整数有理数 + 有理数実数 + 実数合成手続き : 複素数 + 複素数行列 + 行列 37 第章データ抽象化で学ぶこと抽象化の壁 (abstraction barrier) の構築データ構造の実装を外部から隠蔽 (blackbox) 閉包 (closure) 組み合わせを繰り返してもよい慣用インタフェース (conventional interface) Sequence を手続き間インタフェースとして使用ベルトコンベアトヨタの生産ライン UNIXのパイプ記号式 (symbolic expression) による表現汎用演算 (genetic operations) データ主導プログラミング (data-directed programming) 38 0

11 . データ抽象化 (data abstraction) 抽象データの 4 つの基本操作. 構成子 (constructor). 選択子 (selector) 3. 述語 (predicate) 4. 入出力 (input/ output ) 40.. Rational Numbers( 有理数 ) 構成子 (constructor) (make-rat <n> <d>) <n> numenator( 分子 ),<d> denominator ( 分母 ) 選択子 (selector) (numer <x>) (denom <x>) <x> rational number 述語 (predicate) (rational? <x>) (equal-rat? <x> <y>) 入出力 (input/output) <n>/<d> 4.. Rational Numbers( 有理数 ) 加算 (addition) 減算 (subtraction) 乗算 (multiplication) 除算 (division) 述語 n n nd nd + = + d d dd n n nd nd = d d dd n n nn = d d d d n n d d n = nd = d n d nd n = d n d 4

12 Rational Number Operations n n nd nd + = + d d d d n n d d (define (add-rat x y) (make-rat (+ (* (numer x) (denom y)) (* (numer y) (denom x)) ) (* (denom x) (denom y)) )) (define (sub-rat x y) (make-rat (- (* (numer x) (denom y)) (* (numer y) (denom x)) ) (* (denom x) (denom y)) )) nd nd = d d 43 Rational Number Operations n n nn n n nd n d = nd = = d d dd d d dn n n = (define (mul-rat x y) d d (make-rat (* (numer x) (numer y)) (* (denom x) (denom y) ))) (define (div-rat x y) (make-rat (* (numer x) (denom y)) (* (denom x) (numer y) ))) (define (equal-rat? x y) (= (* (numer x) (denom x)) (* (numer y) (denom y)) )) 44 Rational Number Representation (define (make-rat n d) (cons n d)) n d ペア (pair) で表現 (define (numer x) (car x)) (define (denom x) (cdr x)) (define (print-rat x) (newline) (display (numer x)) (display / ) (display (denom x)) x ) 45

13 Rational Number Reduction( 既約化 ) (define (make-rat n d) (cond n d)) これでは表現が曖昧になる (define (make-rat n d) (let ((g (gcd n d))) (cons (/ n gcd) (/ d gcd)) )) 既約化 : reducing rational numbers to the lowest terms 46 宿題 : 月 4 日午後 5 時締切宿題は次の 9 問 : Ex..35,.36,.37,.40,.4,.4,.43,.44,. 53 3

Microsoft PowerPoint - IntroAlgDs-09-6.pptx

Microsoft PowerPoint - IntroAlgDs-09-6.pptx アルゴリズムとデータ構造入門 6 2009 年 11 月 18 日大学院情報学研究科知能情報学専攻知能メディア講座音声メディア分野 http://winnie.kuis.kyoto-u.ac.jp/~okuno/lecture/08/introalgds/ okuno@i.kyoto-u.ac.jp TA のページがオープン, 質問箱もあります http://winnie.kuis.kyoto-u.ac.jp/~fukubaya/algdswiki/