アルゴリズムとデータ構造
第7週 ＜演習＞木の構造、木の走査、二分木、決定木
2014年11月13日 金岡 晃
授業計画
第1週 (9/25)
データ構造とアルゴリズムの基 礎
第2週 (10/2)
アルゴリズムの効率、線型構造、
スタックと待ち行列 第3週
(10/9)
＜演習＞アルゴリズムの効率、
線型構造、スタックと待ち行列 第4週
(10/16)
文字列照合（KMP法、BM法）
＋＜演習＞
第5週 (10/23)
休講 第6週
(10/30)
木の構造、木の走査、二分木、
決定木
第7週 ＜演習＞木の構造、木の走査、
第9週 (11/27)
休講 第10週
(12/4)
グラフ構造と最短路問題＋
＜演習＞
第11週 (12/11)
データ整列：ヒープソート 法、クイックソート法
第12週 (12/18)
＜演習＞データ整列：ヒー プソート法、クイックソー ト法
第13週 (1/8)
データ探索：ハッシュ法、
木構造探索法 第14週
(1/15)
＜演習＞データ探索：ハッ シュ法、木構造探索法
第 3 回課題の解説
2014/11/13 アルゴリズムとデータ構造
2
演習（その 6 ）
KMP法による文字列照合 KMP法による文字列照合
演習：KMP法によるfailの導出を行うプログラムを作成してみよう 入力：文字列
出力：文字列の長さに応じたfail
第 6 週【復習】
文字列照合（ BM 法）
木の構造、木の走査、二分木、決定木
アルゴリズムとデータ構造
4 2014/11/13 アルゴリズムとデータ構造
BM 法
Boyer-Moore法（BM法）
Boyer-Moore法（BM法）
末尾から照合をしていく場合の照合失敗後のシフト量を
あらかじめパターンから計算をしておき、照合を行っていく
アルゴリズムの流れ
パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算
shiftの計算
パターンの末尾から照合して いくが、照合失敗後のシフト 量はshift[1..m]とλ[1..Σ]に従う
照合
各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算
λの計算
BM 法： λ と shift の利用
2014/11/13 アルゴリズムとデータ構造
6
アルゴリズムの流れ
パターンpat[1..m]より シフト量を決める量 shift[1..m]を計算
shiftの計算
パターンの末尾から照合していくが 照合失敗後のシフト量は
照合を失敗したテキスト場所kの文字text[k]
パターンの場所をiとした場合、
shift[i]と(i- λ[text[k]) の大きい方の分だけシフトする
照合
各文字がpat上で 最も右に現れる 位置λ[1..Σ]の計算
λの計算
BM 法： shift の導出
shiftの導出
（アルゴリズム）
shiftの導出
（アルゴリズム）
第 7 週
＜演習＞文字列照合（ BM 法）
木の構造、木の走査、二分木、決定木
アルゴリズムとデータ構造
8 2014/11/13 アルゴリズムとデータ構造
演習（その 7 ）
BM法による文字列照合 BM法による文字列照合
演習：BM法によるλとshiftの導出を行うプログラムを作成してみよう
入力：文字列
出力：文字の種類に応じたλ、文字列の長さに応じたshift
前提：アルファベット（文字の種類）は3文字（A、B、C）とする
演習（その 8 ）
2014/11/13 アルゴリズムとデータ構造
10
二分木の走査 二分木の走査
演習：下記の二分木を先順・中順・後順でそれぞれ走査したときの、節の訪問 順序を記載せよ
入力：なし（二分木データはプログラム中に記載してよい）
出力：先順、中順、後順
前提：各順での訪問順序 𝐴𝐴
𝐵
𝐵 𝐶𝐶
𝐷
𝐷 𝐸𝐸 𝐹𝐹 𝐺𝐺 𝐻
𝐻 𝐼𝐼 𝐽𝐽
演習（その 9 ）
偽コインの問題 偽コインの問題
演習：8枚のコインから決定木を用いて偽コインを見つけるプログラムを作成し、
天秤で比較される順序と結果を記載せよ 入力：偽コインの指定（0～7）
出力：3回の天秤の比較において、それぞれに載せられるコインとその結果
締切と提出方法：演習その 7 ～ 9
• 締切
– 3週間後（11月20日）の16:10まで
• 提出方法
– 電子メール
• メールアドレス
– メールのタイトルに「アルゴリズムとデータ構造第4回課題」と書 いてください
– 作ったプログラムをメールに添付してください。
• 注意事項
– 必ず金岡から受領確認メールを返します。
• 必ず日本語で受領確認メールを返します
• 英語のメールはエラーメール（アドレスが間違っている）の可 能性が高いです
– メールで提出がされていないものは未提出とみなします
2014/11/13 アルゴリズムとデータ構造
12
中間試験について
アルゴリズムとデータ構造
評価方法とオフィスアワー
•
評価方法–
アルゴリズムとデータ構造• 中間試験 50点
•
期末試験50
点•
合計60
点以上を合格とする–
アルゴリズムとデータ構造演習•
演習課題60
点•
中間試験20
点•
定期試験20
点•
合計60
点以上を合格とする•
オフィスアワー–
オフィスアワーについてはメールで個別に時間を予約するもの とする•
連絡先：[email protected]
2014/11/13 アルゴリズムとデータ構造
14
来週の試験
