6/12 計算とプログラム, 問題の解決


質問と回答

Q.
2007年度の問題の問い1で「平均情報量」という言葉を使えとかいてありま すが、最低回数を調べる上で平均情報量から判断するのはおかしくないですか?

「一番運が悪かった場合」、つまり、「毎回得られる情報量が一番少なかった 場合」を考えなければならないと僕は思います。

7個のうち2個が偽物な ので、必要な情報量はlog2(21)両方の皿に違う個数ずつのせる試行は無意味な ので考えない。1個ずつのせるとき、片方の皿が下がる確率はそれぞれ5/21で、 釣り合う確率は11/21。故に、1回の試行で得られる情報量の最小値は log2(21/11)。同様に考えると、2個ずつ、3個ずつをのせる時に得られる情報 の最小値はそれぞれlog2(3),log2(28/13)。これらはいずれも2倍しても log2(7/2)に届かないので、2回の試行では必ずしも十分な情報量が得られると は限らない。故に、2回で必ず偽物を見つけ出すことは不可能である。

これが僕の答えです。このとき、確かに皿に2個ずついれたときの平均情報量 と、最低の情報量は等しくなりますが、意味があるのは平均情報量ではなく最 低の情報量だと僕は思います。

A.
この問題は「平均情報量」という言葉を使わなくても,細かく場合分けをすれ ば解くことは可能です.ただ,この問題の意図は,「平均情報量」という概念 を使って,よりシンプルに解くことにあります.

「平均情報量」そのものは生起確率が確定しないと求めることはできないわけ ですが,「n通りのメッセージの平均情報量の最大値」は求まります(教科書 P.43-44のあたり).それを使えば,具体的な場合わけを考えなくても証明でき るというわけです.


5/29の課題について


今日の講義

講義は1時間で30分は自習とする.講義の時間中は,端末は使わないように(電源をつける,ログインしておくのは可). 第5章の「計算の方法」, 第6章の「問題の解き方」の部分を説明する.

今回の演習