問題 空欄を埋めよ。
n個のバケツにq個のボールをランダムに入れる。
2個以上のボールが少なくとも１つのバケツに入る
確率（Pcoll）は、1≦q≦(2n)1/2ならば、
Pcoll＞q(q-1)/n×0.316
であることを利用して以下の問題に答えよ。
１．メッセージを10ビットのハッシュ値に圧縮する。
二つのメッセージのハッシュ値を計算した結果、
これらが一致する確率Pcollを考える。以下を埋
めよ。
（１）q＝
（２）n＝
（３）Pcoll＞
/n×0.316=0.000617
２．メッセージを10ビットのハッシュ値に圧縮する。
ハッシュ値を計算するメッセージ数が41 の時、
少なくとも二つのメッセージが同じハッシュ値に
なる確率が0.5よりも大きくなる。
正しければY、誤りであればNを書け。
q個のボール
…
…
n個のバケツ

演習問題

Document

復習テスト12