京都大学 情報学研究科 知能情報学専攻 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)

题目描述

1. SelectKth(A,k) 返回元素互异的整数集合 $A$ 中第 $k$ 小值。PivotSelect(A) 从 $A$ 随机选一个枢轴 $p$；Partition(A,p) 把 $A$ 分成由不大于 $p$ 的元素组成的 $L$ 与大于 $p$ 的元素组成的 $R$；Remove(A,p) 删除 $p$，$|X|$ 表示集合大小。

   

   1. 填写图中 Algorithm 1 的空栏 (a)–(e)。
   2. 当 $|A|=n$，假设 Partition、Remove、PivotSelect 的比较次数分别为 $O(n),O(n),O(1)$，用大 $O$ 给出 Algorithm 1 的平均比较次数。

2. 采用 4 条链的分离链接哈希，键为 $s_4s_3s_2s_1$，其中每个 $s_i\in\{0,1,2\}$。

   1. 哈希函数为 $\left(\sum_{i=1}^4 3^{i-1}s_i\right)\bmod4$。初态如下，继续依次插入 0010,2101,1222,1111，画出最终结构。

      索引	链表
      0
      1	0100 → 1211
      2
      3

   2. 向已有 $k$ 个元素的链表追加一个元素代价为 $ck$（$c>0$）。按下表概率独立产生并持续插入键，填写 (a)–(d) 的哈希值，使期望插入代价最小，并说明理由。

      键	概率	哈希值
      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,\ldots,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

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

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