アルゴリズム入門 試験問題
※解答用紙は4枚ある。各設問ごとに、1枚の解答用紙を使用せよ。スペースが足りない場合 は「裏へ続く」と明記して、裏面を用いて良い。
問1. 次の用語を簡潔に説明せよ。
(1) 分割統治法。(2) 局所探索法。(3)乱択アルゴリズム。
問2. 充足可能性問題(SAT)について、以下の問に答えよ。
(1) SAT（Yes/Noで答える判定問題）とはどういう問題かを説明せよ。
(2) SATの最適化版であるMAX SATとはどういう問題かを説明せよ。
(3) MAX SATにおける局所探索アルゴリズムの動作を説明せよ。
問3. オンラインアルゴリズムについて、以下の問に答えよ。
(1) オンライン問題、オンラインアルゴリズムとは何か、簡潔に説明せよ。
(2) スキーレンタル問題とはどういう問題かを説明せよ。
(3) スキーを買う金額が7万円、レンタルする金額が1万円としたときの最適なアルゴリズムの 動作を説明せよ。アルゴリズムを解答するだけで十分であり、提示したアルゴリズムの最適 性を証明することまでは必要ない。
問4. 独立頂点集合問題について、以下の問に答えよ。
(1) グラフの頂点の部分集合Sが「独立頂点集合」であるとは、Sに含まれるどの2頂点間にも 枝が存在しないことである。裏面のグラフGの独立頂点集合を1つ答えよ。
(2) 「独立頂点集合問題」とは、入力としてグラフGと正整数kが与えられる。グラフGがk 頂点からなる独立頂点集合を持てば「Yes」、持たなければ「No」と答える判定問題である。
裏面のグラフGとk= 6が入力として与えられたとき、答えはYesかNoか？ また、その 理由を答えよ。
(3) グラフの頂点の部分集合Sが「クリーク」であるとは、Sに含まれるどの2頂点間にも枝が 存在することである。「クリーク問題」とは、入力としてグラフGと正整数kが与えられる。
グラフGがk頂点からなるクリークを持てば「Yes」、持たなければ「No」と答える判定問 題である。独立頂点集合問題が難しいことは既に分かっているとして、クリーク問題が難し いことを示せ。
1 3
2 4
5 6
8 7
9
G 10
