アルゴリズムと計算量の問題

バケット数 $4$ のチェイン法ハッシュ表に、互いに異なる $5$ 個のキーを挿入する。各キーのハッシュ値は $4$ 個のバケットのどれかに等確率 $\frac{1}{4}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$5$ 個すべてを挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

バケット数 $3$ のチェイン法ハッシュ表が最初は空である。この表に、互いに異なる $4$ 個のキーを挿入する。各キーのハッシュ値は $3$ 個のバケットのどれかに等確率 $\frac{1}{3}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーをすべて挿入し終えたとき、キーを $2$ 個以上含むバケットの個数の期待値を求めよ。

番号 $0,1,2,3,4$ の $5$ 個のスロットからなるハッシュ表が最初は空である。この表に、互いに異なる $3$ 個のキーを $1$ 個ずつ順に、次の線形探査法（オープンアドレス法）で挿入する。

• キーのハッシュ値を $h$ とし、スロット $h,h+1,h+2,\dots$ の順に（番号は $5$ を法として考え、スロット $4$ の次はスロット $0$ とする）調べ、最初に見つかった空のスロットにそのキーを入れる。
• $1$ 個のスロットを調べることを探査 $1$ 回と数える。キーを入れた空のスロットを調べることも $1$ 回に数える（たとえば、スロット $h$ が空ならば探査は $1$ 回）。

各キーのハッシュ値は $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$3$ 個のキーを挿入し終えるまでの探査回数の合計の期待値を求めよ。

番号 $0,1,2,3,4$ の $5$ 個のビットからなるブルームフィルタを考える。最初はすべてのビットが $0$ である。このフィルタは $2$ 個のハッシュ関数 $h_1,h_2$ を使い、次のように動作する。

• 要素 $x$ を挿入するときは、ビット $h_1(x)$ とビット $h_2(x)$ を $1$ にする（$h_1(x)=h_2(x)$ のときは、そのビット $1$ 個だけが $1$ になる）。
• 要素 $y$ を問い合わせるときは、ビット $h_1(y)$ とビット $h_2(y)$ がともに $1$ であれば「含まれる」と答え、そうでなければ「含まれない」と答える。

互いに異なる $2$ 個の要素 $a,b$ をこの順に挿入したあと、$a,b$ のどちらとも異なる要素 $c$ を問い合わせる。ここで、$6$ 個の値 $h_1(a),h_2(a),h_1(b),h_2(b),h_1(c),h_2(c)$ は互いに独立で、それぞれ $0,1,2,3,4$ のどれかに等確率 $\frac{1}{5}$ で定まるとする。

$c$ について誤って「含まれる」と答える確率（偽陽性の確率）を求めよ。

番号 $0,1,2,3,4,5$ の $6$ 個のセルからなる、線形探査法（オープンアドレス法）のハッシュ表がある。最初はすべてのセルが空である。この表に、互いに異なる $4$ 個のキーを $1$ 個ずつ順に挿入する（削除は行わない）。

キー $x$ を挿入するときは、ハッシュ値 $h(x)\in \{0,1,\dots ,5\}$ から始めて、セル $h(x),h(x)+1,h(x)+2,\dots$（番号は $6$ を法として考え、セル $5$ の次はセル $0$ とする）の順に調べ、最初に見つかった空のセルにキーを格納する。調べたセルの個数（キーを格納した空のセルも $1$ 個と数える）を、その挿入の探査回数とよぶ。

各キーのハッシュ値は $0,1,\dots ,5$ のどれかに等確率 $\frac{1}{6}$ で定まり、キーどうしのハッシュ値は互いに独立であるとする。$4$ 個のキーの挿入における探査回数の合計の期待値を求めよ。