試験について • 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 と同じ問題なのでそちらをご覧下さい．