情報システム評価学’00レポート問題解説


総評:
ほとんどの人が問題1、4を選択していました。 もう少しチャレンジ精神とか、「目立ちたがる」意思が 見えるとより嬉しかったのですが..
「自分で考える」事と オリジナリティーを高く評価しました。
100点 2名。 中村さん(自分でアイデアを考えて、 出題者を「負かし」た。 問題6参照) 堀田さん(非常にソツないレポートです)
その他、20名、最低点60点 平均は80点くらい (ちょっと採点が甘すぎたかもしれません。)

なお、同じ内容ならば、簡潔なレポートに高得点がつきます。 ただし、説明不足、特に設問8に関して私が理解できない (あるいは余りに漠然としている)ものは減点です。

問題1
平面上に線分の集合が有ります.これらはM箇所で交差しています。 線分を赤と緑に塗り、同色の線分間の交差をM/2以下にすることが 必ず出来ることを示しなさい。ただし、各交差点ではちょうど2本 の線分が交差していると仮定します。

解答
 解答1: 線分を頂点とし、交わっている線分に対応する 辺を考えてグラフを作る.このグラフの最大カット問題 を考えると、カットできられる片側を赤、もう一方を緑に塗れば 問題がとける。 最大カットについては授業でやりました。
 解答2: ランダムに色を塗れば 条件を満たすことを示せばいいです。 詳細は略。
注意として,線分は何本あるかはわかりません。 交差数よりもっと多いかもしれないです。 線分数Nに対してM=N(N+1)/2 としていた人が居ましたが, これは仮定できません。
 解答3: ランダムに色を塗る方法をDerandomizeすると、 貪欲アルゴリズムでいいことになります。 すなわち、 一本ずつ、過去に色を塗った線分のうちでどちらの色の線分 と多く交わっているか考えながら色塗りをします。 この解答が一番多かったです。
問題2 
アリスとボブがコイン投げゲームをするとします。 表が出ればアリスが勝ち,裏が出るとボブが勝ちで、 負けた方が勝ったほうに1円払うとしましょう。 最初にアリスもボブも N円持っており、どちらかが破産するまでゲームを続けるとすると、 (N / log N)^2 回まではゲームが続く確率が高いことを チェルノフの定理を用いて示しなさい。

解答
問題2は出来て欲しかったのだけど.…  Y回目のゲームまでで表が出る回数の期待値はY/2です。 一方、Y回目でゲームが破産する場合は, 表がY/2+N/2回以上出ているか,Y/2-N/2 回以下しか出なかった場合です。 つまり,期待値の(1+N/Y)倍以上か(1-N/Y)倍以下しか 表が出なかった場合です。 これはチェルノフの定理で 計算できますね。 この確率をF(Y)として、F(Y)をY=Nから(N/log N)^2 まで足してみてください。 これが小さいことを示せばいいです。
問題3
上の問題で, 100N^2回でどちらかが破産している確率は1/2以上です。 これを次のようにして示しなさい。
注意: 他の方法(問題4の結果を証明なしに使ってはいけません) で示した場合は、いい点をあげます。

(1) Stirlingの公式(数学辞典、数学公式集、 解析概論(高木貞治)などに有ります)を使って,
100N^2 から50N^2 を取り出す組み合わせ数 がほぼ(π/2)^{-1/2} 2^{100N^2+1} (10N)^{-1}  であることを示しなさい。
(2) アリスもボブも破産していない確率に 2^{100N^2} を掛けたものは、上記の組み合わせ数の2N倍よりも 小さいことを示しなさい。
(3)(1)と(2)から命題が証明できます。

解答
  上で私が示した方法は非常に拙いものなのです。 ただ、Stirlingの公式 $n! = \sqrt{2n \pi} e^{-n} n^n $ で、ゴミのように見える$\sqrt{2n \pi}$ の項が 本質的に効いてくるのが実感できるので、一度上のような 計算をやってみると面白いです。 自分で考えた別解の方が望ましく、いい点がついています。 二項分布の性質を使う方法(福岡さん)や 差分方程式を使う方法(西村さんら)が有ります。 例えば差分方程式を使うのは、 D(N)をアリスがN円持っていて、どちらかが破産するまでの 回数の期待値とすると、期待値の和法則を用いて、 D(N)= 1/2(D(N-1)+D(N+1)) +1 という方程式が でます。これを差分方程式として、条件 D(0)=D(2N)=0の元でとけばいいです。 これは、「マルコフ過程」の特別な場合で, これを解くと、問題4にあるように$N^2$という答えが出てきます。
問題4
問題2,3で、 実は破産までの回数の期待値はN^2です。 (だから、100N^2は過大な評価です)。 Motowani-Raghavanの本の第6章に、 エレガントな解法がありますが、 授業ではやっていません。 シミュレーションプログラムを作って,これを確かめなさい (もしくは、徳山が間違っていることを示しなさい?!)。
これの解説は略。実験と理論がほとんど一致する例です。
問題5
魔法使いの部屋の扉には20個のレバーが有ります。 各々のレバーをONかOFFにして、全部が[正しい」位置に 来た時に扉が開きます。 扉にはこんな文章が書いてあります。 「扉が開かない間は、2つのレバーの対が示されます。 どちらか一方は正しい位置にありません。」  何回くらいのレバー操作で扉は開くと思いますか?

ヒント:正しいレバー位置にしたら1円もらい、レバー位置を 誤った方向に動かした時1円払うと考えてください。 問題4の結果(破産までの回数の期待値がN^2であること) を用いてよろしい。

解答
これは2充足問題(2SAT)というアルゴリズム理論の基本問題を 解くアルゴリズムの問題(の変形)です。

「どちらか一方は正しい位置にありません」というのは、 私は「両方間違った位置にある可能性も有ります」という つもりでした. これは設問の説明が悪かったようで,「一方だけ間違っている」 という意味に採った人が多かったです(それでも減点はしません)。  正確な評価をしたほうがいいのですが,易しい評価を しましょう。

まずランダムにレバーを引きます。 間違っているレバーの数をXとします。Xの期待値は10で、 Xまたは20−Xは10以下です。 その後、提示された対のどちらかを変更すると、 間違っているレバーの数が1増える確率が1/2以下で、 1減る確率は1/2以上です(もし、「一方だけ間違っている」 だと、確率はちょうど1/2になります)。
これはコイン投げゲームと同じです。 だから、200回やると、 全部正解になる確率が(1/2)(1-X^2/200)以上 (マルコフの定理から 間違っているレバーが0になるか、2Xになるかどちらかになる 確率が1-X^2/200以上、0になっている確率がその半分) になります。 マルコフの定理の変わりにチェビシェフの定理を使うと もっと正確に議論できますが、ちょっと難しい。
200回操作して、空かなかったら初めの配置を逆転して やり直して見ましょう (こうするとXを20−Xに置き換えたことになります)。 これで空かない確率は上の議論からだけだと1/2以下です。 きちんとやるともっと小さいです。 駄目だったら,これを何回もやり直します。 期待値評価は、この議論だけだと800以下である ことになります。

「どちらか一方だけ間違っている」モデルで、 魔法使いが対を提示しないまでレバー操作を行って, 駄目だったら全部逆にすればよくて、期待値は110、 というような答案が多かったです. 概略はOKです。

充足問題(SAT)は授業で聞いたことがあると思いますが, 2充足問題(2SAT)とは、ブール変数x_1, x_2,...x_n と、ブール変数もしくはその否定の対の集合 C_1, C_2,....,C_m が与えられます。  対C_i=(x,y)において、xまたはyが1になれば、この対は 充足されるといいます。 全ての対が充足されるようにブール変数に0,1を割り当てる解 (充足解)を求める(あるいは、存在しないことを示す)のが 2SAT問題です。

  今,2SAT問題が与えられた時,一つの充足解の 変数割り当てAを考えましょう。これが魔法使いの部屋 をあけるレバーの配置です。 最初にある割り当てを行った時, 充足されていない対を一つとります。 この対に入っている変数2つのうち,どちらかはAと異なる 割り当てになります(Aではこの対は充足されていますから)。 つまり、この対は「魔法使いが示す対」になります。 ですから、もし充足解が存在すれば、 O(n^2)回の操作で、「扉が開く」、すなわち 2SAT解が求まりますし、もしも扉が開かなければ,高い確率で, もともと充足解が存在しないということが言えます。

問題6 (これは難しいResearch Problemなので、 無理にレポート期間中に解こうとしないように)。
文章が 「扉が開かない間は、3つのレバーの組が示されます。 そのどれかは正しい位置にありません。」  だったらどうでしょうか?

解答
これは3SAT(3充足問題)という問題に対応します (下に書くように、問題文に不備がありましたが)。 3充足問題はNP完全なので,多項式時間でこの扉が開いたら、 P=NPという大問題が解け、Clay Researchから Millennium Prize で百万ドルもらえます。 多項式時間ではないのだけど、ある程度高速にという 研究があって、
U. Shoning, A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problem, Proc. 40th IEEE Foundation of Computer Science, (1999) 410-415
(興味ある人は私の部屋にどうぞ)。

さて、中村真輔氏のレポートでは、次のような考えが示されています。
全部でレバーの組み合わせの数は2の20乗です。 1つの対が示されたとき、その対の8通りの可能性のうち、現在の 可能性が否定されます。ですから、残りの3通りの 一つになります。 よって、残る可能性は7/8倍になります。 従って,k個の対が示されたとき、組み合わせ数は (7/8)^k 2^{20}になります。k=103だと、これは1以下になるので, 103回魔法使いの出す対を見ると、 高い確率で組み合わせは1通りに決まります。 従って、後20回で、計123回 レバー操作をすると扉が開きます。

これは実は正解(厳密には、魔法使いが可能な対からランダムに 選んで示すという条件が要り、また、それでも正確では ないのですが)です。  意表をつかれましたが、出題者(私)の「負け」です。 問題を「レバー操作の数」と書いたのが、かなり迂闊でした. 問題の本質(NPとは何か、情報の公開とは何か、複雑度とは何か) をついているので、私はこういう意見が好きです。 これが「私の意図した正解」、すなわち、「高速に扉をあける方法」 だと1億円もらえます。私が意図した解と どこが違っているのでしょうか。
問題は,最後の20回でどちらにレバーを引いたらいいかを 「考えないと」いけない事です。今まで見た103回の 魔法使いの「提示」から、最後の20回のレバー操作を するための情報は開示されているのですが,どうやって 具体的な操作をその情報から「発見する」事ができるのでしょうか。
世の中である「公開鍵暗号」などは、上のような 「公開されている情報」から「具体的な操作」をするのが 難しい場合があることを用いて設計されています。
実際,上の例では、103個の提示対 は、3充足問題の「問題」を与えたことになります。 そこから具体的なレバー操作を計算するのはNP完全なので、 レバー操作の数は確かに123回ですが、最後の20回を どう操作をするかを3充足問題を解いて計算しないといけません。 理論的には太陽が燃え尽きるくらい計算しても答えが出ません。
でも、3充足問題はこれくらいのサイズだと、ヒュ-リスティクス と呼ばれる手法で割と早く解ける場合もあるので, 魔法使いの部屋の前で,超高速コンピュータを持っていれば、 中村さんの解が賢い場合が多いということになりますね.
この中村さんの議論を精密化すると、 「3充足問題の問題例生成」という、最近はやりの研究テーマに 行き当たりますし、 SATを用いた公開鍵暗号ができるかもしれません。

問題7
  n対の平面上の線分があります(全部で2n本)。 各々の対から1本づつの線分を選択して, 選んだn本の線分が交わらないように 出来るかどうか(高い確率で) 判定するアルゴリズムを考えてください。
ヒント:問題5を使います。すこし考える必要のある問題です。

解答
これは2充足問題ですが、扉の問題にすると, 一つの線分対がレバーに対応し, 対のどちらの線分を選ぶかでレバーをON OFFに対応させます。 もしも交わらない選択法があったとします。
そのような選択を一つ固定して, 「魔法使いの扉の開けるレバー配置」にします。 まずランダムに対から1本ずつ選びます。 もし、2本の線分の交差があったら,これが、「魔法使いが示す レバーの対」ですから、どちらかの線分を(もう一つの候補と) 取り替えます。 O(N^2)で高い確率で,「扉が開く」、 すなわち、交わらない配置が出来ます。 
この場合,交わらない選択法は一つとは限らないのですが, これは、「扉が開く」コンビネーションが他にもあるということ なので、アルゴリズムには有利に働いても不利にはなりません。

一方、O(N^2)で「扉が開かない」場合は, 高い確率で「もともと交差しない配置は不可能」ということが 判定できます。

問題8
自分が興味を持っているコンピュータ科学の問題に付いて 徳山にわかるように説明してください。
全般に、もう少し情熱的に書いて欲しかったような気がします。