基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史

Slides:



Advertisements
Similar presentations
基本情報技術概論(第2回) 埼玉大学 理工学研究科 堀山 貴史
Advertisements

基本情報技術概論 I 演習(第5回) 埼玉大学 理工学研究科 堀山 貴史
データ構造とアルゴリズム 平成20年度 前期 2年生必修  水曜日 3-4時限.
基本情報技術概論(第10回) 埼玉大学 理工学研究科 堀山 貴史
基本情報技術概論(第12回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの演習 第13回.
2 分探索木 Binary Search Tree 実行可能な操作 計算量 木の高さは,最悪 O(n) n = |A| : 要素の個数
アルゴリズムとデータ構造 第8回 ソート(3).
第10回 整列 ~ バブルソート,挿入ソート,選択ソート~
第11回 整列 ~ シェルソート,クイックソート ~
第11回 整列 ~ バケットソート,基数ソート,ヒープソート~
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
基本情報技術概論(第4回) 埼玉大学 理工学研究科 堀山 貴史
2章 データ構造.
第10回 ソート(1):単純なソートアルゴリズム
データ構造とアルゴリズム 第7回 木 ~ データ構造(3)~.
岩井 儀雄 コンピュータ基礎演習  ー探索、整列ー 岩井 儀雄
データ構造とアルゴリズム 第6回の2 木 ~ データ構造(3)~.
第11講: 平成18年12月 8日 (金) 4限 E352教室 グラフ (1).
エージェントを管理するボスの苦悩 問題 n人のエージェントを部下に持つボスがいる. エージェントは出張・帰還を頻繁に繰り返す.
①データ構造 ②アルゴリズム ③プログラム言語 ④マークアップ言語
ヒープソートの復習.
基本情報技術概論(第8回) 埼玉大学 理工学研究科 堀山 貴史
基本情報技術概論(第3回) 埼玉大学 理工学研究科 堀山 貴史
アルゴリズムとデータ構造 第7回探索のためのデータ構造(1) 2015/11/18 アルゴリズムとデータ構造 2015.
第11回 整列 ~ シェルソート,クイックソート ~
二分探索木によるサーチ.
7-3.高度な木 (平衡木) AVL木 平衡2分木。回転操作に基づくバランス回復機構により平衡を保つ。 B木
情報工学総合演習 D-I 近似アルゴリズム 埼玉大学 理工学研究科 山田 敏規、 橋口 博樹、 堀山 貴史
2009/10/16 いろいろなデータ構造 第3講: 平成21年10月16日 (金) 4限 E252教室 コンピュータアルゴリズム.
アルゴリズムとデータ構造1 2005年7月26日
ソートアルゴリズムの種類 選択ソート (selection sort) バブルソート (bubble sort)
第9回 優先度つき待ち行列,ヒープ,二分探索木
データ構造と アルゴリズム 第七回 知能情報学部 新田直也.
データ構造と アルゴリズム 第六回 知能情報学部 新田直也.
基本情報技術概論(第6回) 埼玉大学 理工学研究科 堀山 貴史
Cプログラミング演習 第10回 二分探索木.
アルゴリズムとプログラミング (Algorithms and Programming)
プログラミング 4 整列アルゴリズム.
2009/10/23 整列アルゴリズム (1) 第4講: 平成21年10月23日 (金) 4限 E252教室 コンピュータアルゴリズム.
プログラミング 4 木構造とヒープ.
明星大学 情報学科 2012年度 後期   情報技術Ⅱ   第8回
基本情報技術概論I (第4回) 埼玉大学 理工学研究科 堀山 貴史
15.cons と種々のデータ構造.
基本情報技術概論(第2回) 埼玉大学 理工学研究科 堀山 貴史
基本情報技術概論(第2回) 埼玉大学 理工学研究科 堀山 貴史
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分
アルゴリズムとデータ構造 第3章 ヒープ 5月31日分の復習
情報数理Ⅱ 第11章 データ構造 平成29年1月18日.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
基本情報技術概論(第10回) 埼玉大学 理工学研究科 堀山 貴史
第9回 優先度つき待ち行列,ヒープ,二分探索木
ハフマン符号長の効率的な求め方.
アルゴリズムとデータ構造 2012年7月2日
基本情報技術概論(第13回) 埼玉大学 理工学研究科 堀山 貴史
基本情報技術概論(第5回) 埼玉大学 理工学研究科 堀山 貴史
アルゴリズムとデータ構造 2011年6月28日
アルゴリズムとデータ構造 2011年6月16日
基本情報技術概論(第5回) 埼玉大学 理工学研究科 堀山 貴史
ヒープソートの復習 第12回.
情報工学概論 (アルゴリズムとデータ構造)
第11回放送授業.
アルゴリズムとデータ構造 2013年7月2日
2009/11/27 グラフ (1) 第9講: 平成21年11月27日 (金) 4限 E252教室 コンピュータアルゴリズム.
平面走査法を使った 一般線分の 交点列挙アルゴリズム
ヒープソート.
ヒープソート.
アルゴリズムとデータ構造 2013年6月20日
参考:大きい要素の処理.
7.木構造 7-1.データ構造としての木 7-2.2分探索木 7-3.高度な木.
Presentation transcript:

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

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

前回までの復習 (アルゴリズム) 問題を解決するための、有限ステップからなる手順 (言葉やフローチャートなどで書く) 線形探索 (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 …

前回までの復習 (アルゴリズム) 2分探索 (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

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

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

2分木の実現法 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 深さ

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

2分木の節点の順序付け 中間順 : 左部分木、根、右部分木 × + - A B C D 4 2 6 (A+B)×(C-D) に対応 1 3 中間順 : 左部分木、根、右部分木 4 × + - A B C D 2 6 (A+B)×(C-D) に対応 1 3 5 7

2分木の節点の順序付け 先行順 : 根、左部分木、右部分木 × + - A D B C 後行順 : 左部分木、右部分木、根 × + - A 先行順 : 根、左部分木、右部分木 1 × + - A D B C 2 5 ___________ ×+AB-CD に対応 (ポーランド記法) 3 4 6 7 後行順 : 左部分木、右部分木、根 7 × + - A B C D 3 6 ___________ AB+CD-× に対応 (逆ポーランド記法) 1 2 4 5

2分探索木 ___________

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

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

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

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

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

ヒープ ___________

親と子の大小関係をそろえる (ヒープ ソートに利用) 親 > 子 なら、根が最大 親 < 子 なら、根が最小 データ構造: ヒープ (heap) ___________ 完全2分木の各節点に、データを格納 親と子の大小関係をそろえる (ヒープ ソートに利用) 親 > 子 なら、根が最大 親 < 子 なら、根が最小 2分探索木との 違いに注意 例) 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

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

アルゴリズム: マージソート (併合ソート) アルゴリズム:  マージソート (併合ソート) ソートされた2つの列 → 1つにマージ(併合)するのは簡単   (各列の先頭を見比べながら、小さい方を取っていく) 1回のマージの実行時間は、要素数に比例 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 終 了 …

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

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

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

この文面は、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 / クリップアート その他 堀山 貴史