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