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

标签：

• 东京大学
• 快速排序

Author

adj-matrix, 祭音Myyura

Description

I.

Answer the following questions on logic circuits. Lower italic letters such as $x$ and $y$ represent logical variables. Also, $x\cdot y$, $x+y$, $x\oplus y$, and $\overline{x}$ represent logical conjunction (AND), logical disjunction (OR), exclusive disjunction (XOR), and negation (NOT), respectively. Fig. 1 shows the symbols for logic gates used in circuit diagrams. Use these symbols in your answers.

(1) Complete the truth table for the logical function $o=C(x,y,z)$ implemented by the circuit in Fig. 2. Also, obtain the logical formula of $C(x,y,z)$ in the most simplified sum-of-products form.

(2) Suppose that we design a full adder circuit FA, which receives 1-digit binary numbers $x$, $y$, and a carry $i$ as the input and compute their sum $z$ and the carry $c$ as shown in Fig. 3. Obtain the representations of $z$ and $c$ as logical functions of $(x,y,i)$ in the most simplified sum-of-products form. Suppose that Fig. 4 is an implementation of FA. Draw the circuit for $A_1$ in Fig. 4 using only XOR gates, and draw the circuit for $A_2$ in Fig. 4 using only NAND gates.

In the following, we design circuits S, D, and SD using the full adder circuit FA in Fig. 3.

(3) Suppose that a circuit S computes the sum of 2-digit binary numbers $X=x_1x_0$ and $Y=y_1y_0$. As in Fig. 5, $(x_0,y_0,x_1,y_1)$ is the input to S. For the sum $Z=X+Y$ and its binary representation $Z=z_2z_1z_0$, the output of S is $(z_0,z_1)$. Draw the circuit S using the full adder circuits FA and the gates in Fig. 1 if necessary.

(4) Suppose that a circuit D shown in Fig. 6 computes the difference $Z=X-Y$ of 2-digit binary numbers $X=x_1x_0$ and $Y=y_1y_0$. Here, the negative number $-Y$ is defined by the two’s complement as $-Y=\overline{y_1}\,\overline{y_0}+01$. Also the difference is defined as $Z=X+(-Y)$ by using the negative number $-Y$. Draw the circuit D using the full adder circuits FA and the gates in Fig. 1 if necessary.

(5) Suppose that, for input $(x_0,y_0,x_1,y_1,w)$, a circuit SD shown in Fig. 7 outputs the sum obtained in Question (3) when $w=0$ and the difference obtained in Question (4) when $w=1$. Draw the circuit SD with the smallest numbers of both the full adder circuits FA and the gates in Fig. 1.

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.

/*  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;
}

题目描述

I. 回答下列关于逻辑电路的问题。用 $x$、$y$ 等小写斜体字母表示逻辑变量。$x\cdot y$、$x+y$、$x\oplus y$、$\overline{x}$ 分别表示逻辑与（AND）、逻辑或（OR）、异或（XOR）和逻辑非（NOT）。图 1 给出了电路图中使用的逻辑门符号，解答中也应使用这些符号。

I.(1) 求图 2 所示电路实现的逻辑函数 $o=C(x,y,z)$ 的真值表，并将 $C(x,y,z)$ 的逻辑表达式写成尽可能简化的与或式。

I.(2) 要设计图 3 所示的全加器 FA，其输入为一位二进制数 $x$、$y$ 和进位 $i$，输出为它们的和位 $z$ 及进位 $c$。将 $z$、$c$ 分别表示为 $(x,y,i)$ 的逻辑函数，并写成尽可能简化的与或式。设图 4 是 FA 的一种实现，画出仅使用 XOR 门构成的 $A_1$ 电路，以及仅使用 NAND 门构成的 $A_2$ 电路。

以下使用图 3 所示的全加器 FA 设计电路 S、D 和 SD。

I.(3) 设电路 S 计算两位二进制数 $X=x_1x_0$ 和 $Y=y_1y_0$ 的和。如图 5 所示，S 的输入为 $(x_0,y_0,x_1,y_1)$。若和为 $Z=X+Y$，其二进制表示为 $Z=z_2z_1z_0$，则 S 的输出为 $(z_0,z_1)$。使用全加器 FA，并在必要时使用图 1 中的逻辑门，设计电路 S 并画出电路图。

I.(4) 设图 6 所示电路 D 计算两位二进制数 $X=x_1x_0$ 和 $Y=y_1y_0$ 的差 $Z=X-Y$。这里用二进制补码将负数 $-Y$ 定义为 $-Y=\overline{y_1}\,\overline{y_0}+01$，并用负数 $-Y$ 将差定义为 $Z=X+(-Y)$。使用全加器 FA，并在必要时使用图 1 中的逻辑门，设计电路 D 并画出电路图。

I.(5) 对输入 $(x_0,y_0,x_1,y_1,w)$，设图 7 所示电路 SD 在 $w=0$ 时输出第 (3) 问求得的和，在 $w=1$ 时输出第 (4) 问求得的差。使用全加器 FA 和图 1 中的逻辑门，使这两类器件各自的数量尽可能少，设计电路 SD 并画出电路图。

II. 考虑下列算法 $f(X)$，它直接改写由 $n$ 个互不相同的非负整数组成的输入数组 $X=(x_1,x_2,\cdots,x_n)$，使各元素按升序排列：

1. 当 $n=0$ 或 $n=1$ 时，不进行任何操作。
2. 当 $n=2$ 时，若 $x_1<x_2$，则不进行任何操作；否则将 $X$ 改写为 $X=(x_2,x_1)$。
3. 当 $n>2$ 时，利用函数 $h(X)$ 从 $X$ 中选择一个元素 $p=h(X)$。令 $X_1$ 为由 $X$ 中所有小于 $p$ 的元素组成的数组，$X_2$ 为由 $X$ 中所有大于 $p$ 的元素组成的数组。将 $X$ 改写为 $X=(X_1,p,X_2)$，然后对 $X$ 中的子数组 $X_1$、$X_2$ 分别递归地应用 $f$，即执行 $f(X_1)$、$f(X_2)$。

回答下列问题。

II.(1) 图 8 以数组 $X=(6,9,3,5,1,7)$ 为例，展示了当 $h(X)=x_1$ 且 $X_1$、$X_2$ 中元素的排列顺序沿用其在 $X$ 中的顺序时，算法 $f$ 的运行过程。仿照图 8，画出 $X=(6,8,4,5,2,3,1,9,7)$ 时算法 $f$ 的运行过程。

II.(2) 设数组 $X$ 恰好包含整数 1 至 9 各一次，且 $h(X)=x_1$，$X_1$、$X_2$ 中元素的排列顺序沿用其在 $X$ 中的顺序。求使 $f(X)$ 的递归调用次数最多、并且作为九位整数时数值最大的数组 $X_{\max}$。同时，求使递归调用次数最少、并且作为九位整数时数值最大的数组 $X_{\min}$。这里，将 $X=(1,2,3,4,5,6,7,8,9)$ 作为九位整数时，其值为 123456789。

II.(3) 设 $h(X)=x_1$。对长度为 $n$ 的数组 $X$，推导 $f(X)$ 最坏情况下的时间复杂度阶，并写出推导的中间过程。推导中仅按比较操作评价复杂度，忽略其他操作的复杂度。

II.(4) 程序 1 是算法 $f(X)$ 的一种 C 语言实现。写出应填入上方程序 [A]、[B]、[C] 三个空栏的代码。

II.(5) 设函数 $h(X)$ 从 $X$ 中均匀随机地选择一个元素 $p$ 并返回。给出 $f(X)$ 平均时间复杂度阶关于 $n$ 的表达式，并详细说明理由。

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

$$\begin{aligned} C&=\overline xy+\overline xz+\overline yz\\ &=\boxed{\overline xy+\overline yz}. \end{aligned}$$

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

(2)

$$\begin{aligned} z&=\boxed{\overline x\,\overline y i+\overline x y\overline i+x\overline y\,\overline i+xyi},\\ c&=\boxed{xy+xi+yi}. \end{aligned}$$

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

$$\begin{aligned} n_1&=N(x,y),\\ n_2&=N(x,i),\\ n_3&=N(y,i),\\ n_4&=N(n_1,n_2),\\ n_5&=N(n_4,n_4),\\ c&=N(n_5,n_3). \end{aligned}$$

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

(3)

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)$.

(4)

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)$.

(5)

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

$$\begin{aligned} z_0&=x_0\oplus y_0,\\ b&=y_0(x_0\oplus w),\\ z_1&=x_1\oplus y_1\oplus b. \end{aligned}$$

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

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

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

$$\begin{aligned} T(n)&=T(n-1)+cn\\ &=cn+c(n-1)+c(n-2)+\dots+c(1)\\ &\approx c\frac{n(n+1)}{2}. \end{aligned}$$

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

$$\begin{aligned} \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), \end{aligned}$$

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

Reference

• 東京大学 電気系工学専攻：公式サンプル問題、Problem 4、PDF pp. 21–23