アルゴリズム入門 試験問題
※解答用紙は3枚ある。各設問ごとに、1枚の解答用紙を使用せよ。スペースが足りない場合 は「裏へ続く」と明記して、裏面を用いて良い。
問1. 次の用語を簡潔に説明せよ。
(1) ソーティング。
(2) 多項式時間アルゴリズム。
(3) 貪欲アルゴリズム。
(4) 近似アルゴリズム。
(5) オンラインアルゴリズム。
問2. MAX CUT問題について、以下の問に答えよ。
(1) MAX CUT問題とはどういう問題かを説明せよ。
(2) MAX CUT問題に対する以下のアルゴリズムについて、それぞれ動作を簡単に説明せよ。
(i) 局所探索アルゴリズム、(ii)貪欲アルゴリズム、(iii) 乱択アルゴリズム
(3) (2)の(i)〜(iii)のうちいずれか1つを選び、その近似度が2になることを説明せよ。
問3. ハミルトン閉路について、以下の問に答えよ。
(1) グラフのハミルトン閉路とは何かを説明せよ。
(2) 裏面に記載のグラフは、ハミルトン閉路を持つか？ 持つならば閉路を図示せよ。持たない ならば、その理由を出来るだけ簡潔に示せ。
(3) オイラー閉路を持つがハミルトン閉路を持たないグラフを１つ示せ。答は図示せよ。答が正 しい理由も述べよ。
(4) グラフの「ハミルトンパス」とは、グラフの全ての頂点をちょうど1 度ずつ通るパスのこ とである。与えられたグラフがハミルトンパスを持つかどうかを問うyes/no問題を「ハミ ルトンパス問題」と言う。また、与えられたグラフがハミルトン閉路を持つかどうかを問う
yes/no問題を「ハミルトン閉路問題」と言う。ハミルトンパス問題が難しいことは既に分
かっているとして、ハミルトン閉路問題が難しいことを示せ。
