アルゴリズム入門 試験問題
※解答用紙は3枚ある。各設問ごとに、1枚の解答用紙を使用せよ。スペースが足りない場合 は「裏へ続く」と明記して、裏面を用いて良い。
問1. 次の用語を簡潔に説明せよ。
(1) ソーティング。(2)分割統治法。(3) 局所探索法。
(4) オンラインアルゴリズム。(5)指数時間アルゴリズム。
問2. 最小頂点被覆問題について、次の問に答えよ。
(1) 最小頂点被覆問題とはどういう問題かを、例を用いながら説明せよ。
(2) 最小頂点被覆問題に対する貪欲アルゴリズムの動作を説明せよ。
(3) (2)のアルゴリズムで最適解が求まらない入力の例を示せ。（理由も簡潔に述べよ。）
(4) 最小頂点被覆問題に対する2-近似アルゴリズムの動作を説明せよ。
(5) (4)で答えたアルゴリズムが2-近似アルゴリズムになっている理由を説明せよ。
問3. 判定問題Aが難しい（Aを解く高速なアルゴリズムが存在しない）ことが既に分かってい る状況で、判定問題Bが難しいことを示したいとする。以下の(1)および(2)に答えよ。なお、必 要に応じて図を用いるなど工夫して、分かりやすく説明すること。
(1) この目的のためには、問題Aから問題Bへのリダクション（還元）が作れると良い。リダ クションとはどういうものかを説明せよ。
(2) (1)のリダクションが作れたら、なぜ問題Bの難しさを示したことになるのか説明せよ。
