京都大学 情報学研究科 知能情報学専攻 2021年8月実施 情報学基礎 F2-1
Author
Isidore, 祭音Myyura
Description
設問1
整数の集合 \(A\) の要素の小さい方から \(k\) 番目 \((k \ge 1)\) の要素の値を返す関数 \(\text{SelectKth}(A,k)\) を考える。例えば、\(A = \{5,1,7\}\) および \(k = 2\) の場合、\(\text{SelectKth}(A,k)\) は \(5\) 出力する。 今、\(p:= \text{PivotSelect}(A)\) は \(A\) に含まれる要素のうち一つをランダムに返す関数とし、\((L,R):= \text{Partition}(A,p)\) は集合 \(A\) を \(p\) 以下の値で構成される集合 \(L\) と \(p\) より大きい値で構成される集合 \(R\) に分割する関数とする。 例えば、\(A = \{5,1,7\}\) および \(p = 5\) の場合、\((L,R):= \text{Partition}(A,p)\) の \(L\) および \(R\) はそれぞれ、\(L = \{5,1\}\)、\(R = \{7\}\) となる。また、\(\text{Remove}(A,p)\) は集合 \(A\) から要素 \(p\) を削除する関数とする。 例えば、\(A = \{5,1,7\}\) および \(p = 7\) 場合、\(\text{Remove}(A,p)\) は \(A\) を \(\{5,1\}\) にする。 \(|X|\) は集合 \(X\) の要素数とし、\(A\) のすべての要素は異なるとする。
(1) Algorithm. \(1\) は SelectKth 関数の疑似コードである。Algorithm .\(1\) の (a)-(e) を埋めよ。
(2) \(|A| = n\) の場合の \(\text{Partition}(A,p)\)、\(\text{Remove}(L,p)\)、\(\text{PivotSelect}(A)\) の要素の比較回数をそれぞれ \(O(n)\)、\(O(n)\)、および \(O(1)\) とする。Algorithm. \(1\) の平均比較回数をオーダー表記で答えよ。
設問2
\(4\) つのリストを用いた外部ハッシュ法について以下の問いに答えよ。キーは \(0,1,2\) のいずれかの整数が \(4\) つ並んだパターン \(s_4s_3s_2s_1,s_i \in \{0,1,2\}\) で与えられる。また以下において、\(\text{ mod }\) は割り算の余りを出力する演算子を示す。
(1) 表 \(1\) は、ハッシュ関数 \(\big(\sum_{i = 1}^4 3^{i - 1}s_i\big) \text{ mod } 4\) を用して、キー \(0100,1211\) を順に挿入した後のデータ構造を模式的に表している。この状態に追加で \(0010,2101,1222,1111\) を順に挿入した後のデータ構造を表 \(1\) に倣って図示せよ。
(2) \(k\) 個の要素で構成されるリストに、新たに要素を \(1\) つ追加するのに要するコストを \(ck(c\text{は正の実定数})\) とする。表 \(2\) に示す確率分布に従って独立に生起する複数個のキーをハッシュ法を用して順に挿入していくとき、挿入コストの期待値が最小となるキーとハッシュ値の対応付けをその理由とともに示せ。対応付けは表 \(2\) における (a),(b),©,(d) を埋める形で解答せよ。
(3) (2) で求めた対応付けを \(\big(\sum{i = 1}^4 a_is_i + a_5s_1s_2 + a_6s_3s_4\big)\text{ mod } 4\) なるハッシュ関数で実現するときの \(a_1,a_2,a_3,a_4,a_5,a_6\) を導出せよ。
表1
| インデックス | リスト |
|---|---|
| 0 | |
| 1 | 0100 \(\rightarrow\) 1211 |
| 2 | |
| 3 |
表2
| キー | 生起確率 | ハッシュ値 |
|---|---|---|
| 0100 | 0.10 | (a) |
| 0210 | 0.20 | (b) |
| 1010 | 0.15 | 0 |
| 1101 | 0.15 | 1 |
| 1111 | 0.25 | © |
| 2101 | 0.15 | (d) |
Kai
設問1
(1)
a. \(|L| = k\)
b. \(|L| > k\)
c. \(k\)
d. \(|L| < k\)
e. \(k - |L|\)
(2)
Note that Algorithm 1 is so called "Quick Select" algorithm. Let \(T(n)\) denote the expected time complexity of Quick-Select, we have
Therefore, \(T(n) = O(n)\)
設問2
(1)
| index | list |
|---|---|
| 0 | 2101 -> 1111 |
| 1 | 0100 -> 1211 -> 1222 |
| 2 | |
| 3 | 0010 |
(2)
- (a): 0
- (b): 2
- (\(c\)): 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