基本情報技術概論（第６回） 埼玉大学 理工学研究科 堀山 貴史 2009/11/25 中間試験 12/9 (水) 5,6限 教室未定 基本情報技術概論 (第６回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

前回までの復習 （データ構造） 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree)、２分木 (binary tree) ２分探索木、ヒープ この後、すぐ

前回までの復習 （アルゴリズム） 問題を解決するための、有限ステップからなる手順 （言葉やフローチャートなどで書く） 線形探索 (linear search) 先頭から順番に調べる 大きさ n の配列の探索時間 （計算量） O( n ) A [ ] 探索キー 70 1 2 3 4 5 6 7 8 9 10 1 2 5 10 35 50 70 100 110 150 …

前回までの復習 （アルゴリズム） ２分探索 (binary search) ソートされた配列に対し、高速に探索できる 探索範囲の中央を調べる → 探索キーとの比較で、探索範囲が半分に 計算量 … O( log n ) A [ ] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1 2 5 10 35 50 70 100 110 150 190 191 200 300 400 探索キー 70

節点 と 辺 （枝 ともいう） からなり 以下の １、２ を満たすもの 深さ 根 0 … 1 … 2 … 3 … すべての節点が連結である データ構造： 木 (tree) 深さ 根 0 … 節点 と 辺 （枝 ともいう） からなり 以下の １、２ を満たすもの 1 … 2 … 3 … すべての節点が連結である サイクルを持たない 葉 親 先祖 この節点から見て 兄弟 子 子孫

データ構造： ２分木 (binary tree) ___________ 各節点の子は、高々２つ 右の子 と 左の子 は、区別する 例) 下の３つは、どれも異なる２分木 完全２分木 … 20 個 … 21 個 … 22 個

２分木の実現法 1 2 3 リスト 配列 1 4 5 7 2 3 4 5 7 節点 i の 左の子 2i 右の子 2i + 1 親 i /2 ________ A [ ] 1 2 3 4 5 6 7 深さ

２分木の節点の順序付け 先行順 (pre order) 根、左部分木、右部分木 中間順 (in order) 左部分木、根、右部分木 ___________ 先行順 (pre order) 根、左部分木、右部分木 中間順 (in order) 左部分木、根、右部分木 後行順 (post order) 左部分木、右部分木、根 左部分木 右部分木

２分木の節点の順序付け 中間順 ： 左部分木、根、右部分木 × ＋ － Ａ Ｂ Ｃ Ｄ 4 2 6 （Ａ＋Ｂ）×（Ｃ－Ｄ） に対応 1 3 中間順 ： 左部分木、根、右部分木 4 × ＋ － Ａ Ｂ Ｃ Ｄ 2 6 （Ａ＋Ｂ）×（Ｃ－Ｄ） に対応 1 3 5 7

２分木の節点の順序付け 先行順 ： 根、左部分木、右部分木 × ＋ － Ａ Ｄ Ｂ Ｃ 後行順 ： 左部分木、右部分木、根 × ＋ － Ａ 先行順 ： 根、左部分木、右部分木 1 × ＋ － Ａ Ｄ Ｂ Ｃ 2 5 ___________ ×＋ＡＢ－ＣＤ に対応 （ポーランド記法） 3 4 6 7 後行順 ： 左部分木、右部分木、根 7 × ＋ － Ａ Ｂ Ｃ Ｄ 3 6 ___________ ＡＢ＋ＣＤ－× に対応 （逆ポーランド記法） 1 2 4 5

２分探索木 ___________

２分木の各節点に、データを格納 節点 v のデータは (1) v のどの左の子孫よりも大きい (2) v の 〃 右 〃 小さい 6 3 データ構造： ２分探索木 ___________ ２分木の各節点に、データを格納 節点 v のデータは (1) v のどの左の子孫よりも大きい (2) v の 〃 右 〃 　 小さい 例） 6 3 10 最小 → 1 4 8 12 ← 最大 7

２分探索木の操作 探索 6 3 10 1 4 8 12 7 探索キー 8 根から出発 探索キー < 節点のキー … 左の部分木へ 探索キー = 節点のキー … 探索成功 探索キー < 節点のキー … 左の部分木へ 探索キー > 節点のキー … 右の部分木へ

２分探索木の操作 追加 6 3 10 1 4 8 12 9 7 9 を追加 探索と同様にして、木をたどる 木から飛び出したところに、新しい節点を加える

２分探索木の操作 削除 6 3 10 1 4 8 12 7 10 を削除 削除するキーを探索して削除 ２分探索木の条件に合うように移動 （子孫も同様） 左部分木の最大値を移動 or 右部分木の最小値を移動

練習：　２分探索木 次の２分探索木から要素12を削除したとき、その位置に別の要素を移動するだけで２分探索木を再構成するには、削除された要素の位置にどの要素を移動すればよいか。 (H16年度 秋 一部改変) 6 4 8 ア. 10　　　イ. 11 ウ. 14　　　エ. 15 イ 3 2 5 7 12 1 3 10 14 9 11 13 15

ヒープ ___________

親と子の大小関係をそろえる (ヒープ ソートに利用) 親 > 子 なら、根が最大 親 < 子 なら、根が最小 データ構造： ヒープ (heap) ___________ 完全２分木の各節点に、データを格納 親と子の大小関係をそろえる (ヒープ ソートに利用) 親 > 子 なら、根が最大 親 < 子 なら、根が最小 ２分探索木との 違いに注意 例） 9 6 7 3 2 4 1

ヒープの操作 探索 最大値は？ 7 6 5 3 2 4 1 値を順に追加 最大値を順に取り出す (最大値を探索 & 削除) ヒープ ソート

ヒープの操作 追加 8 を追加 7 6 5 3 2 4 1 8 ヒープの最後 (深さ最大、左詰め) に新しい節点を追加 ヒープの維持

ヒープの操作 削除 7 1 6 5 6 5 3 2 4 1 3 2 4 7 を削除 ヒープの最後を削除する節点に追加移動 ヒープの維持

アルゴリズム： ヒープソート (heap sort) ヒープの最大値の取り出し、ヒープの維持を繰り返す 4 7 6 5 3 2 1 7 1 7 4 6 5 3 2 1 7 4 5 3 2 6 1 最大値の取り出し 最後の葉の移動 ヒープの維持 7 4 3 5 1 2 6 6 4 6 7 4 3 5 1 2 6 7 3 1 2 5 4 最大値の取り出し 最後の葉の移動 ヒープの維持

アルゴリズム： ヒープソート (heap sort) ヒープの最大値の取り出し、ヒープの維持を繰り返す 7 1 6 5 6 5 3 2 4 1 3 2 4 7 最大値の取り出し ヒープの維持 計算量 O( 1 ) 計算量 O( log n ) n 回 繰り返し … トータルの計算量 O( n log n )

ハッシュ法 (hash) キー値に対して演算を行うことで、 アイデア） キー値が大きな数字で、要素数が少ない ハッシュ表 キー値に対して演算を行うことで、 高速なアクセスを実現する アイデア） キー値が大きな数字で、要素数が少ない → キー値を折りたたんで、配列に 例） 名前をキーにした名簿 … 13 14 ハッシュ関数 ハッシュ値 15 キー 16 mod 23 1234 mod 23 1234 = 15 …

ハッシュ法 (hash) ハッシュ表が混んでいなくて、 → O( 1 ) 時間でアクセス可能 ハッシュ関数が適切なら、衝突の確率は低い → O( 1 ) 時間でアクセス可能 衝突 … 異なるキーのハッシュ値が同じになること 衝突時の処理 チェーン法 オープンアドレス法 ハッシュ関数 ハッシュ値 ハッシュ表 キー mod 23 15 1234 15 mod 23 15 15

アルゴリズム： バブルソート (隣接交換法) アルゴリズム：　 バブルソート (隣接交換法) 隣り合うデータを見比べて、大小関係が逆なら交換 確定 小 20 20 20 20 1 大小がバラバラ 30 30 30 1 20 バラバラ 5 5 1 30 30 10 見比べて交換 1 5 5 5 大 1 10 10 10 10 1 1 1 20 20 5 確定 … 30 5 20 バラバラ 5 30 30 10 10 10

アルゴリズム： バブルソート (隣接交換法) 基本情報技術概論（第６回） 2009/11/25 アルゴリズム：　 バブルソート (隣接交換法) 計算量 1 確定 1 1 1 20 5 確定 5 5 … n 個 30 20 10 確定 10 5 30 20 20 10 10 30 30 １個目を確定させるのに 比較が n – 1 回 ２個目 n – 2 回 ３個目 n – 3 回 … n - 1 個目 1 回 … 全部で O( n2 )

アルゴリズム： マージソート (併合ソート） アルゴリズム：　 マージソート (併合ソート） ソートされた２つの列 → １つにマージ（併合）するのは簡単 　　（各列の先頭を見比べながら、小さい方を取っていく） １回のマージの実行時間は、要素数に比例 5 20 25 50 1 10 30 40

アルゴリズム： マージソート (併合ソート） アルゴリズム：　 マージソート (併合ソート） 5 25 50 20 30 40 10 1 50 25 5 20 10 40 30 1 分割 log n 段 25 5 20 50 40 30 1 10 5 25 50 20 30 40 10 1 25 5 50 20 40 30 10 1 log n 段 マージ 1 段に O( n ) 時間 → 全部で O( n log n ) 時間

ループの中の比較回数を減らす n 100 n： 配列の要素数 K： 探索キー 開 始 K 70 i 1 → i K → A(n+1) Yes アルゴリズム：　番兵付き の 線形探索 ループの中の比較回数を減らす n 100 n： 配列の要素数 K： 探索キー 開 始 K 70 i 1 → i K → A(n+1) Yes A [1] 30 A(i) = K Yes No i > n A [2] 50 No A [3] 20 i + 1 → i A [4] 70 探索成功の処理 探索失敗の処理 A [5] 10 終 了 …

アルゴリズム： 線形探索 (linear search) 配列を先頭から順番に探索する n 100 開 始 n： 配列の要素数 K： 探索キー K 70 1 → i i Yes i > n A [1] 30 No Yes A [2] 50 A(i) = K A [3] 20 No 探索成功の処理 探索失敗の処理 A [4] 70 i + 1 → i A [5] 10 終 了 …

「全学向け」 用に、「情報向け」 から 抜いたものを、以下に置く

２分木の実現法 1 情報向け 2 3 リスト 配列 1 4 5 7 2 3 4 5 7 節点 i の 左の子 2i 右の子 2i + 1 ________ A [ ] 1 2 3 4 5 6 7 深さ

練習：　データ構造 データ構造に関する記述のうち、適切なものはどれか。 ア. ２分木は、データ間の関係を階層的に表現する木構造の一種であり、すべての節が２つの子をもつデータ構造である。 イ. スタックは、最初に格納したデータを最初に取り出す先入れ 先出しのデータ構造である。 ウ. リストは、データ部と次のデータの格納先を指すポインタ部 から構成されるデータ構造である。 エ. 配列は、ポインタの付替えだけでデータの挿入 ・ 削除が できる構造である。

この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材のご利用について この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を求めることなく、無償で自由にご利用いただけます。講義、自主学習はもちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著作者に帰属します。この教材、または翻訳や改変等を加えたものを公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施してください。なお、この教材に改変等を加えたものの著作権は、次ページ以降に示す著作者および改変等を加えた方に帰属します。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する場合には、頒布・再頒布の形態を問わず、このページの利用条件に準拠して無償で自由に利用できるようにしてください。

この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史　2007-2010 horiyama@al.ics.saitama-u.ac.jp 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 3, 4, 14 ～ 17, 19 ～ 22, 40 クリップアート : Microsoft Office Online / クリップアート その他 堀山 貴史