アルゴリズム入門 試験問題
※解答用紙は3枚ある。各設問ごとに、1枚の解答用紙を使用せよ。スペースが足りない場合 は「裏へ続く」と明記して、裏面を用いて良い。
問1. 次の用語を簡潔に説明せよ。
(1) ソーティング。(2)分割統治法。(3) 局所探索法。
(4) オンラインアルゴリズム。(5)近似アルゴリズム。
問2. MAX CUTについて、次の問に答えよ。
(1) MAX CUTとはどういう問題かを説明せよ。
(2) MAX CUTに対する貪欲アルゴリズムの動作を説明せよ。
(3) (2)で答えたアルゴリズムが2-近似アルゴリズムになっている理由を説明せよ。
(4) (2)のアルゴリズムの解が最適解の2倍悪くなってしまう入力例と、それに対するアルゴリ
ズムの実行例を示せ。
問3. グラフの3-彩色問題とは、グラフの各頂点を3色で塗る際、どの枝もそれに接続する2頂点 が異なる色になるような塗り方が存在するか否かを問う判定問題(YES/NO問題)である。
(1) 裏面のグラフG1およびG2がそれぞれ3-彩色問題の入力として与えられた場合の答えを示 せ。理由も答えよ。
(2) グラフの4-彩色問題とは、3-彩色問題と同様の判定問題で、ただし使える色数が4色となっ たものである。3-彩色問題が難しいことは既に分かっているとして、4-彩色問題が難しいこ とを示せ。
