基本情報技術概論 I 演習 (第５回) アルゴリズム と データ構造 埼玉大学 理工学研究科 堀山 貴史 1 前回までの復習： データ構造 基本的なデータ構造 配列 (array) リスト (list) その他のデータ構造 スタック (stack) 待ち行列 (queue, キュー) 木 (tree)、２分木 (binary tree) ２分探索木、ヒープ 2 ２分木の走査 3 ２分木の走査順序 先行順 / 前順 (pre order) 根、左部分木、右部分木 中間順 / 間順 (in order) 左部分木、根、右部分木 根 左部分木 右部分木 後行順 / 後順 (post order) 左部分木、右部分木、根 ___________ 4 ２分木の走査順序 中間順 ： 左部分木、根、右部分木 4 × 2 6 ＋ 1 Ａ 3 （Ａ＋Ｂ）×（Ｃ－Ｄ） に対応 － Ｂ 5 Ｃ 7 Ｄ 5 ２分木の走査順序 先行順 ： 根、左部分木、右部分木 1 × 2 5 ＋ 3 4 Ａ ×＋ＡＢ－ＣＤ に対応 ___________ － 6 Ｂ 7 Ｃ Ｄ （ポーランド記法） 後行順 ： 左部分木、右部分木、根 7 × 3 6 ＋ 1 Ａ 2 ＡＢ＋ＣＤ－× に対応 ___________ － Ｂ 4 Ｃ 5 Ｄ （逆ポーランド記法） 7 再帰アルゴリズム 自分自身と同じものを呼び出して 処理を繰り返す手続き 例) n の階乗： n ! = n x ( n – 1 ) ! 1 (n = 0 の場合) F( n ) = 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 ) =4x3x2x1 8 再帰アルゴリズム ２分木の各ノードがもつ記号を出力する再帰的なプログラム Proc ( ノード n ) は、次のように定義される。このプログラム を、図の２分木の根 (最上位のノード) に適用したときの出力 を答えなさい。 + a * - b (H19年度 秋 一部改変) d Proc ( ノード n ) ｛ n に左の子 ℓ があれば Proc ( ℓ ) を呼び出す n に右の子 r があれば Proc ( r ) を呼び出す n に書かれた記号を出力する ｝ c 9 構文解析 10 逆ポーランド記法 と スタック (３＋７)×(６－１) 逆ポーランド記法では、 ３ ７ ＋ ６ １ － × ___________ ３ ７ ３ 10 １ ６ 10 ６ 10 ５ 10 50 11 BNF 表記法 (プログラミング) 言語の構文規則を記述するのに利用 例) <式> ::= <数> | <式> ＋ <式> | <式> － <式> | <式> × <式> | <式> ／ <式> | ( <式> ) <数> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 ( ３ ＋ ７ )×( ６ － １ ) <数> <数> <数> <数> <式> <式> ＋ <式> <式> <式> － <式> <式> <式> × <式> 再帰的な定義 12 BNF 表記法 例) 数値の定義 <数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 <数字列> ::= <数字> | <数字列> <数字> <符号> ::= + | - <数値> ::= <数字列> | <数字列> E <数字列> | <数字列> E <符号> <数字列> 例題： どれが <数値> ？ -12 12E-10 +12E-10 +12E10 13 ハッシュ 14 ハッシュ法 ハッシュ表 キー値に対して演算を行うことで、 高速なアクセスを実現する ハッシュ関数 mod 23 ハッシュ値 1234 mod 23 = 15 13 14 15 16 … キー 1234 … (hash) アイデア） キー値が大きな数字で、要素数が少ない → キー値を折りたたんで、配列に 例） 名前をキーにした名簿、 プログラミング言語の連想配列 15 衝突 異なるキーのハッシュ値が 同じになること シ ノ ニ ム 15 ハッシュ関数 mod 23 mod 23 ハッシュ値 1234 mod 23 = 15 13 14 15 16 … キー 1234 … ハッシュ表 15 ハッシュ表が混んでいなくて、 ハッシュ関数が適切なら、衝突の確率は低い → O( 1 ) 時間でアクセス可能 16 チェーン法 リンクをたどる オープンアドレス法 次のアドレスに移る (次でも衝突すれば、 さらにその次に移る) 次のアドレス計算 13 14 15 16 … … 衝突時の処理 ハッシュ表 … 現アドレス + 1 次のハッシュ関数 … 13 14 15 16 17 18 19 この教材のご利用について この文面は、TOKYO TECH OCW の利用 条件を参考にしました この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を 求めることなく、無償で自由にご利用いただけます。講義、自主学習は もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。 非商業利用に限定 この教材は、翻訳や改変等を加えたものも含めて、著作権者の許 諾を受けずに商業目的で利用することは、許可されていません。 著作権の帰属 この教材および教材中の図の著作権は、次ページ以降に示す著 作者に帰属します。この教材、または翻訳や改変等を加えたもの を公開される場合には、「本教材 (or 本資料) は http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です (or 教材を改変したものです」 との旨の著作権表示を明確に実施 してください。なお、この教材に改変等を加えたものの著作権は、 次ページ以降に示す著作者および改変等を加えた方に帰属しま す。 同一条件での頒布・再頒布 この教材、または翻訳や改変等を加えたものを頒布・再頒布する 場合には、頒布・再頒布の形態を問わず、このページの利用条件20 この教材のご利用について 配布場所 http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/ この powerpoint ファイルの著作者 堀山 貴史 2007-2011 [email protected] 改変等を加えられた場合は、お名前等を追加してください 図の著作者 p. 4 ～17 堀山 貴史 21
© Copyright 2024 ExpyDoc
