Microsoft PowerPoint - Intro-Comp-Sci-07.ppt [互換モード]

Size: px

Start display at page:

Download "Microsoft PowerPoint - Intro-Comp-Sci-07.ppt [互換モード]"

ありあみやのじょう
5 years ago
Views:

情報科学基礎論 -3 007 年 4 月 4 日情報科学基礎論 3. アルゴリズムとデータ構造 Algorthms ad Data Structures 奥乃博 data structure( データ構造 ). 配列. リスト 3. 木構造 4. ハッシング Sortg ( 整列 ). 内部整列. 外部整列 http://we.kus.kyoto-u.ac.

1 情報科学基礎論年 4 月 4 日情報科学基礎論 3. アルゴリズムとデータ構造 Algorthms ad Data Structures 奥乃博 data structure( データ構造 ). 配列. リスト 3. 木構造 4. ハッシング Sortg ( 整列 ). 内部整列. 外部整列 ~okuo/lecture/07/itrocs/ 入力アルゴリズム (Algorthm) アルゴリズム有限回の計算ステップ停止性正当性計算量 (complexty) 時間計算量空間計算量出力 O 記法 ( 上限 ) Ω 記法 ( 下限 ) Θ 記法 ( 上下限 ) 3 データ構造 (Data Structure) データの有限集合しかも動的に要素の数が変化する集合を扱うための表現待ち行列スタックデータ構造の抽象化演算の抽象化オブジェクトベースド : データ構造と演算のカプセル化クラスベースド : クラスとインスタンスの区別オブジェクト指向 : クラス間の階層構造 4 データ構造 : ベクタ (vector) データの並びを表現するデータ型 #( 要素 0 要素 - ) インデックス (dex) は0から始まる (0-org) 要素は任意のデータいわゆる次元配列 (array) Costructor( 構築子 ) (make-vector サイズ [ データ ]) (vector データ 0 データ - ) (lst->vector リスト ) 5 データ構造 : ベクタ (vector)( 続 ) Selectors( 選択子 ) (vector-ref ベクタインデックス ) その他 (vector-legth ベクタ ) サイズを返す (vector-set! ベクタインデックスデータ ) (vector->lst ベクタ ) 入出力は #( 3 4 5) 6 ベクタ (vector) の例 (defe y (make-vector 5)) #(() () () () ()) (defe x #( 3 4 5)) #( 3 4 5) (vector-legth x) 5 (vector-ref x ) 3 (vector-set! x 3 8) #( 3 8 5) x #( 3 8 5) (vector-set! x 0 'foo) #(foo 3 8 5) 7

2 データ構造 : 配列 (array) N 次元にベクタを拡張次元の場合 X=[x j ] 3 次元の場合 X=[x j k ] 基本データ構造待ち行列 ( キュー queue) FIFO(Frst-I Frst-Out) equeue, dequeue スタック (stack) LIFO(Last-I Frst-Out) push, pop 8 データ構造 : リスト (lst) 対 (par) 元セルリスト並び (sequece) (cos l) (lst ) と同じ l は空リスト (lst 3 4) ドット記法 (dotted otato) (cos ) (cos l) (. ) 箱ポインタ記法 (box-ad-poter otato) t ) (cos (cos (cos 3(cos 4 l) ))) (. l) または () 3 4 ( 3 4) あるいは (. (. (3. (4. l)))) 9 前置記法 (prefx otato) 木の辿り方から 3 つの記法への変換式 ( 演算子被演算子 ) operator operads 式の記法前置記法 (prefx otato, Pollsh otato, ポーランド記法 ) +3*45 中置記法 (fx otato) (4 * 5) 後置記法 (postfx otato, reverse Pollsh otato 逆ポーランド記法) * + 木表現はどれも同じ木の辿り方前順走査 (pre-order traversal) ノード左部分木右部分木 + 3 * 4 5 間順走査 (-order tr.) 左部分木ノード右部分木 * 5 後順走査 (post-order tr.) 左部分木右部分木ノード * データ構造 : 木 (tree) 木節節点 (ode) 頂点(vertex ) 枝 (edge, brach) 辺(arc) 根付き木 (rooted tree) 根 (root) 節葉(leaf) 節の深さ (depth): 根からその節までの節数木の高さ (heght): その木に含まれる最大の節の深さデータ構造 : 木 (tree) ( 続 ) 有向木 (drected tree) 親 (paret) 子(chld) 兄弟(sblg) 祖先 (acestor) 子孫(decedet) 順序木 (ordered tree) 根付き木 (rooted tree) かつ子 ( 兄弟 ) に順序付け 3

3 4 月 4 日本日のメニュー data structure( データ構造 ). 配列. リスト 3. 木構造 4. ハッシング Sortg ( 整列 ). 内部整列. 外部整列 4 Sortg ( 整列 ) 内部整列 (teral sortg) データはすべて主記憶上に置いて整列. 作業領域を極力減らす. 比較回数を極力減らす外部整列 (exteral sortg) 外部の記憶装置を用いて整列 3. 主記憶と補助記憶との間でのデータ転送回数を極力減らす 5 Iteral Sortg( 内部整列 ) 逐次入力型. 挿入ソート (serto sort). ヒープソート (heap sort) バッチ型. クイックソート (quck sort). バブルソート (bubble sort) その他 ( 外部整列と共通 ). マージソート (merge sort) 6 安定整列 (stable sortg) 同じデータ間のもともとの順序が整列後も保存されている整列のこと基数ソート (radx sort) では重要な性質辞書式順序で整列で基数ソートが使われる 7 挿入ソート (sert sort). データを前から見て行き適切な場所に入れる. すべてのデータに対して繰り返す例 : 挿入ソート (sert sort) (defe (sert-sort-pred pred records) (f (ull? records) '() (sert-elem pred (car records) (sert-sort-pred pred (cdr records)) ))) (defe (sert-elem pred elem ordered-rec) (cod ((ull? ordered-rec) rec) (cos elem '())) ((pred elem (car ordered-rec)) (cos elem ordered-rec) ) (else (cos (car ordered-rec) (sert-elem pred elem (cdr orderd-rec) ))))) (defe (sert-sort records. args) (sert-sort-pred (f (ull? args) > (car args))) records )) 9 3

4 挿入ソート (sert sort) の実行トレース (sert-sort-pred > '( 3 6 4)) 挿入ソート (sert sort) の計算量. 最悪の場合 (worst case) (predがとする) 大きなものから順に入ってくる比較回数は ( ) = ( ) = O( ). 最良の場合 (best case) ) 小さいものから順に入ってくる比較回数は = ( ) O() = 3. 平均の場合 (average case) すでに入っているデータの半分だけ比較比較回数は ( ) = ( ) O( = 4 ) 4 クイックソート (quck sort). データが個ならば整列終了. データの中からpvot( 枢軸 ) を選ぶ 3. 残りのデータのpvotでそれより大きいグループと小さいグループに分割 4. それぞれのグループについて整列 5. 大きいグループの整列結果 pvot 小さいグループの整列結果を順に並べる例 : クイックソート (quck sort) (defe (quck-sort records. args) (quck-sort-pred (f (ull? args) > (car args)) records )) (defe (quck-sort-pred pred records) (f (ull? records) '() (let* ((pvot (car records)) (dvso (partto pred pvot (cdr records) () () ))) (apped (quck-sort-pred pred (car dvso)) (cos pvot (quck-sort-pred pred (cdr dvso) )))))) (defe (partto pred pvot records left rght) (cod ((ull? records) (cos left rght)) ((pred pvot (car records)) (partto pred pvot (cdr records) left (cos (car records) rght) )) (else (partto pred pvot (cdr records) (cos (car records) left) rght )))) 6 quck sort の実行トレース ( まとめ ) (quck-sort-pred > '( 3 6 4)) (3 6 4) () 3 (6 4) () () () 6 () (4) 4 () () 分割統治法 (dvde ad coquor) 7 クイックソート (quck sort) の計算量. 最悪の場合 (worst case) (predがとする) 小さいものから順に入ってくる parttoでの走査回数は = ( ) = ( + ) = ( ). 最良の場合 (best case) 分割がバランスしている partto の呼ばれる回数は 3. 平均の場合 (average case) O( ) log O( log ) 30 4

5 クイックソート (quck sort) の計算量 3. 平均の場合 (average case) データはすべて異なるあらゆる順列が等確率途中での分割でも同様の仮定が成立するとする要素のquck sort に要する時間 : T() とする左右の結果の統合に要する時間 : c (c: 定数 ) 要素が要素と-- 要素に分割されたとすると T() T()+T(--)+c T ( ) T ( ) + T ( ) + c 3 クイックソート (quck sort) の計算量要素の分割 (0,-), (, -),, (-,0) が等確率で生ずるとすると次の漸化式を得る ( ) = + T c = T () = 0 T (0) = 0 帰納法で証明すると T ( ) ( ) T ( ) log O( log ) 3 クイックソートの補足 pvot のとり方は工夫が必要すでに並んでいる場合には最小あるいは最大要素を pvot に取ると最悪適切な pvot を取れば O( log ) リスト使用の場合は pvot 選択がリスト辿りが必要コストが重いベクタ使用の場合にはコストが軽いピープ (heap) というデータ構造ヒープとは分木の特殊形ヒープの高さをhとすると. 高さh- までは完全分木. 高さh の葉は左詰 3. 親ノードの値 v p と子ノードの値 v c とすると v p pred v c が成立 pred は比較ベクタで実現する h h ピープ (heap) のベクタ表現ヒープの高さを h とすると高さ h- までは完全分木高さ h の葉は左詰ベクタで実現するサイズ0 親のインデックスを子のインデックスは, h h- 39 ピープの諸演算手続き (defe (make-heap maxsze) (let ((heap (make-vector (+ maxsze )))) (vector-set! heap 0 0) heap ))) (defe (heap-sze heap) (vector-ref heap 0)) (defe (heap-left-chld ) (* )) (defe (heap-rght-chld ) (+ (* ) )) (defe (heap-paret ) (quotet )) (defe (heap-top heap) (vector-ref heap )) (defe (heap-sze-set! heap ) (vector-set! heap 0 ) ) 0サ + イズ40 5

6 sert-heap ( ピープに要素挿入 ) (defe (sert-heap heap elemet pred) (let (( (+ (heap-sze heap) ))) (vector-set! heap elemet) (heap-sze-set! heap ) (sft-up heap elemet pred) elemet )) sft-up では高さがつずつ減少 4 sft-up(heap 修復 ) (defe (sft-up heap from elemet pred) (f (<= from ) elemet (let ((paret (heap-paret from))) (let ((value (vector-ref heap paret))) (cod ((pred value elemet) elemet) (else (vector-set! heap from value) (vector-set! heap paret elemet) (sft-up heap paret elemet pred ))))))) 回繰り返すと高さが減少要素数をとすると計算量は O(log ) 4 最大要素の抽出と heap 修復 (defe (heap-extract-top heap pred) (let* ((value (heap-top heap)) ( (heap-sze heap)) (elemet (vector-ref heap )) ) (heap-sze-set! heap (- )) (vector-set! heap elemet) (sft-dow heap (- ) elemet pred) value )) sft-dow では高さがつずつ増加 43 sft-dow(heap 修復 ) (defe (sft-dow heap from to elemet pred) (let ((left-chld (heap-left-chld from)) (rght-chld (heap-rght-chld from)) ) (f (or (>= from to) (> left-chld to)) elemet (let ((max-chld (f (> rght-chld to) left-chld (f (pred (vector-ref heap left-chld) (vector-ref heap rght-chld) ) left-chld rght-chld )))) (let ((max-chld-value (vector-ref heap max-chld))) (cod ((pred elemet max-chld-value) elemet) (else (vector-set! heap from max-chld-value) (vector-set! heap max-chld elemet) (sft-dow heap max-chld to elemet pred )))))))) 44 ヒープソート (heap-sort) (defe (heap-sort records. args) (let ((pred (f (ull? args) >= (car args))) (heap (make-heap 00)) (result ()) ) (for-each (lambda () (sert-heap heap pred)) records) (do (( (legth records) (- )) (result l) ) ((<= 0) (reverse result)) (set! result (cos (heap-extract-top heap pred) result ))))) ヒープソートの計算量 O( log ) 46 ヒープソート (heap-sort) の正しさベクタ x のヒープ成立条件 heap(m,) m +, x x [ ] [ ] [] sft-dow では実行前 : heap(,) の成立は? 実行後 : heap(,3) が成立回目の sft-dow では実行前 :heap(,k) は成立, heap(k,)? 実行後 :heap(k,k+) が成立つまり, heap(,k+) が成立 47 6

7 ヒープソート (heap-sort) の正しさ () ベクタ x のヒープ成立条件 heap(m,) m +, x x [ ] [ ] [] sft-up では実行前 :heap(,) h ) 成立, heap((+)/,+) だけが? 実行後 :heap((+)/4,(+)/) は? 回目の sft-up では実行前 :heap(k/,k)? 他は成立実行後 :heap(k/,) 成立, heap(k/4,k/)? 48 バブルソート (bubble sort) (defe (bubble-sort records. args) (let ((pred (f (ull? args) >= (car args))) (sze (vector-legth records)) ) (do (( 0 (+ ))) ((>= sze) records) (do ((j (- sze ) (- j )) (data l) ) ((<= j )) (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) )))))) 50 バブルソート (bubble sort) 実行トレースバブルソート (bubble sort) の計算量回ごとに敷居 ( ) がつずつ減る == ( ) = ( ) O( ) 5 シェルソート (Shell sort) バブルソート : 隣接データを比較 h= 飛び飛び (h) に比較 h k = 3h k- +,, の時 e.g., 40, 3, 4, O(.5 ) 53 マージソート ( 併合ソート merge sort) ソート済みのデータを前からマージ ( 併合 ) リスト版ベクタ版計算量は両方のデータのスキャンのみ m 個のデータと個のデータとすると O ( m + ) 空間計算量も余分に O ( m + ) 54 7

5 クイックソート (quck sort), 分割統治法 (devde ad coquer) 平均 O ( log ) 最悪 O( ) ヒープソート (heap sort) 常時 O( log ) マージソート (merge sort) 常時 O( log ) ) 57 Sortg( 整列 ) のデモ Java

8 内部マージソート (I-place merge sort) 分割統治型内部マージソート (I-place merge sort) 分割統治型 ( ベクタの場合 ) ラン (ru) と言う O( log )55 O( log ) 56 Sortg( 整列 ) のまとめ選択ソート (selecto sort) 挿入ソート (serto sort) シェルソート (Shell sort) h k = 3h k- +,, の時 k k O( ) O( ) O( 定数小.5 クイックソート (quck sort), 分割統治法 (devde ad coquer) 平均 O ( log ) 最悪 O( ) ヒープソート (heap sort) 常時 O( log ) マージソート (merge sort) 常時 O( log ) ) 57 Sortg( 整列 ) のデモ Java のデモプログラム ~okuo/lecture/07/itroalgds/ 58 Sort( 整列 ) 済ベクタの探索分探索 (bary search) > = < 比較 > = < > = < 分探索の計算量 O(log ) 60 4 月 4 日本日のメニュー Sortg ( 整列 ). 内部整列. 外部整列 data structure( データ構造 ). 配列. リスト 3. 木構造 4. ハッシング 63 8

9 ハッシュ法 (hashg) 探したいデータの範囲膨大例 : 最大 0 文字の単語 50 文字とすると組合わせの数は 0 log(50 ) 0( log ) = 7 ところが実際の単語数は高々 6 0 ベクタ ( 配列 ) で単語を管理すると疎すかすかの配列ハッシュ法 (hasg) を使用 0 64 辞書とハッシュ表 apocope 語尾消失ッapocalypse 黙示シュ値エントリハハッシュ apocrypha 聖書外典 apocalypse apogee 遠地点 apodoss 帰結節 apogee 遠地点 drectaccess table apocope 6 apocrypha 4 apodoss 5 apogee 0 ( 空 ) apocalypse apocrypha apodoss apocope 65 ハッシュ法 (hashg) キーの値の探索なしにアクセスハッシュ関数 (hash fucto) キーハッシュ値 ( 整数 ) ハッシュ表 (hash table) ) サイズ M 占有率 (load factor)α データ量 N α = N M 異なるキーに対してハッシュ値が同じハッシュ値の衝突 (collso) 67 ハッシュ関数 (hash fucto) 設計の指針 : ランダム性を有するものキー : x = a a L key ( x) = m 例 : キーから h ( x) m mod M 例 : 文字列から整数への写像 = h ( x) a code( a ) mod M 例 3: m の中央部分の logm 桁分を使用 h3 ( x) m mod M K where costat K such that MK N 68 ハッシュ法の基本手続き挿入 (sert) hash 表に key を持つデータを挿入検索 (member) hash 表からkeyでデータを検索削除 (delete) hash 表から key を持つデータを削除ハッシュ値衝突 (collso) 対処法チェイン法 (chag, separate chag, 連鎖法内部ハッシュ法 ) 開番地法 (ope addressg, オープン法外部ハッシュ法 ). 線形走査法 (lear probg). 万能ハッシュ法 (uversal hashg) 3. 重ハッシュ法 (double hashg) h, gとすると h(x), h(x)+g(x), h(x)+g(x), h(x)+3g(x),

10 dog curb brd チェイン法 brd ハッシュ値の衝突 Backet( バケツ ) を作りつないで行くチェイン法の平均最悪計算量. 挿入 Θ(N). 検索 Θ(N) 3. 削除 Θ(N) 7 内部ハッシュ法 (teral hashg) ハッシュ関数 h α = 占有率 α エントリに状態を導入 N M < /deleted/key( データ ). 挿入 : /deleted というフラグのあるエントリに入れる. 検索 : /deletedまで探す 3. 削除 : deletedというフラグを立てる deleted キーデータキーデータ 7 線形走査法 (lear probg) ハッシュ関数 h 衝突発生時 h h+ mod M 挿入 /deleted というフラグのあるエントリに入れる検索 /deletedまで探す削除 deletedというフラグを立てる 73 万能ハッシュ法 (uversal hashg) ハッシュ関数 h, ハッシュ関数をランダムに選択挿入 /deleted というフラグのあるエントリに入れる検索 /deletedまで探す削除 deletedというフラグを立てる 74 重ハッシュ法 (double hashg) ハッシュ関数 h, g 衝突発生時 h h+g mod M 挿入 /deleted というフラグのあるエントリに入れる検索 /deletedまで探す削除 deletedというフラグを立てる 75 線形走査法 (lear probg) の例. h(dog)=. h(kyoto)=4 3. h(uv)=0 4. h(iformatcs)= 5. h(sicp)=3 6. h(test)=

11 線形走査法の挿入の計算量. 個のデータが格納 + 個目のデータを挿入するときにh (x) が回目で空いている確率 + L M M M M +. 空きセルを見つけるまでの比較回数 M ( ) L( + ) M + + = = M ( M ) L( M + ) = M M 3. ハッシュ表にN 個のデータを挿入する手間は N M N M dx = M log M x e 0 = 0 M M N M 77 線形走査法の挿入の計算量 ( 続 ) 4. 回あたりの平均の挿入の手間は M M loge loge( α) N M N + α Computatoal Complexty /(-α) -/α log (-α) Load Factor load factor α α loge( α) α 78 線形走査法の検索の計算量. deleted はないものと仮定. 表にキーがない時は =N の挿入と同じ M = M N α 3. 表にキーがある時 M M loge loge( α) N M N + α 4. 削除も検索と同じ 5. 上記の解析は一様ハッシュ (uform hashg) を仮定 : キーの探索列ランダム 79 線形走査法の削除の計算量. deleted はないものと仮定. 表にキーがない時は =N の挿入と同じ 3. 表にキーがある時 M = M N α M M loge loge( α) N M N + α 8 ハッシュ表というデータ構造 (defe (quck-sort records. args) (quck-sort-pred (f (ull? args) > (car args)) records )) (defe (quck-sort-pred pred records) (f (ull? records) l (let* ((pvot (car records)) (dvso (partto pred pvot (cdr records) l l)) ) (apped (quck-sort-pred pred (car dvso)) (cos pvot (quck-sort-pred pred (cdr dvso)) ))))) (defe (partto pred pvot records left rght) (cod ((ull? records) (cos left rght)) ((pred pvot (car records)) (partto pred pvot (cdr records) left (cos (car records) rght) )) (else (partto pred pvot (cdr records) (cos (car records) left) rght )))) (defe (sert-sort records. args) (sert-sort-pred (f (ull? args) > (car args))) records )) 8 レポート課題 : 5 月日午後 5 時締切どれかつアルゴリズムを選び次の課題を行え. アルゴリズムを説明せよ今日習ったアルゴリズムご自身の研究に関係するアルゴリズム. アルゴリズムの挙動を表示 ( 可視化 ) するプログラムを作成せよ MATLAB Java などでレポートとプログラムはメイルで提出のこと okuo@.kyoto-u.ac.jp 83

Microsoft PowerPoint - IntroAlgDs ppt

Microsoft PowerPoint - IntroAlgDs ppt アルゴリズムとデータ構造入門 -4 006 年月 7 日アルゴリズムとデータ構造入門 Sorting( 整列 ) Hashing( ハッシュ法 ) 奥乃博年前の今朝阪神淡路大震災犠牲者死者だけで 6434 人天災は忘れた頃にやってくる ( 寺田寅彦 ) 天才は忘れた頃にやってくる ( 奥乃博 ) 月 7 日本日のメニュー. vector ( ベクタ ). Sorting ( 整列 ) 3.