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

标签：

• Kyoto-University
• Randomized-Quickselect
• Algorithm-Complexity
• Separate-Chaining-Hashing
• Expected-Insertion-Cost-in-Hashing

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),(c),(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	(c)
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

$$\begin{aligned} T(n) &= O(n) + T(\frac{n}{2}) \\ &= O(n) + O(\frac{n}{2}) + T(\frac{n}{4}) \\ &= O(n) + O(\frac{n}{2}) + O(\frac{n}{4}) + \cdots + O(1) \\ &\sim n (1 + \frac{1}{2} + \frac{1}{4} + \cdots + \left(\frac{1}{2} \right)^{\log n}) \\ &= n \cdot \frac{1}{1-\frac{1}{2}} = 2n \end{aligned}$$

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

$$\begin{aligned} a_1 &= 1 \\ a_2 &= 2 \\ a_3 &= 0 \\ a_4 &= -2 \\ a_5 &= 0 \\ a_6 &= 2 \\ \end{aligned}$$