アルゴリズム入門 試験問題
※解答用紙は3枚ある。各設問ごとに、1枚の解答用紙を使用せよ。スペースが足りない場合 は「裏へ続く」と明記して、裏面を用いて良い。
問1. 次の用語を簡潔に説明せよ。
(1) 多項式時間アルゴリズム。(2)分割統治法。(3)局所探索法。
(4) クラスNP。(5)近似アルゴリズム。
問2. 最小全域木問題について、以下の問に答えよ。
(1) 最小全域木問題とはどのような問題か、定義を答えよ。何が入力として与えられ、何を出力 することが求められる問題かを明確にせよ。
(2) 最小全域木問題に対するクラスカルのアルゴリズムの動作を説明せよ。
(3) 以下の記述は正しいか？ 正しければ理由を説明せよ。間違っていれば反例を挙げよ。
「枝の重みが全て異なる入力グラフに対しては、最適解は一通りしかない。」
問3. 京都の市バスは、1回の乗車運賃が230円である。ただし、500円の一日乗車券を購入すれ ば、その日はその券を使って乗り放題である。毎回の降車時に、これから先何回バスに乗るかが 不明の状況で、230円払うか一日乗車券を購入するかを決定するオンライン問題を考える。問題の 目的は、その日支払った料金の合計（これを「コスト」と呼ぶことにする）を最小化することで ある。以下の問に答えよ。
(1) この問題は、授業で取り扱ったスキーレンタル問題と本質的に同じである。どのように対応 するかを説明せよ。
(2) i= 1,2,3,4,5のそれぞれについて、その日の乗車回数が予めi回と分かっていた場合の最 適な行動とそのコストを答えよ。
(3) オンラインアルゴリズムの競合比とは何か説明せよ。
(4) この問題に対する最適な（つまり競合比が最小となる）オンラインアルゴリズムはどのよう なものか答えよ。また、そのアルゴリズムの競合比を答えよ（答のみでよい）。
