基本情報技術概論 I 演習（第５回） 埼玉大学 理工学研究科 堀山 貴史

Presentation on theme: "基本情報技術概論 I 演習（第５回） 埼玉大学 理工学研究科 堀山 貴史"— Presentation transcript:

1 基本情報技術概論 I 演習（第５回） 埼玉大学 理工学研究科 堀山 貴史
2011/5/19 基本情報技術概論 I 演習 (第５回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 2008/01/23

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

3 ２分木の走査

4 ２分木の走査順序 先行順 / 前順 (pre order) 根、左部分木、右部分木 中間順 / 間順 (in order)
___________ 先行順 / 前順 (pre order) 根、左部分木、右部分木 中間順 / 間順 (in order) 左部分木、根、右部分木 後行順 / 後順 (post order) 左部分木、右部分木、根 左部分木 右部分木

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

6 ２分木の走査順序 先行順 ： 根、左部分木、右部分木 × ＋ － Ａ Ｄ Ｂ Ｃ 後行順 ： 左部分木、右部分木、根 × ＋ － Ａ Ｂ Ｃ
先行順 ： 根、左部分木、右部分木 × ＋ － Ａ Ｄ Ｂ Ｃ ___________ ×＋ＡＢ－ＣＤ に対応 （ポーランド記法） 後行順 ： 左部分木、右部分木、根 × ＋ － Ａ Ｂ Ｃ Ｄ ___________ ＡＢ＋ＣＤ－× に対応 （逆ポーランド記法）

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

8 再帰アルゴリズム 自分自身と同じものを呼び出して 処理を繰り返す手続き 例) n の階乗： n ! = n x ( n – 1 ) !
自分自身と同じものを呼び出して 処理を繰り返す手続き 例) n の階乗： n ! = n x ( n – 1 ) ! (n = 0 の場合) n x F( n – 1 ) (n ≧ 1 の場合) F( 4 ) = 4 x F( 3 ) = 4 x 3 x F( 2 ) = 4 x 3 x 2 x F( 1 ) = 4 x 3 x 2 x 1 x F( 0 ) = 4 x 3 x 2 x 1 F( n ) =

9 再帰アルゴリズム * d b c - a + (H19年度 秋 一部改変)
２分木の各ノードがもつ記号を出力する再帰的なプログラム Proc ( ノード n ) は、次のように定義される。このプログラムを、図の２分木の根 (最上位のノード) に適用したときの出力を答えなさい。 Proc ( ノード n ) ｛ n に左の子 ℓ があれば Proc ( ℓ ) を呼び出す n に右の子 r があれば Proc ( r ) を呼び出す n に書かれた記号を出力する ｝ * d b c - a +

10 構文解析

11 逆ポーランド記法 と スタック ( ３ ＋ ７ ) × ( ６ － １ ) 逆ポーランド記法では、 ３ ７ ＋ ６ １ － ×
　　　　　３ ７ ＋ ６ １ － × ___________ 10 ６ １ ３ ７ 10 ６ ３ 10 10 ５ 50

12 BNF 表記法 (プログラミング) 言語の構文規則を記述するのに利用 <式> ::= <数> | <式> ＋ <式> | <式> － <式> | <式> × <式> | <式> ／ <式> | ( <式> ) <数> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 例) 再帰的な定義 ( ３ ＋ ７ ) × ( ６ － １ ) <数> <式> ＋ <数> <式> － × <式>

13 BNF 表記法 例) 数値の定義 <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
例) 数値の定義 <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <数字列> ::= <数字> | <数字列> <数字> <符号> ::= + | - <数値> ::= <数字列> | <数字列> E <数字列> | <数字列> E <符号> <数字列> 例題： どれが <数値> ？ E E E10

14 ハッシュ

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

16 衝突 異なるキーのハッシュ値が 同じになること ハッシュ表が混んでいなくて、 → O( 1 ) 時間でアクセス可能 ハッシュ表 … 13
ハッシュ関数が適切なら、衝突の確率は低い → O( 1 ) 時間でアクセス可能 … 13 14 ハッシュ関数 ハッシュ値 15 キー 16 mod 23 1234 mod 23 1234 シノニム = 15 … mod 23 15 15

17 衝突時の処理 チェーン法 リンクをたどる オープンアドレス法 次のアドレスに移る (次でも衝突すれば、 さらにその次に移る)
ハッシュ表 衝突時の処理 … 13 チェーン法 リンクをたどる オープンアドレス法 次のアドレスに移る (次でも衝突すれば、 さらにその次に移る) 次のアドレス計算 現アドレス + 1 次のハッシュ関数 14 15 16 … … 13 14 15 16 …

18

19

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

21 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/
この powerpoint ファイルの著作者 堀山 貴史　 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4 ～17 堀山 貴史