解説スライド

平成 23 年 8 月 4 日
担当教員：山口
データ構造とアルゴリズム II
試験問題 冊子
• 試験時間は本ページの説明も含めて 90 分です．資料持込可
です．
• 全ての解答用紙に学籍番号と氏名を丁寧に記入して下さい．
科目名は「DA2」で構いません．
• 問 1 ∼ 8 の中から 4 問を選んで解答して下さい．配点は全て
25 点です．
• 5 問以上に解答した場合は減点します．採点を望まない解答
を書いてしまった場合は大きく×印を付けて下さい．
• 問題文の意味を理解し，グラフ等の問題として定式化するこ
とも採点対象です．それに関する質問には答えられないこと
もあります．
• 設問の中には授業で習った内容だけでは答えられないものも
含まれます．それらも他の問題と同等の基準で採点します．
• 教科書に載っていないアルゴリズムを使う場合は手順および
計算量を明記すること．
• 授業評価アンケートに回答して下さい．回答が終わったら，
宛先「[email protected]」，件名「DA2 アンケート回答済み」
のメールを送って下さい．本文には学籍番号・氏名をお書き下
さい．よろしければ本講義に対するコメントもお願いします．
• 試験結果が思わしくない者には追加レポートを実施します．
詳細については８月１１日 (木) 以降，学科掲示板か授業ホー
ムページ (http://www2.kobe-u.ac.jp/∼ky/da2/) で確認し
て下さい．
問1
(1) パターン p = aaaab に対するクヌース・モーリス・プラット
のアルゴリズムの失敗関数を，関数 compf（教科書 p.85 図
5.5）に従って計算しなさい．計算過程を明記すること．
(2) テキスト t = aaabaaaaaba に対してクヌース・モーリス・プ
ラットのアルゴリズムの関数 kmp（教科書 p.85 図 5.4） を
実行したとき，変数 j, i の値はどのように変化するか，その
遷移の様子を示しなさい．
遷移の記述例：(j, i) の順に：(1, 1) → (2, 2) → (2, 3) → 終了
ＫＭＰのアルゴリズムを使う．
問2
自宅の庭に噴水付きの池を作ろうとしています．作業内容とそ
れにかかる手間，作業の依存関係について以下の表にまとめます．
作業番号
1
2
3
4
5
6
7
8
9
10
作業内容
設計
旧塀撤去
池堀り
セメント搬入
噴水工事
木材の搬入
塀新設
型枠固定
コンクリート打ち
撤収
手間
2
5
6
4
6
4
7
4
8
2
着手前に完了すべき仕事
（なし）
設計
設計
設計
池堀り
設計，旧塀撤去
木材の搬入
木材の発注，噴水工事
セメント搬入，噴水工事，型枠固定
塀新設，コンクリート打ち
(1) 上記の各作業には，手間に比例した時間がかかるものとしま
す．このとき，設計を開始してから撤収が完了するまでの時
間を求める問題は，どのような最適化問題になるかを答えな
さい．
(2) 上記の問題の解を求めるアルゴリズムとその計算量を示し
なさい．そのアルゴリズムを用いて完了までの時間を求めな
さい．
閉路のない有向グラフの最長路を求める問題 (PERT)
問3
(1) ネットワーク上にメインサーバ A と ミ
A B C D E
ラーサーバ B, C, D, E があり，サーバ A
からあるデータを全てのミラーサーバに転
A
–
7
5
6 10
送しようとしています．2 つのサーバ間で
B
7
–
9
2
8
データを転送する際の費用は右の表の通り
C
5
9
–
3
1
とします．
D
6
2
3
–
4
E 10 8
1
4
–
例えば，全てのミラーサーバに対し A から直接データを
送った場合，7 + 5 + 6 + 10 = 28 という費用がかかります．
A から B にデータを転送し，さらに B から C，C から D，
D から E と順々にデータを転送した場合，7 + 9 + 3 + 4 = 23
という費用がかかります．
この状況下で，費用最小の通信経路を求める問題はどのよ
うな最適化問題になるかを示しなさい．また，その最適解を求
めるアルゴリズムを実行し，通信コスト最小のリンクの集合
を求めなさい．集合は，例えば {(A, B), (B, C), (C, D), (D, E)}
のように記します．使用したアルゴリズムと計算過程を明記
すること．
最小スパニング木，Kruskal のアルゴリズム
(2) ネットワーク上にメインサーバ A と ミラーサーバ B, C,
D, E があり，サーバ A からあるデータを全てのミラーサー
バに遅延時間の総和が最小となるように転送しようとしてい
ます．サーバ間のデータ転送時間は前問で示した表の通りと
します．例えば，A から B にデータを転送し，さらに B か
ら C，C から D，D から E と順々にデータを転送した場合，
遅延の総和は 7 + (7 + 9) + (7 + 9 + 3) + (7 + 9 + 3 + 4) = 65
となります．
この状況下で，遅延最小の通信経路を求める問題はどのよ
うな最適化問題になるかを示しなさい．また，その最適解を求
めるアルゴリズムを実行し，通信コスト最小のリンクの集合
を求めなさい．集合は，例えば {(A, B), (B, C), (C, D), (D, E)}
のように記します．使用したアルゴリズムと計算過程を明記
すること．
最短経路問題，Dijkstra のアルゴリズム
問4
与えられた 2 進数を規則に従って書き換え，全ての桁を 0 に
するパズルがあります．1 回の手順で行えるのは以下のいずれか
です．
• 最下桁の数字を他の数字に書き換える．
• 下 2 桁の数字が同じとき，下 2 桁を同時に他の数字に書き換
える．
• 下から k 番目の桁が 1 で，それより下の桁が全て 0 のとき，
下から k + 1 番目の桁の数字を他の数字に書き換える．
例えば，1100 という数は，最初の規則により 1101 に，2 番目
の規則により 1111 に，3 番目の規則により 0100 に書き換えられ
ます．
1111 が与えられたときに 0000 に書き換える最小の手順を求
めるパズルをグラフの問題として解きます．以下の問いに答えな
さい．
(1) 4 桁の 2 進数は全部で 16 個ありますが，それらに対応する 16
個の頂点があり，1 回の手順で書き換えられる 2 頂点間に無
向辺があるようなグラフを描きなさい．各頂点は，下図のよ
うに丸の中に 2 進数を書いて下さい．
(2) 上設問で作成したグラフにおいて全ての辺の重みを 1 とした
ときの，頂点 1111 から頂点 0000 への最短経路を求めなさ
い．使用したアルゴリズムおよび計算過程を明記すること．
(3) 全ての桁が 1 であるような n 桁の 2 進数が与えられたとき
に全ての桁が 0 になるように書き換える最短手順数を n の
式で表しなさい．
（参考）上記のパズルはチャイニーズリングと呼ばれる知恵の
輪を解く手順を数字のパズルとして表したものです．
チャイニーズリング（初期状態と完成図）
グラフを描けば，幅優先探索で解ける．
問5
エドモンズ・カープのアルゴリズムを用いて
右図のネットワークにおける頂点 s から頂点 t
への最大フローを求めます．ただし，各辺に付
けられた数は，各辺の容量を表しているものと
します．以下の問いに答えなさい．
(1) 増分路にフローを流す処理を 2 回行った後の残余グラフを示
しなさい．
(2) 前問の残余グラフにおける増分路を求め，その増分路上に現
れる頂点を s から順に示しなさい（記述例：s → v3 → v1 →
t）．
(3) 最大フローを求め，その値が最適であることを証明しなさい．
問6
(1) 7 人の学生に対し面接を行います．面接の候補日は 6 日間で，
各人の都合の良い日には○が記されています．学生の都合と
日程の関係を表現するような 2 部グラフを図示しなさい．
1 日目 2 日目 3 日目 4 日目 5 日目 6 日目
Andy
○
○
Bob
○
Cindy
○
Fred
Gale
○
○
Dora
Edo
○
○
○
○
○
○
○
○
○
(2) 面接は候補日のうち 3 日だけ実施するものとします．各人が
実施日のうち少なくとも 1 日は都合が良いような実施スケ
ジュールを求めなさい．アルゴリズムと計算過程を明記する
こと．
(3) 前問で用いたアルゴリズムについて，人数が n 人，候補日
が m 日あり，そのうち k 日に面接を実施するような実施ス
ケジュールを求めた場合の時間計算量を示しなさい．
一見，マッチングに見えるが，面接を実施する日数に制限があ
るので簡単には解けない．
問7
(1) 8 人の学生が 2 人ペアを 4 組作ろ
うとしています．各人は組む相手
学生
希望する相手
の希望を表の通りに出していま
Andy
Bob, Cindy
す．学生の希望を表現するような
Bob
Andy, Cindy, Dora
グラフを図示しなさい．頂点は丸
Cindy Andy, Bob, Edo
の中に各人の頭文字を書くだけ
Dora
Bob, Edo
で構いません．
Edo
Cindy, Dora, Fred
Fred
Edo, Gale, Heidi
Gale
Fred, Heidi
Heidi
Fred, Gale
(2) 全員の希望を満たすようなペア 4 組を求めなさい．アルゴリ
ズムと計算過程を明記すること．
(3) 学生が n 人いる場合に前問で用いたアルゴリズムを用いた
ときの時間計算量を求めなさい．
こちらはマッチングの問題だが，2 部グラフではない！
問8
3 種 類 の 薬 品 C1 , C 2 , C 3
から製品
P1 , P2 , P3 を作ります．各製品の単価と，各
製品を 1 単位作るのに必要な薬品の単位数
は右表の通りです．このとき，以下の設問
に答えなさい．
単価
C1 C2 C3
P1
50
1
2
1
P2
60
2
1
1
P3
100
1
1
4
(1) 薬品 C1 , C2 , C3 がそれぞれ 90, 110, 160 単位ずつあるとき，
製品の総額が最大になるような製造量を求める線形計画問題
を示しなさい．
(2) 前問で示した線形計画問題を標準形に直しなさい．
(3) 前問の線形計画問題を解き，最適解とその目的関数の値を示
しなさい．