解説スライド

試験について
• 7 月 31 日（木）2 限，LR–501
• 90 分，持込可．選択式（詳細は未定）．
• 合格点に達しない方にはレポートを提出し
て頂きます（合格点以上の人が解いた場合
は追加点をあげます）．
平成２５年度定期試験の解説
• 以下では平成２５年度の試験問題の解説を
行います．
問１：ストリングマッチング
• 失敗関数 compf（教科書 p.85 図 5.5）の
計算
• クヌース・モーリス・プラットのアルゴリ
ズムの関数 kmp（教科書 p.85 図 5.4）の
実行
いずれも計算過程（i と j の変化）を記す．
練習しておいて下さい．講義ＨＰからプログ
ラムをダウンロードできます．
問２：幅優先探索
三つの容器 A,B,C があります．A,B,C それぞれの
容量は 3,5,8 リットルです．C には 8 リットルの水が
入っており AB は空です．あなたはこれから容器 B に
4 リットルの水を入れようとしています．
あなたができる操作は，一つの容器から他の容器に水
を移すことです．ただし，水を移す際は，注ぐ側の容
器が空になるか，注がれる側の容器が満杯になるまで
行い，途中で止めてはいけません．このとき以下の設
問に答えなさい．
（以下略）
問２：幅優先探索
• 容器 A と容器 B に何リットル入っている
かが分かれば容器 C の水の量が分かる．
• 可能な手順は A → B, A → C, B → A, B →
C, C → A, C → B の 6 通り．ただし，空
の容器から水を出せず，満杯の容器には水
を入れられない．
• 状態 (0,0) から幅優先探索し，B の水量
が 4 の頂点に達すれば良い．
問３：2 連結成分への分解
• 講義中に行った練習問題４とほぼ同じ．
問４：線形計画問題
• 講義中に行った練習問題 10 とほぼ同じ．
• Excel のソルバなどで答え合わせができ
ます（詳細は省略）．
問５：最大フロー問題
• 講義中に行った練習問題８とほぼ同じ．
問６：２部グラフのマッチング
（問題文省略）
• 問題文を読み右
図のようなグラ
フを描く．
• 最大マッチング
を求める．
• （証明は省略）
1n
2n
3n
4n
5n
6n
7n
8n
9n
n
10
n
11
n
12
n
13
n
14
n
15
n
16
問７
• 2011 年の問 2 と同じ問題なのでそちらを
ご覧下さい．
問８
• 2010 年の問 8 と同じ問題なのでそちらを
ご覧下さい．