京都大学 情報学研究科 知能情報学専攻 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) で求めた対応付けを なるハッシュ関数で実現するときの を導出せよ。
| キー | 生起確率 | ハッシュ値 |
|---|
| 0100 | 0.10 | (a) |
| 0210 | 0.20 | (b) |
| 1010 | 0.15 | 0 |
| 1101 | 0.15 | 1 |
| 1111 | 0.25 | (c) |
| 2101 | 0.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)
| index | list |
|---|
| 0 | 2101 -> 1111 |
| 1 | 0100 -> 1211 -> 1222 |
| 2 | |
| 3 | 0010 |
(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