アルゴリズムとデータ構造入門 -3 04 年 月 4 日 大学院情報学研究科知能情報学専攻 http://wiie.kuis.kyoto-u.ac.jp/~okuo/lecture//itroalgds/ okuo@i.kyoto-u.ac.jp,okuo@ue.org if mod( 学籍番号の下 3 桁,3) 0 if mod( 学籍番号の下 3 桁,3) if mod( 学籍番号の下 3 桁,3). Sortig. Iteral Sortig ( 内部整列 ). 挿入ソート (isertio sort). バブルソート (bubble sort) 3. マージソート (merge sort) 4. クイックソート (quick sort) 3. vector ( ベクタ ) によるSortig. ヒープソート (heap sort) 3 内部整列 (iteral sortig) データはすべて主記憶上に置いて整列. 作業領域を極力減らす.. 比較回数を極力減らす. 外部整列 (exteral sortig) 外部の記憶装置を用いて整列 3. 主記憶と補助記憶との間でのデータ転送回数を極力減らす. 4
逐次入力型 挿入ソート (isertio sort) ヒープソート (heap sort) バッチ型 クイックソート (quick sort) バブルソート (bubble sort) その他 ( 外部整列と共通 ) マージソート (merge sort, 併合ソート ) Java によるデモ ( ページの最後の方 ) http://wiie.kuis.kyoto-u.ac.jp/~okuo/lecture/3/itroalgds/ 5 同じデータ間のもともとの順序が整列後も保存されている整列のこと 基数ソート (radix sort) では重要な性質 辞書式順序で整列で基数ソートが使われる 6. Sortig. Iteral Sortig ( 内部整列 ). 挿入ソート (isertio sort). バブルソート (bubble sort) 3. マージソート (merge sort) 4. クイックソート (quick sort) 3. vector ( ベクタ ) による Sortig. ヒープソート (heap sort) 7
(defie (isert-sort-pred pred records) (if (ull? records) '() (isert-elem pred (car records) (isert-sort-pred pred (cdr records)) ))) (defie (isert-elem pred elem ordered-rec) (cod ((ull? ordered-rec) (cos elem '())) ((pred elem (car ordered-rec)) (cos elem ordered-rec) ) (else (cos (car ordered-rec) (isert-elem pred elem (cdr orderd-rec) ))))) (defie (isert-sort records. args) (isert-sort-pred (if (ull? args) > (car args))) records )) 8 (isert-sort-pred > '( 3 6 4)) 3 6 3 4 3 9. (isert-sort-pred > '( 3 6 4)). (isert-elem > (isert-sort-pred > '(3 6 4)) ) 3. (isert-elem > (isert-elem > 3 (isert-sort-pred > '( 6 4)) )) 4. (isert-elem > (isert-elem > 3 (isert-elem > (isert-sort-pred > '(6 4)) ))) 5. (isert-elem > (isert-elem > 3 (isert-elem > (isert-elem > 6 (isert-sort-pred > '(4)) )))) 6. (isert-elem > (isert-elem > 3 (isert-elem > (isert-elem > 6 (isert-elem > 4 (isert-sort-pred > ()) )))) 0 3
7. (isert-elem > (isert-elem > 3 (isert-elem > (isert-elem > 6 (isert-elem > 4 '()) )))) 8. (isert-elem > (isert-elem > 3 (isert-elem > (isert-elem > 6 '(4)) ))) 9. (isert-elem > (isert-elem > 3 (isert-elem > '(6 4)) )) 0. (isert-elem > (isert-elem > 3 (cos 6 (isert-elem > '(4))) )). (isert-elem > (isert-elem > 3 (cos 6 (cos 4 (isert-elem > '()))) )). (isert-elem > (isert-elem > 3 (cos 6 (cos 4 '())) )) 3. (isert-elem > (isert-elem > 3 (cos 6 (cos 4 '())) )) 4. (isert-elem > (isert-elem > 3 '(6 4 )) ) 5. (isert-elem > (cos 6 (isert-elem > 3 '(4 ))) ) 6. (isert-elem > (cos 6 (cos 4 (isert-elem > 3 '()))) ) 7. (isert-elem > '(6 4 3 )) 8. (cos 6 (isert-elem > '(4 3 ))) 9. (cos 6 (cos 4 (isert-elem > '(3 )))) 0. (cos 6 (cos 4 (cos 3 (isert-elem > '())))). (cos 6 (cos 4 (cos 3 (cos '())))). (6 4 3 ). 最悪の場合 (worst case) (predが とする) 大きなものから順に入ってくる 比較回数は ( i ) ( ) ( ) i. 最良の場合 (best case) 小さいものから順に入ってくる 比較回数は ( ) () i 3. 平均の場合 (average case) すでに入っているデータの半分だけ比較 比較回数は ( i ) ( ) ( i 4 ) 3 4
. Sortig. Iteral Sortig ( 内部整列 ). 挿入ソート (isertio sort). バブルソート (bubble sort) 3. マージソート (merge sort) 4. クイックソート (quick sort) 3. vector ( ベクタ ) によるSortig. ヒープソート (heap sort) 4 (defie (bubble-sort records. args) (let ((pred (if (ull? args) >= (car args))) (size (vector-legth records)) ) (do ((i 0 (+ i ))) ((>= i size) records) (do ((j (- size ) (- j )) (data il) ) ((<= j i)) (set! data (vector-ref records j)) (cod ((pred data (vector-ref records (- j )) ) (vector-set! records j (vector-ref records (- j )) ) (vector-set! records (- j ) data) )))))) 5 9 9 8 5 8 35 8038 807 4 9 8 8 7 5 7357 037 04 9 8 7 7 5 5 3 40 43 0 9 8 7 5 4 3 0 9 8 7 5 4 3 0 9 8 7 5 4 3 0 9 8 7 5 4 3 0 9 8 7 5 4 3 0 6 5
回ごとに敷居 ( ) が つずつ減る i ( i ) ( ) ( ) 7 バブルソート : 隣接データを比較 h= 飛び飛び (h) に比較 h k = 3h k- +,, の時 e.g., 40, 3, 4,.5 ( ) 8. 最悪の場合 (worst case) (predが とする) 小さいものから順に入ってくる 比較回数は ( i ) ( ) i. 最良の場合 (best case) 大きなものから順に入ってくる 比較回数は ( ) () i 3. 平均の場合 (average case) すでに入っているデータの半分だけ比較 比較回数は ( i ) ( ) ( ( ) i 4 ) 9 6
ソート済みのデータを前からマージ ( 併合 ) リスト版 ベクタ版 計算量は両方のデータのスキャンのみ m 個のデータと 個のデータとすると ( m ) 空間計算量も余分に ( m ) 0. Sortig. Iteral Sortig ( 内部整列 ). 挿入ソート (isertio sort). バブルソート (bubble sort) 3. マージソート (merge sort) 4. クイックソート (quick sort) 3. vector ( ベクタ ) によるSortig. ヒープソート (heap sort) 分割統治型 ラン (ru) と言う ( log ) 7
分割統治型 ( ベクタの場合 ) ( log ) 3. Sortig. Iteral Sortig ( 内部整列 ). 挿入ソート (isertio sort). バブルソート (bubble sort) 3. マージソート (merge sort) 4. クイックソート (quick sort) 3. vector ( ベクタ ) によるSortig. ヒープソート (heap sort) 6 (defie (quick-sort records. args) (quick-sort-pred (if (ull? args) > (car args)) records )) (defie (quick-sort-pred pred records) (if (ull? records) '() (let* ((pivot (car records)) (divisio (partitio pred pivot (cdr records) () () ))) (apped (quick-sort-pred pred (car divisio)) (cos pivot (quick-sort-pred pred (cdr divisio) )))))) (defie (partitio pred pivot records left right) (cod ((ull? records) (cos left right)) ((pred pivot (car records)) (partitio pred pivot (cdr records) left (cos (car records) right) )) (else (partitio pred pivot (cdr records) (cos (car records) left) right )))) 7 8
(quick-sort-pred > '( 3 6 4)) (3 6 4) () 3 (6 4) () () () 6 () (4) 4 () () 分割統治法 (divide ad coquor) 8. (quick-sort-pred > '( 3 6 4)). (partitio > '(3 6 4) '() '()) ((3 6 4) ()) 3. (apped (quick-sort-pred > '(3 6 4)) (cos (quick-sort-pred > '()) ) 3-. (partitio > 3 '(6 4) '() '()) ((6 4) ()) 3-. (apped (quick-sort-pred > '(6 4)) (cos 3 ()) ) 4-. (partitio > 6 '(4) '() '()) (() (4)) 4-. (apped () (cos 6 (quick-sort-pred > '(4))) ) 5-. (partitio > 4 '() '() '()) (() ()) 4-3. (apped () (cos 6 (apped () (cos 4 ())))) (6 4) 4-4. (6 4) 9 3-. (partitio > 3 '(6 4) '() '()) ((6 4) ()) 3-. (apped (quick-sort-pred > '(6 4)) (cos 3 ()) ) 3-3. (apped '(6 4) (3)) (6 4 3) 3-4. (apped '(6 4 3) (cos (quick-sort-pred > '()) ) 4-. (partitio > '() '() '()) 4-. (apped '(6 4 3) (cos '()) ) (6 4 3 ) 30 9
. 最悪の場合 (worst case) (predが とする) 小さいものから順に入ってくる partitioでの走査回数は i ( i) ( ) ( ). 最良の場合 (best case) 分割がバランスしている partitio の呼ばれる回数は 3. 平均の場合 (average case) log ( ) ( log ) 3 3. 平均の場合 (average case) データはすべて異なる あらゆる順列が等確率 途中での分割でも同様の仮定が成立するとする 要素のquick sort に要する時間 : T() とする 左右の結果の統合に要する時間 : c (c: 定数 ) 要素がi 要素と-i- 要素に分割されたとすると T() T(i)+T(-i-)+c T ( ) T ( i) T ( i ) c 3 要素の分割 (0,-), (, -),, (-,0) が等確率で生ずるとすると 次の漸化式を得る T( ) c T( i) ( ) T (0) 0 T () 帰納法で証明すると i 0 T ( ) log ( log ) 33 0
(defie (wid-mill paiter colors) (lambda (frame) (set-color (car colors)) (paiter frame) (set-color (cadr colors)) ((rotate90 paiter) frame) (set-color (caddr colors)) ((rotate80 paiter) frame) (set-color (cadddr colors)) ((rotate70 paiter) frame) )) (defie (mouli paiter colors) (lambda (frame) (cod ((pair? colors) (set-color (car colors)) (paiter frame) ((mouli (rotate90 paiter) (cdr colors)) frame) )))) (mouli color-lambda '(red blue gree yellow)) 35 (defie (right-split paiter colors) (lambda (frame) (if (= 0) (paiter frame) (let ((smaller (right-split paiter (- ) (cdr colors))) ) (if (pair? colors) (set-color (car colors))) ((beside paiter below smaller smaller)) frame) )))) (defie (corer-split paiter colors) (lambda (frame) (if (= 0) (paiter frame) (let ((up (up-split paiter (- ))) (right (right-split paiter (- ) (cdr colors))) ) (let ((top-left (beside up up)) (bottom-right (below right right)) (corer (corer-split paiter (- ) (cdr colors))) ) (if (pair? colors) (set-color (car colors))) ((beside (below paiter top-left) (below bottom-right corer) ) frame )))))) (defie (square-limit paiter colors) (let ((quarter (corer-split paiter colors))) (let ((half (beside flip-horiz quarter) quarter))) (below (flip-vert half) half)) )) ((square-limit color-letterlambda 5 '(red gree blue yellow black) ) 36 (defie (palidrome? chars) (equal? chars (reverse chars) ) (defie (make-palidrome chars) (defie (make-eve-palidrome chars) (apped chars (reverse chars)) ) (defie (make-odd-palidrome chars) (apped chars (cdr (reverse chars))) ) (palidrome? '(shi bu shi)) (palidrome? '(ta ke ya bu ya ke ta)) (palidrome? (M A D A M I M A D A M)) (defie (last-but-oe items) (reverse (cdr (reverse items))) ) (last-but-oe '(shi bu shi)) (shi bu ) 37
Quick Sort の正しさを証明せよ. Quick-sort アルゴリズムを書け. Quick-sort の最良計算量を求めよ 3. Quick-sort の最悪計算量を求めよ 4. Quick-sort の平均計算量を求めよ以上の説明 証明をPDFで作成し, SICP-3@zeus.kuis.kyoto-u.ac.jp に送付 38. 教科書 -3-3 を読み, 汎用演算システムの場合を参考にして, 多項式システムを設計する上での課題について述べ, あなたの解決方針を提案しなさい.( 最低 A4 枚, ポイント,sigle space, margiはich 以下 ). ソーティング法をつ調べて, そのアルゴリズムと計算量についてまとめなさい.( 最低 A4 枚, 同様 ) 3. 上記 つのレポートを SICP-@zeus.kuis.kyoto-u.ac.jp に送付 友達に教えてもらったら, 明記すること. Web は出展を明記.(otherwise 回答は減点 ) 39