跳到主要内容

京都大学 情報学研究科 知能情報学専攻 2021年8月実施 情報学基礎 F2-1

Author

Isidore, 祭音Myyura

Description

設問1

整数の集合 の要素の小さい方から 番目 の要素の値を返す関数 を考える。例えば、 および の場合、 出力する。 今、 に含まれる要素のうち一つをランダムに返す関数とし、 は集合 以下の値で構成される集合 より大きい値で構成される集合 に分割する関数とする。 例えば、 および の場合、 および はそれぞれ、 となる。また、 は集合 から要素 を削除する関数とする。 例えば、 および 場合、 にする。 は集合 の要素数とし、 のすべての要素は異なるとする。

(1) Algorithm. は SelectKth 関数の疑似コードである。Algorithm . の (a)-(e) を埋めよ。

(2) の場合の の要素の比較回数をそれぞれ 、および とする。Algorithm. の平均比較回数をオーダー表記で答えよ。

設問2

つのリストを用いた外部ハッシュ法について以下の問いに答えよ。キーは のいずれかの整数が つ並んだパターン で与えられる。また以下において、 は割り算の余りを出力する演算子を示す。

(1) 表 は、ハッシュ関数 を用して、キー を順に挿入した後のデータ構造を模式的に表している。この状態に追加で を順に挿入した後のデータ構造を表 に倣って図示せよ。

(2) 個の要素で構成されるリストに、新たに要素を つ追加するのに要するコストを とする。表 に示す確率分布に従って独立に生起する複数個のキーをハッシュ法を用して順に挿入していくとき、挿入コストの期待値が最小となるキーとハッシュ値の対応付けをその理由とともに示せ。対応付けは表 における (a),(b),(c),(d) を埋める形で解答せよ。

(3) (2) で求めた対応付けを なるハッシュ関数で実現するときの を導出せよ。

表1
インデックスリスト
0
10100 1211
2
3
表2
キー生起確率ハッシュ値
01000.10(a)
02100.20(b)
10100.150
11010.151
11110.25(c)
21010.15(d)

Kai

設問1

(1)

a.

b.

c.

d.

e.

(2)

Note that Algorithm 1 is so called "Quick Select" algorithm. Let denote the expected time complexity of Quick-Select, we have

Therefore,

設問2

(1)

indexlist
02101 -> 1111
10100 -> 1211 -> 1222
2
30010

(2)

  • (a): 0
  • (b): 2
  • (): 3
  • (d): 1

Reason: to minimize the cost is to equalize the probability to insert each list

(3)

Construct a system of six linear equations in six variables from the table given in (2), and we have