東京大学 工学系研究科 電気系工学専攻 2024年8月実施 問題4 情報工学II

标签：

• Tokyo-University
• Quick-Sort

Author

adj-matrix, 祭音Myyura

Description

I.

Problem summary

the official sample paper, Problem 4, pp. 21–23

Gates have two inputs unless shown otherwise.

1. For the supplied circuit, $o=(\overline x+\overline y)(y+z)$, give its truth table and a minimal sum-of-products expression.
2. A full adder takes $(x,y,i)$ and outputs sum bit $z$ and carry $c$. Find minimal sum-of-products expressions. Implement the sum block $A_1$ using XOR gates and the carry block $A_2$ using NAND gates.
3. Draw a circuit $S$ adding $X=x_1x_0$ and $Y=y_1y_0$. Only the two low result bits $(z_0,z_1)$ are output; use full adders and gates as needed.
4. Draw the corresponding subtractor $D$, using $X-Y=X+(\overline{y_1}\,\overline{y_0}+01)$ modulo $4$.
5. Draw a combined circuit $SD$: input $w=0$ selects addition and $w=1$ selects subtraction. Reduce both the number of full adders and the number of gates.

The top-left circuit in the following drawing gives the connections for Question (1); the other panels show implementations requested in (2).

II.

Consider the following algorithm $f(X)$, which overwrites an input array $X = (x_1, x_2, \cdots, x_n)$ of $n$ distinct non-negative integers to sort its components in ascending order:

1. for $n = 0$ or $n = 1$, do nothing.
2. for $n = 2$, do nothing if $x_1 < x_2$, and overwrite $X$ as $X = (x_2, x_1)$, otherwise.
3. for $n > 2$, select an element $p$ of $X$ by using a function $h(X)$ as $p = h(X)$. Let $X_1$ be an array consisting of all the elements in $X$ being smaller than $p$, and $X_2$ be an array consisting of all the elements in $X$ being greater than $p$. Overwrite $X$ as $X = (X_1, p, X_2)$. Then, recursively apply $f$ to the subarrays $X_1$ and $X_2$ in $X$ as $f(X_1)$ and $f(X_2)$, respectively.

Answer the following questions.

(1) Fig. 8 exemplifies the operation of $f$ for an array $X = (6,9,3,5,1,7)$ when $h(X) = x_1$ and the order of the elements in $X_1$ and $X_2$ inherits their order in $X$. Draw the operation of $f$ for $X = (6,8,4,5,2,3,1,9,7)$ by following the diagram in Fig. 8.

(2) Suppose that an array $X$ contains each integer from 1 to 9, once each. Also, assume that $h(X) = x_1$ and the order of the elements in $X_1$ and $X_2$ inherits their order in $X$. Obtain the array $X_{\max}$ that maximizes the number of recursive calls of $f(X)$ and has the largest value evaluated as a 9-digit integer. Also obtain the array $X_{\min}$ that minimizes the number of recursive calls of $f(X)$ and has the largest value evaluated as a 9-digit integer. Note that the value of $X = (1,2,3,4,5,6,7,8,9)$ evaluated as a 9-digit integer is 123456789.

(3) Assume that $h(X) = x_1$. For an array $X$ with length $n$, obtain the order of worst-case time complexity by supplementing the intermediate steps of its derivation. In the derivation, evaluate the order of the time complexity in terms of comparisons, while ignoring the complexity of the other operations.

(4) Program 1 is an implementation of the algorithm $f(X)$ in the C programming language. Describe the codes that should be in the blanks, [A], [B], and [C].

(5) Suppose that $h(X)$ is a function that returns an element $p$ selected from $X$ uniformly and randomly. Answer the order of the average time complexity of $f(X)$ as a function of $n$. In addition, describe its reason in detail.

Fig. 8

        (6,9,3,5,1,7)
              |
   (3,5,1) -- 6 - (9,7)
      |       |     |
(1) - 3 - (5) |   (7,9)
 |____|____|  |     |
      |       |     |
   (1,3,5) -- 6 - (7,9)
              |
        (1,3,5,6,7,9)

/* Program1 */
void swap(int X[], int i, int j){
    int tmp = X[i]; X[i] = X[j]; X[j] = tmp;
}
int partition (int X[], int left, int right) {
    int pivot = X[left];
    int i = right;
    for (int j = right; j >= left+1; j--) {
        if (X[j] >= pivot) {
            [A]
            i--;
        }
    }
    [B]
    return i;
}
void f(int X[], int left, int right) {
    if (left < right) {
        int pivotpos = partition(X, left, right);
        [C]
    }
}
int main (void) {
    int X[10] = {9, 6, 1, 7, 2, 3, 4, 5, 0, 8};
    f(X, 0, sizeof(X) / sizeof(X[0]) - 1);
    return 0;
}

题目描述

第二部分定义递归排序算法 $f(X)$。输入是由 $n$ 个互不相同的非负整数组成的数组 $X=(x_1,\ldots,x_n)$：$n\le1$ 时不操作；$n=2$ 时按升序交换；$n>2$ 时由 $p=h(X)$ 选枢轴，把小于 $p$ 的元素组成 $X_1$、大于 $p$ 的元素组成 $X_2$，将数组改写为 $(X_1,p,X_2)$，再分别递归排序 $X_1,X_2$。

1. 当 $h(X)=x_1$，且划分后各元素保持原相对次序时，仿照图 8，完整画出 $X=(6,8,4,5,2,3,1,9,7)$ 的递归划分与最终排序过程。
2. $X$ 恰含整数 $1$ 至 $9$ 各一次，仍取首元素为枢轴并保持相对次序。求使递归调用次数最多、且作为九位整数时数值最大的数组 $X_{\max}$；再求使递归调用次数最少且九位整数值最大的数组 $X_{\min}$。
3. 当 $h(X)=x_1$ 时，以元素比较次数为准，补出递推推导的中间步骤并求长度为 $n$ 的数组在最坏情况下的时间复杂度阶。
4. 补全给定 C 程序中 partition 的 [A]、[B] 和递归函数 f 的 [C]，使程序实现上述划分与排序。
5. 若 $h(X)$ 从 $X$ 中均匀随机选取枢轴，给出 $f(X)$ 的平均时间复杂度阶，并详细说明随机划分、递归树高度和每层工作量如何导出该结论。

Kai

I.

(1)

$x$	$y$	$z$	$o$
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Expanding and applying the consensus theorem gives

$$C=\overline xy+\overline xz+\overline yz =\boxed{\overline xy+\overline yz}.$$

Both two-literal implicants are essential: the input $010$ requires the first and $101$ requires the second.

(2)

$$z=\boxed{\overline x\,\overline y i+\overline x y\overline i+x\overline y\,\overline i+xyi}, \qquad c=\boxed{xy+xi+yi}.$$

The sum is odd parity: $z=(x\oplus y)\oplus i$, requiring two XOR gates. A NAND-only implementation of the carry is shown above. With $N(a,b)=\overline{ab}$, its intermediate nets are

$$n_1=N(x,y),\quad n_2=N(x,i),\quad n_3=N(y,i),\quad n_4=N(n_1,n_2),\quad n_5=N(n_4,n_4),\quad c=N(n_5,n_3).$$

This uses six two-input NAND gates. A three-input NAND, if permitted, could directly combine $n_1,n_2,n_3$ instead.

(3), (4), (5)

For $S$, the low full adder receives $(x_0,y_0,0)$; its carry feeds the high full adder $(x_1,y_1,c_0)$. For $D$, invert both $y$ bits and set the initial carry to $1$. In both circuits, discard the final carry and output only $(z_0,z_1)$.

For $SD$, form $y'_k=y_k\oplus w$ for $k=0,1$, and set the initial carry to $w$. The resulting two-full-adder circuit uses two XOR gates:

$$Z=\bigl[X+(Y\mathbin{\mathrm{xor}}(3w))+w\bigr]\bmod4.$$

There is a trade-off if full adders and individual gates are counted separately. Since the high carry is unused, another realization is

$$z_0=x_0\oplus y_0,\qquad b=y_0(x_0\oplus w),\qquad z_1=x_1\oplus y_1\oplus b.$$

Use two XOR gates and one AND gate to form $z_0,b$, then one full adder with inputs $(x_1,y_1,b)$, taking only its sum. This uses one full adder and three gates. Replacing that full adder by two XOR gates gives a realization with no full adders and five gates. These constructions give upper bounds on component counts. Comparing the two designs requires a cost convention for full adders versus gates.

II.

(1)

             (6,8,4,5,2,3,1,9,7)
                      |
       (4,5,2,3,1) -- 6 -- (8,9,7)
              |       |       |
  (2,3,1) --- 4 - (5) | (7) - 8 - (9)
      |       |    |  |  |____|____|
(1) - 2 - (3) |    |  |       |
 |____|____|  |    |  |    (7,8,9)
      |       |    |  |       |
   (1,2,3)    |    |  |       |
      |_______|____|  |       |
              |       |       |
         (1,2,3,4,5)  |       |
              |_______|_______|
                      |
             (1,2,3,4,5,6,7,8,9)

(2)

The worst case is when the partition is as unbalanced as possible. Since we want the digits at the start of the array to be as large as possible. In addition, each integer from 1 to 9 is one each. Therefore, the worst case is 987654321, i.e. $X_{\max}$.

The following diagram is one minimum-call case, although it is not the largest such array: (from bottom to top)

       (1,2,3,4,5,6,7,8,9)
         _______|_________
        |       |         |
    (1,2,3,4)   5     (6,7,8,9)
   _____|____   |    _____|____
  |     |    |  |   |     |    |
(1,2) - 3 - (4) | (6,7) - 8 - (9)
        |       |         |
    (3,4,2,1) - 5 --- (8,9,7,6)
                |
       (5,8,9,7,6,3,4,2,1)

Let $C(n)$ be the minimum number of invocations on an input of length $n$. Then

$$C(0)=C(1)=C(2)=1,\qquad C(n)=1+\min_{0\le k<n}\{C(k)+C(n-1-k)\}.$$

This gives $C(3)=C(4)=C(5)=3$, $C(6)=C(7)=C(8)=5$, and $C(9)=7$. Lexicographic maximization subject to these optimal splits chooses pivots $9$, then $6$, then $3$, and places the larger child elements first while preserving each child's order. Hence

$$X_{\min}=(9,6,8,7,3,5,4,2,1),$$

i.e. 968735421.

(Note to readers: The C code provided in the question is unstable; it will swap the Pivot to the middle and swap the elements that were originally at the end to the beginning)

(3)

In the worst case, the time complexity $T(n) = T(n-1) + T(0) + O(n)$

Since $T(0)$ is constant, therefore $T(n) = T(n-1) + cn = cn + c(n-1) + c(n-2) + \dots + c(1) \approx c \frac{n(n+1)}{2}$

i.e. $T(n) = \Theta(n^2)$.

(4)

• A: swap(X, i, j);
• B: swap(X, left, i);
• C: f(X, left, pivotpos-1); f(X, pivotpos+1, right);

(5)

The average comparison count is $\Theta(n\log n)$.

Order the keys by rank. A pair with ranks $i<j$ is compared exactly when the first pivot chosen from the interval $\{i,\ldots,j\}$ is one of its two endpoints, which has probability $2/(j-i+1)$. The special case of two keys also makes exactly one comparison. Therefore

$$\mathbb E[C_n]=\sum_{1\le i<j\le n}\frac{2}{j-i+1} =2\sum_{d=1}^{n-1}\frac{n-d}{d+1} =2(n+1)H_n-4n=\Theta(n\log n),$$

where $H_n=\sum_{k=1}^n1/k$. Equivalently, the expectation satisfies the recurrence with partition cost $n-1$ and uniformly distributed pivot rank.