PowerPoint プレゼンテーション

基本情報技術概論 I 演習 (第11回)
アルゴリズムとデータ構造
埼玉大学理工学研究科
堀山貴史
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
構文解析
8
逆ポーランド記法とスタック

(３＋７)×(６－１)

逆ポーランド記法では、
３７＋６１－ ×
___________
３
７
３
10
１
６
10
６
10
５
10
50
9
BNF 表記法

(プログラミング) 言語の構文規則を記述するのに利用

例)

<式> ::= <数> | <式> ＋ <式> | <式> － <式>
| <式> × <式> | <式> ／ <式> | ( <式> )
<数> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
( ３＋７ )×( ６－１ )
<数>
<数>
<数>
<数>
<式> <式>
＋
<式>
<式> <式>
－
<式>
<式>
<式>
×
<式>
再帰的な定義
10
BNF 表記法
例) 数値の定義

<数字> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

<数字列> ::= <数字> | <数字列> <数字>

<符号> ::= + | -

<数値> ::= <数字列> | <数字列> E <数字列>
| <数字列> E <符号> <数字列>
例題：どれが <数値> ？
-12
12E-10
+12E-10
+12E10
11
ハッシュ
12
ハッシュ法
ハッシュ表
キー値に対して演算を行うことで、
高速なアクセスを実現する
ハッシュ関数
mod 23
ハッシュ値
1234 mod 23
= 15
13
14
15
16
…
キー
1234
…

(hash)
アイデア）キー値が大きな数字で、要素数が少ない
→ キー値を折りたたんで、配列に
例）名前をキーにした名簿、
プログラミング言語の連想配列
13
衝突
異なるキーのハッシュ値が
同じになること
シ
ノ
ニ
ム
15

ハッシュ関数
mod 23
mod 23
ハッシュ値
1234 mod 23
= 15
13
14
15
16
…
キー
1234
…

ハッシュ表
15
ハッシュ表が混んでいなくて、
ハッシュ関数が適切なら、衝突の確率は低い
→ O( 1 ) 時間でアクセス可能
14
チェーン法
 リンクをたどる

オープンアドレス法
 次のアドレスに移る
(次でも衝突すれば、
さらにその次に移る)
 次のアドレス計算
13
14
15
16
…

…
衝突時の処理
ハッシュ表
…

現アドレス + 1
次のハッシュ関数
…

13
14
15
16
15
16
17
この教材のご利用について




この文面は、TOKYO
TECH OCW の利用
条件を参考にしました
この教材は、以下に示す利用条件の下で、著作権者にわざわざ許諾を
求めることなく、無償で自由にご利用いただけます。講義、自主学習は
もちろん、翻訳、改変、再配布等を含めて自由にご利用ください。
非商業利用に限定

この教材は、翻訳や改変等を加えたものも含めて、著作権者の許
諾を受けずに商業目的で利用することは、許可されていません。
著作権の帰属

この教材および教材中の図の著作権は、次ページ以降に示す著
作者に帰属します。この教材、または翻訳や改変等を加えたもの
を公開される場合には、「本教材 (or 本資料) は
http://www.al.ics. saitama-u.ac.jp/horiyama/OCW/ の教材です
(or 教材を改変したものです」との旨の著作権表示を明確に実施
してください。なお、この教材に改変等を加えたものの著作権は、
次ページ以降に示す著作者および改変等を加えた方に帰属しま
す。
同一条件での頒布・再頒布

この教材、または翻訳や改変等を加えたものを頒布・再頒布する
場合には、頒布・再頒布の形態を問わず、このページの利用条件18
この教材のご利用について

配布場所

http://www.al.ics.saitama-u.ac.jp/horiyama/OCW/

この powerpoint ファイルの著作者

堀山貴史 2007-2009 [email protected]

改変等を加えられた場合は、お名前等を追加してください
図の著作者

p. 4 ～15
 堀山貴史

19

Download Report