基本情報技術概論 (第６回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 1 中間試験 6/5 (木) 7, 8 限 工-12 教室 (この教室) 試験範囲 今日の講義分まで。 基本情報処理概論演習の問題や 情報処理技術者試験ぐらいの難易度です。 ( ただし、４択ではなく、記述式です。) 情報処理技術者試験の過去問 (解答つき) http://www.jitec.jp/ 2 中間試験 持ち込み不可。 荷物はイスの下に。 机の上 や 机の棚に 物がある場合は、 不正行為とみなします。 問題用紙や解答用紙の配布を始めたら、 私語厳禁。（私語も不正行為とみなします。） 3 前回までの復習 （データ構造） 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree)、２分木 (binary tree) ２分探索木、ヒープ この後、すぐ 4 前回までの復習 （アルゴリズム） 問題を解決するための、有限ステップからなる手順 （言葉やフローチャートなどで書く） 線形探索 (linear search) 探索キー 70 A[ ] 1 2 1 2 3 4 5 6 7 8 9 10 5 10 35 50 70 100 110 150 … 先頭から順番に調べる 大きさ n の配列の探索時間 （計算量） O( n ) 5 前回までの復習 （アルゴリズム） A[ ] 1 2 1 2 ２分探索 (binary search) 3 4 5 6 7 8 9 10 11 12 13 14 15 5 10 35 50 70 100 110 150 190 191 200 300 400 探索キー 70 ソートされた配列に対し、高速に探索できる 探索範囲の中央を調べる → 探索キーとの比較で、探索範囲が半分に 計算量 … O( log n ) 6 深さ 0… データ構造： 木 節点 と 辺 （枝 ともいう） からなり 以下の １、２ を満たすもの 1… 2… 3… 1. すべての節点が連結である 2. サイクルを持たない 葉 先祖 親 この節点から見て 子 根 兄弟 子孫 7 データ構造： ___________ ２分木 (binary tree) 各節点の子は、高々２つ 右の子と左の子は、区別する 例) 下の３つは、どれも異なる２分木 完全２分木 8 ２分木の実現法 リスト 2 1 4 2 5 深さ 0 5 7 7 配列 A[ ] 1 3 3 4 1 2 3 1 4 5 6 2 7 節点 i の 左の子 2i 右の子 2i + 1 親 i /2 ________ 9 ２分木の節点の順序付け 先行順 (pre order) 根、左部分木、右部分木 中間順 (in order) 左部分木、根、右部分木 後行順 (post order) 左部分木、右部分木、根 根 左部分木 右部分木 ___________ 10 ２分木の節点の順序付け 中間順 ： 左部分木、根、右部分木 4 × 2 6 ＋ 1 Ａ 3 （Ａ＋Ｂ）×（Ｃ－Ｄ） に対応 － Ｂ 5 Ｃ 7 Ｄ 11 ２分木の節点の順序付け 先行順 ： 根、左部分木、右部分木 × ＋ Ａ ×＋ＡＢ－ＣＤ に対応 ___________ － Ｂ Ｃ Ｄ （ポーランド記法） 後行順 ： 左部分木、右部分木、根 × ＋ Ａ ＡＢ＋ＣＤ－× に対応 ___________ － Ｂ Ｃ Ｄ （逆ポーランド記法） 12 ２分木の節点の順序付け 先行順 ： 根、左部分木、右部分木 1 × 2 5 ＋ 3 4 Ａ ×＋ＡＢ－ＣＤ に対応 ___________ － 6 Ｂ 7 Ｃ Ｄ （ポーランド記法） 後行順 ： 左部分木、右部分木、根 7 × 3 6 ＋ 1 Ａ 2 ＡＢ＋ＣＤ－× に対応 ___________ － Ｂ 4 Ｃ 5 Ｄ （逆ポーランド記法） 13 データ構造： ___________ ２分探索木 ２分木の各節点に、データを格納 節点 v のデータは (1) v のどの左の子孫よりも大きい (2) v の 〃 右 〃 小さい 例） 6 3 1 10 4 8 12 7 14 ２分探索木の操作 探索 探索キー 8 6 3 1 10 4 8 12 7 根から出発 探索キー = 節点のキー … 探索成功 探索キー < 節点のキー … 左の部分木へ 探索キー > 節点のキー … 右の部分木へ 15 ２分探索木の操作 挿入 9 を挿入 6 3 1 10 8 4 7 12 9 探索と同様にして、木をたどる 木から飛び出したところに、新しい節点を加える 16 ２分探索木の操作 削除 10 を削除 6 3 1 10 4 8 12 7 削除するキーを探索して削除 ２分探索木の条件に合うように移動 （子孫も同様） 左部分木の最大値を移動 or 右部分木の最小値を移動 17 データ構造： ___________ ヒープ 完全２分木の各節点に、データを格納 親と子の大小関係をそろえる (ヒープ ソートに利用) 親 > 子 なら、根が最大 親 < 子 なら、根が最小 例） ２分探索木との 7 違いに注意 6 3 5 2 4 1 18 アルゴリズム： ヒープソート (heap sort) ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 1 6 5 6 3 2 4 1 最大値の取り出し 5 6 3 2 4 1 7 最後の葉の移動 3 7 2 4 ヒープの維持 4 6 3 5 5 7 1 2 4 最大値の取り出し 3 5 67 1 2 4 最後の葉の移動 3 1 5 67 2 ヒープの維持 19 アルゴリズム： ヒープソート (heap sort) ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 6 1 5 6 3 2 4 1 最大値の取り出し 計算量 O( 1 ) 3 5 7 2 4 ヒープの維持 計算量 O( log n ) n 回 繰り返し … トータルの計算量 O( n log n ) 20 ハッシュ法 ハッシュ表 キー値に対して演算を行うことで、 高速なアクセスを実現する ハッシュ関数 mod 23 ハッシュ値 1234 mod 23 = 15 13 14 15 16 … キー 1234 … (hash) アイデア） キー値が大きな数字で、要素数が少ない → キー値を折りたたんで、配列に 例） 名前をキーにした名簿 21 ハッシュ法 (hash) ハッシュ表が混んでいなくて、 ハッシュ関数が適切なら、衝突の確率は低い → O( 1 ) 時間でアクセス可能 衝突 … 異なるキーのハッシュ値が同じになること キー ハッシュ関数 ハッシュ値 1234 mod 23 15 15 mod 23 15 衝突時の処理 チェーン法 オープンアドレス法 ハッシュ表 1 5 22 23 アルゴリズム： バブルソート (隣接交換法) 隣り合うデータを見比べて、大小関係が逆なら交換 小 大 小 が バ ラ 大 バ ラ 20 30 5 10 1 20 30 5 見比べて 1 交換 10 1 20 30 5 10 1 20 5 30 10 20 30 1 5 10 1 確定 20 バ 30 ラ バ 5 ラ 10 20 1 30 5 10 1 5 確定 20 バ ラ 30 バ 10 ラ … 24 アルゴリズム： n個 バブルソート (隣接交換法) 計算量 1 20 30 5 10 確定 1 5 20 30 10 1 確定 5 10 20 30 １個目を確定させるのに ２個目 比較が n – 1 回 n–2回 確定 … 1 5 10 20 30 ３個目 … n - 1 個目 n–3回 … 1回 全部で O( n2 ) 25 26 アルゴリズム： マージソート ソートされた２つの列 → １つにマージ（併合）するのは簡単 （各列の先頭を見比べながら、小さい方を取っていく） 5 20 25 50 (併合ソート） 1 10 30 40 １回のマージの実行時間は、要素数に比例 27 アルゴリズム： マージソート (併合ソート） 5 25 50 20 30 40 10 1 5 25 50 20 5 25 5 25 5 25 30 40 10 1 50 20 50 20 20 50 30 40 30 40 30 40 分割 10 1 10 log n 段 1 1 10 マージ log n 段 1 段に O( n ) 時間 → 全部で O( n log n ) 時間 29 アルゴリズム： 番兵付き の 線形探索 ループの中の比較回数を減らす 開始 1→i K → A(n+1) Yes A(i) = K No i+1→i n： 配列の要素数 K： 探索キー i>n No Yes 探索成功 の処理 100 K 70 i A [1] 30 A [2] 50 A [3] 20 A [4] 70 A [5] 10 … 終了 探索失敗 の処理 n 30 アルゴリズム： 線形探索 (linear search) 配列を先頭から順番に探索する 開始 n： 配列の要素数 K： 探索キー 1→i i>n No n 100 K 70 i Yes Yes A(i) = K No i+1→i 探索成功 の処理 30 A [2] 50 A [3] 20 A [4] 70 A [5] 10 … 終了 探索失敗 の処理 A [1] 31 32 この教材のご利用について この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を 求めることなく、無償で自由にご利用いただけます。講義、自主学習は もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許 諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著 作者に帰属します。この教材、または翻訳や改変等を加えたもの を公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施 してください。なお、この教材に改変等を加えたものの著作権は、 次ページ以降に示す著作者および改変等を加えた方に帰属しま す。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する 場合には、頒布・再頒布の形態を問わず、このページの利用条件33 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史 2007-2009 [email protected] 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 5, 6, 15 ～ 18 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史 34
© Copyright 2024 ExpyDoc
