京都大学 情報学研究科 知能情報学専攻 2021年7月実施 情報学基礎 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),(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)

题目描述

问题 1 考虑函数 $\operatorname{SelectKth}(A,k)$，它返回整数集合 $A$ 中第 $k$ 小元素的值（$k\ge1$）。例如，$A=\{5,1,7\}$、$k=2$ 时，函数输出 5。设 $p:=\operatorname{PivotSelect}(A)$ 为从 $A$ 的元素中随机返回一个元素的函数；$(L,R):=\operatorname{Partition}(A,p)$ 将 $A$ 分成由不大于 $p$ 的值构成的集合 $L$ 和由大于 $p$ 的值构成的集合 $R$。例如，$A=\{5,1,7\}$、$p=5$ 时，得到 $L=\{5,1\}$、$R=\{7\}$。

$\operatorname{Remove}(A,p)$ 为从 $A$ 中删除元素 $p$ 的函数。例如，$A=\{5,1,7\}$、$p=7$ 时，它把 $A$ 变为 $\{5,1\}$。$|X|$ 表示集合 $X$ 的元素数，且 $A$ 的全部元素互不相同。

上方 Algorithm 1 为寻找 $A$ 中第 $k$ 小元素的伪代码。

（1）填写 Algorithm 1 中的空栏（a）～（e）。

（2）当 $|A|=n$ 时，设 $\operatorname{Partition}(A,p)$、$\operatorname{Remove}(L,p)$、$\operatorname{PivotSelect}(A)$ 的元素比较次数分别为 $O(n)$、$O(n)$、$O(1)$。用阶数记号表示 Algorithm 1 的平均比较次数。

问题 2 回答关于使用 4 个链表的外部哈希法的问题。键是 4 个取值于 $\{0,1,2\}$ 的整数排成的模式 $s_4s_3s_2s_1$，其中 $s_i\in\{0,1,2\}$。以下 $\bmod$ 表示输出除法余数的运算。

（1）表 1 示意使用哈希函数

$$\left(\sum_{i=1}^4 3^{i-1}s_i\right)\bmod4$$

依次插入键 0100,1211 后的数据结构。在此状态下继续依次插入 0010,2101,1222,1111，仿照表 1 画出最终的数据结构。

表 1：

索引	链表
0
1	0100 → 1211
2
3

（2）向含 $k$ 个元素的链表追加一个元素的代价为 $ck$，其中 $c$ 为正实常数。若多个键按照表 2 的概率分布独立产生，并用哈希法依次插入，给出使期望插入代价最小的键与哈希值的对应，并说明理由。以填写表 2 中（a）～（d）的方式回答。

表 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）

（3）用哈希函数

$$\left(\sum_{i=1}^4a_is_i+a_5s_1s_2+a_6s_3s_4\right)\bmod4$$

实现（2）所得对应，推导 $a_1,a_2,a_3,a_4,a_5,a_6$。

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$ be the maximum expected number of comparisons over all target ranks for an input of size $n$, and let $cn$ bound the comparisons outside the recursive call. If the uniformly random pivot has rank $j$, the recursive subproblem has size

$$s(j)= \begin{cases} n-j,&jk. \end{cases}$$

For every $k$,

$$\frac1n\sum_{j=1}^n s(j)\leq\frac{3n}{4}.$$

Thus, by induction with $C\geq4c$,

$$T_n\leq cn+\frac1n\sum_{j=1}^n T_{s(j)} \leq cn+C\frac{3n}{4}\leq Cn.$$

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

Let $q_h$ be the probability that a generated key is assigned to list $h$. After $t$ insertions, the expected cost of the next insertion is $ct\sum_{h=0}^3q_h^2$. The above assignment gives

$$\begin{gathered} (q_0,q_1,q_2,q_3)=(0.25,0.30,0.20,0.25),\\ \sum_{h=0}^3q_h^2=0.255, \end{gathered}$$

which is the minimum over the possible assignments of (a)--(d).

(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}$$

Reference

• 大学公表の原題