東京大学 工学系研究科 電気系工学専攻 2019年8月実施 問題4 情報工学II
Author
Description
I.
Answer the following questions on sequential circuits. We consider a circuit that has four states
(1) Draw the state transition diagram that is equivalent to the state transition table in Table
(2) Show the shortest input sequence that outputs
Next, assume that we represent the state S with two bits as
(3) Copy Table
(4) Simplify the input functions of
(5) Draw the circuit using the symbols shown in Fig.
Table 1
Current state | Input | Next state | Output | J_A | K_A | J_B | K_B | ||||
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | ||||||||||
1 | 0 | ||||||||||
0 | 0 | ||||||||||
1 | 0 | ||||||||||
0 | 0 | ||||||||||
1 | 0 | ||||||||||
0 | 0 | ||||||||||
1 | 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
The function make_heap
in Program array
with n
items.The first element of the array is stored in array[1]
.The function swap(array,i,j)
in Program 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 array
stores the values make_heap
in Program
(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 array
with n
items in descending order. Use the function make_heap
in Program
(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);
}
Kai
I.
(1)

(2)
(3)
Current state | Input | Next state | Output | J_A | K_A | J_B | K_B | ||||
---|---|---|---|---|---|---|---|---|---|---|---|
0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | ||||
1 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | ||||
0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | ||||
1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | ||||
0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | ||||
1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | ||||
0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | ||||
1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 |
(4)

(5)

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

(3)
要素の数を
(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
という問題文の指示が気になったので本解の方を思いついた。もっとも、どんなプログラムであれ改行無しで書けば make_heap
を実行するとarray
の先頭が最大値になることを利用している。以下は本解の解説。
make_heap
の引数は先頭アドレスarray + i
、サイズn - i
の配列を渡すという意味である。本来先頭アドレスarray
、サイズn
の配列から部分配列を切り出してmake_heap
に渡す操作を行っている。ちなみに配列はメモリ上で、(インデックスが array
にarray[1]
、array + 1
にarray[2]
、...、array + n - 1
にarray[n]
という風に配置されている。
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
まで回してもいいのだが、その時はサイズ make_heap
することになり何も起こらないので条件式をi < n - 1
に設定している。ちなみにi <= n - 2
としてもよい。こちらの方が直感的かもしれない.
(5)
array をサイズ n の int 型配列とする。
1. まず、make_heap を用いて array に max heap を作る。
次に、array の先頭 array[1] は max heap 中の最大値となっているので、
それを array の最後の要素 array[n] と swap する。
2. n2 = n-1, n-2, ..., 2 に対して下記を実行する。
先頭アドレス array[1]、サイズ 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) {
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);
}
}
計算量オーダーは (4) が