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

标签：

• 东京大学
• 堆排序

Author

donguri0912, 祭音Myyura

Description

I.

Answer the following questions on sequential circuits. We consider a circuit that has four states $S=\{s0, s1, s2, s3\}$. The circuit changes its state and output $Y$ according to the value of input $X$. Table $1$ shows the state transition table of the circuit.

(1) Draw the state transition diagram that is equivalent to the state transition table in Table $1$.

(2) Show the shortest input sequence that outputs $Y=1$ when the initial state is $s2$.

Next, assume that we represent the state S with two bits as $s0=00$, $s1=01$, $s2=10$, $s3=11$. We consider designing the circuit with two JK-Flip Flop (JK-FF) $F_A$ and $F_B$. We represent the higher bit of the states with $Q_A$, and the lower bit with $Q_B$ such as $s=Q_AQ_B$. $F_A$ and $F_B$ hold the states $Q_A$ and $Q_B$ in the circuits, respectively. A JK-FF has one bit state Q, and the state transits as shown in Fig. $1$ according to inputs J and K.

(3) Copy Table $1$ to your answer sheet and complete the table by filling the blanks. Here, ($J_A, K_A$) and ($J_B, K_B$) are the inputs to $F_A$ and $F_B$, respectively. Use $d$ for "don't care" conditions.

(4) Simplify the input functions of $J_A, K_A, J_B, K_B$ and output function of $Y$ by using Karnaugh maps.

(5) Draw the circuit using the symbols shown in Fig. $2$.

Table 1

Current state $S(t)$	Input $X$	Next state $S(t+1)$	Output $Y$	$Q_A(t)$	$Q_B(t)$	$Q_A(t + 1)$	$Q_B(t + 1)$	$J_A$	$K_A$	$J_B$	$K_B$
$s_0$	0	$s_1$	0
$s_0$	1	$s_2$	0
$s_1$	0	$s_3$	0
$s_1$	1	$s_2$	0
$s_2$	0	$s_0$	0
$s_2$	1	$s_2$	0
$s_3$	0	$s_0$	0
$s_3$	1	$s_2$	1

II.

Answer the following questions on heapsort. Assume that max heap is an array representation of a binary tree where the value in a parent node is greater than the values in its two children nodes. The structure of the array is as follows: assuming that the index $i$ is an integer greater than or equal to $1$, the value in the left child node of node $i$ is stored in the $(i \times 2)$-th element of the array, and the value in the right child node of node $i$ is stored in the $(i \times 2 + 1)$-th element of the array.

The function make_heap in Program $1$ is a function that generates the max heap from an array with n items. The first element of the array is stored in array[1]. The function swap(array,i,j) in Program $1$ is a function that switches the values of array[i] and array[j].Here, the values in the array are integers, and there is no duplication among them.

(1) Assume that the number of items is $7 (n=7)$, and the input array stores the values $\{1, 7, 8, 9, 6, 4, 5\}$ in this order. Find the max heap that is generated by make_heap in Program $1$.

(2) Draw the process of generating the max heap in Question (1) with binary trees. The arrays follow the same structure as the max heap even during the process of making max heap. You do not need to draw the trees that remain unmodified in the process.

(3) Give the order of the time complexity of make_heap according to the number of comparisons of the values.

Assume that we sort a max heap by iteratively taking the maximum value and rebuilding a max heap with the remaining items.

(4) Describe a function by using the $C$ programming language in as few lines as possible to sort a max heap array with n items in descending order. Use the function make_heap in Program $1$ for rebuilding the max heap in your function.

(5) Describe an overview of an algorithm to sort an array using max heap, which is more computationally efficient than that obtained in Question (4). The sort order can be either ascending order or descending order.

/* Program 1 */
void push_down(int array[], int n, int node) {
    if(node * 2 > n)    return;
    int     parent = node, child;
    do {
        child = parent * 2;
        if ((child < n) && (array[child] < array[child + 1]))
            child = child + 1;
        if (array[child] < array[parent])
            break;
        swap(array, child, parent);
        parent = child;
    }while (parent * 2 <= n);
}

void make_heap(int array[], int n){
    int    node;
    for (node = n / 2; node >= 1; --node)
        push_down(array, n, node);
}

题目描述

I. 时序逻辑电路

回答以下时序电路问题。考虑具有四个状态 $S=\{s_0,s_1,s_2,s_3\}$ 的电路。电路根据输入 $X$ 的值改变状态和输出 $Y$，状态转移表如表 1 所示。

(1) 画出与表 1 的状态转移表等价的状态转移图。

(2) 当初始状态为 $s_2$ 时，给出使输出为 $Y=1$ 的最短输入序列。

接下来，设用两位表示状态 $S$，即 $s_0=00$、$s_1=01$、$s_2=10$、$s_3=11$。考虑使用两个 JK 触发器（JK-FF）$F_A,F_B$ 设计该电路。状态的高位记为 $Q_A$，低位记为 $Q_B$，即 $s=Q_AQ_B$。$F_A,F_B$ 分别保存电路中的状态 $Q_A,Q_B$。一个 JK 触发器具有一位状态 $Q$，根据输入 $J,K$ 按图 1 所示进行状态转移。

(3) 将表 1 抄到答题纸上并填满空白。这里 $(J_A,K_A)$ 和 $(J_B,K_B)$ 分别为 $F_A,F_B$ 的输入。不关心条件用 $d$ 表示。

(4) 使用卡诺图化简 $J_A,K_A,J_B,K_B$ 的输入函数和 $Y$ 的输出函数。

(5) 使用图 2 中的符号画出电路。

表 1

当前状态 $S(t)$	输入 $X$	下一状态 $S(t+1)$	输出 $Y$	$Q_A(t)$	$Q_B(t)$	$Q_A(t+1)$	$Q_B(t+1)$	$J_A$	$K_A$	$J_B$	$K_B$
$s_0$	0	$s_1$	0
$s_0$	1	$s_2$	0
$s_1$	0	$s_3$	0
$s_1$	1	$s_2$	0
$s_2$	0	$s_0$	0
$s_2$	1	$s_2$	0
$s_3$	0	$s_0$	0
$s_3$	1	$s_2$	1

II. 堆排序

回答以下堆排序问题。假设最大堆是二叉树的数组表示，其中父结点的值大于两个子结点的值。数组结构如下：下标 $i$ 为不小于 $1$ 的整数，结点 $i$ 的左子结点的值存于数组第 $2i$ 个元素，右子结点的值存于第 $2i+1$ 个元素。

程序 1 中的函数 make_heap 将含有 $n$ 个元素的 array 转换为最大堆。数组首元素存储在 array[1]。程序 1 中的函数 swap(array,i,j) 交换 array[i] 与 array[j] 的值。这里，数组中的值均为整数且互不重复。

(1) 假设元素个数为 $7$（$n=7$），输入数组按顺序存放 $\{1,7,8,9,6,4,5\}$。求程序 1 中 make_heap 生成的最大堆。

(2) 用二叉树画出问 (1) 中生成最大堆的过程。即使在建堆过程中，数组仍采用与最大堆相同的结构。不必画出过程中没有发生变化的树。

(3) 根据元素值的比较次数，给出 make_heap 的时间复杂度阶。

假设通过反复取出最大值，再用剩余元素重新建立最大堆来排序。

(4) 用尽量少的 C 语言代码写一个函数，将具有 $n$ 个元素的最大堆 array 按降序排列。在你的函数中，使用程序 1 中的 make_heap 重建最大堆。

(5) 概述一种使用最大堆对数组排序的算法，其计算效率要高于问 (4) 的方法。排序可为升序或降序。

/* 程序 1 */
void push_down(int array[], int n, int node) {
    if(node * 2 > n)    return;
    int     parent = node, child;
    do {
        child = parent * 2;
        if ((child < n) && (array[child] < array[child + 1]))
            child = child + 1;
        if (array[child] < array[parent])
            break;
        swap(array, child, parent);
        parent = child;
    }while (parent * 2 <= n);
}

void make_heap(int array[], int n){
    int    node;
    for (node = n / 2; node >= 1; --node)
        push_down(array, n, node);
}

Kai

I.

(1)

(2)

$x = 0,0,0,1$ の順

(3)

Current state $S(t)$	Input $X$	Next state $S(t+1)$	Output $Y$	$Q_A(t)$	$Q_B(t)$	$Q_A(t + 1)$	$Q_B(t + 1)$	$J_A$	$K_A$	$J_B$	$K_B$
$s_0$	0	$s_1$	0	0	0	0	1	0	$d$	1	$d$
$s_0$	1	$s_2$	0	0	0	1	0	1	$d$	0	$d$
$s_1$	0	$s_3$	0	0	1	1	1	1	$d$	$d$	0
$s_1$	1	$s_2$	0	0	1	1	0	1	$d$	$d$	1
$s_2$	0	$s_0$	0	1	0	0	0	$d$	1	0	$d$
$s_2$	1	$s_2$	0	1	0	1	0	$d$	0	0	$d$
$s_3$	0	$s_0$	0	1	1	0	0	$d$	1	$d$	1
$s_3$	1	$s_2$	1	1	1	1	0	$d$	0	$d$	1

(4)

$J_A=X+Q_B$、$K_A=\overline X$、$J_B=\overline X\,\overline{Q_A}$、$K_B=X+Q_A$、$Y=XQ_AQ_B$。

JK-FF の励起表の $d$ を利用すると、$J_A$ の $Q_A$、$J_B$ の $\overline{Q_B}$、$K_B$ の $\overline{Q_B}$ は不要となる。

(5)

同じ名前の端子は接続されている。二つの JK-FF は同じクロックで更新する。

II.

(1)

$\{9,7,8,1,6,4,5\}$

問題のコードはC言語と違って配列のインデックスが1スタートなので注意。

(2)

(3)

要素の数を $n$ として、$\Theta(n)$

(4)

本解:

void sort_by_heap(int array[], int n) { for(int i = 0; i < n - 1; i++) make_heap(array + i, n - i); }

本解を改行したもの:

void sort_by_heap(int array[], int n) {
  for(int i = 0; i < n - 1; i++) make_heap(array + i, n - i);
}

参考解:

void sort_by_heap(int array[], int n) {
  for(int i = n; i > 1; i--) {
    make_heap(array, i);
    swap(array, 1, i);
  }
  for (int i =1; i <= n / 2; i++) swap(array, i, n - i + 1);
}

ヒープソートの話かなと思ったので最初参考解を思いついたが、as few lines as possibleという問題文の指示が気になったので本解の方を思いついた。もっとも、どんなプログラムであれ改行無しで書けば $1$ 行になるのだが。 どちらもmake_heapを実行するとarrayの先頭が最大値になることを利用している。以下は本解の解説。

make_heap(array + i, n - i) では、関数内の添字 $j$ が元の array[i + j] に対応する。C の配列自体は常に添字 $0$ から始まり、array は &array[0]、array + 1 は &array[1] である。このプログラムは array[0] を使わず、データを array[1] から array[n] に格納する規約なので、少なくとも $n+1$ 要素分の領域が必要となる。

for文の()の中の書き方のコツはイテレータ変数(解答でいうとi)の初期値と最終値だけ見ることである。今回は初期値がi = 0で、条件式i < n - 1がi = n - 2の時まではtrueになることから最終値がi = n - 2になることがわかる。make_heapに渡した引数の方も初期値と最終値だけ考えればよく、初期値が(array, n)、最終値が(array + n - 2, 2)であることがわかる。別にi = n - 1まで回してもいいのだが、その時はサイズ $1$ の配列をmake_heapすることになり何も起こらないので条件式をi < n - 1に設定している。ちなみにi <= n - 2としてもよい。こちらの方が直感的かもしれない.

(5)

array[0] は未使用とし、データは array[1] から array[n] とする。n < 2 なら終了する。
1. まず、make_heap を用いて array に max heap を作る。
次に、array の先頭 array[1] は max heap 中の最大値となっているので、
それを array の最後の要素 array[n] と swap する。

2. n2 = n-1, n-2, ..., 2 に対して下記を実行する。
先頭ポインタ array、データ数 n2 の array の部分配列を array2 と定義する。
array2 は array2[1] の要素以外は max heap の条件を満たしている。
array2[1] も max heap の条件を満たすため、
push_down(array2, n2, 1) (つまり push_down(array, n2, 1))を実行し、
木の下方に向かって並べ替える。
その後、array2[1] はまた max heap 中の最大値となっているのでarray2[n2] と swap する。

以上の手順により並べ替えられた array は先頭から昇順に並んでいる。

仰々しく書いてしまったが要はヒープソートをやっている。コードで書くと次のよう。

void heap_sort(int array[], int n) {
  if (n < 2) return;
  make_heap(array, n);
  swap(array, 1, n);
  for(int n2 = n - 1; n2 >= 2; n2--) {
    push_down(array, n2, 1);
    swap(array, 1, n2);
  }
}

最悪時の比較回数のオーダーは、make_heap が線形時間なので (4) が $\Theta(n^2)$、(5) が $\Theta(n \log n)$ である。したがって (5) の方が効率的になっている。

Reference

• 原問題の公開保存版：JK-FF・ヒープソート（PDF 1–2ページ）
• donguri0912：東大院電気系の過去問解説・2020年問題4