第3回　予想問題（FA年・プロセッサ年の再来）

想定シナリオ：FA年・プロセッサ年の再来。問題4がFA中心（最小化・閉包性）、問題2はパイプライン再出（2025型）、問題6は2019型のCMOS＋加算器＋カウンタ、問題7はDTFT系、問題1は頻出リスト内の木構造。

本番形式：問題1・2は必須、問題4・6・7から2問選択（計4問・3時間・500点満点）。

問題1【必須】アルゴリズムとプログラミング ― 二分探索木

配点：(1) 20, (2) 25, (3) 15, (4) 35, (5) 30

傾向準拠：木構造は大問1の頻出リスト記載テーマ。構造体＋ポインタのコード読解は2025年度大問1（二分ヒープ）、トレース＋出力記述の形式は2026年度大問1に準拠。

図1はANSI Cで記述されたプログラムである。大域変数 count は22行目が実行された回数を数えるカウンタである。図1のプログラムに関する以下の各問に答えよ。

 1: #include <stdio.h>
 2: #include <stdlib.h>
 3: int count = 0;
 4: typedef struct node {
 5:     int key;
 6:     struct node *left, *right;
 7: } node_t;
 8:
 9: node_t *insert(node_t *p, int key) {
10:     if (p == NULL) {
11:         p = (node_t *)malloc(sizeof(node_t));
12:         p->key = key; p->left = p->right = NULL;
13:     } else if (key < p->key) {
14:         p->left  = insert(p->left,  key);
15:     } else {
16:         p->right = insert(p->right, key);
17:     }
18:     return p;
19: }
20: node_t *search(node_t *p, int key) {
21:     while (p != NULL) {
22:         count++;
23:         if (key == p->key) return p;
24:         else if (key < p->key) p = p->left;
25:         else                   p = p->right;
26:     }
27:     return NULL;
28: }
29: void inorder(node_t *p) {
30:     if (p != NULL) {
31:         inorder(p->left);
32:         printf("%d ", p->key);
33:         inorder(p->right);
34:     }
35: }
36:
37: int main(void) {
38:     int keys[7] = {50, 30, 70, 20, 40, 60, 10};
39:     node_t *root = NULL;
40:     for (int i = 0; i < 7; i++) root = insert(root, keys[i]);
41:     inorder(root);
42:     printf("\n");
43:     node_t *p = search(root, 40);
44:     printf("%d %d\n", (p != NULL), count);
45:     return 0;
46: }

図1　プログラム

(1) 40行目のループがすべて完了した時点の木を図2に示す。空欄①〜③に入るキーを答えよ。

(2) 図1のプログラムが開始してから終了するまでに出力される内容をすべて記述せよ。また、二分探索木で中間順巡回（inorder traversal）を行うと必ずキーが昇順に出力される理由を1〜2行で述べよ。

(3) 43行目の search(root, 40) の実行中に23行目で p->key と比較されるキーを、訪問順にすべて列挙せよ。

(4) 空の木にサイズ $n$ のキー列を昇順で挿入する場合を考える。$k$ 番目のキーの挿入で13行目の条件式が評価される回数を $k$ で表し、挿入全体での評価回数の総和を $n$ を用いて示せ（総和計算の過程も示すこと）。また、このとき完成する木において、根から最も深い節点までの経路上の節点数を答えよ。

(5) 挿入されるキー列の順序によらず search の比較回数を $O(\log n)$ に保つには、木にどのような性質が必要か。その性質を述べ、その性質の下で比較回数が $O(\log n)$ で抑えられる理由を2〜3行で説明せよ。

問題2【必須】計算機システム ― パイプライン処理

配点：(1) 20, (2-1) 25, (2-2) 25, (3) 30, (4) 25

傾向準拠：2025年度大問2（5ステージパイプライン）の型に準拠。ハザード・ストール数・速度向上率の計算構成。

IF（命令フェッチ）、ID（デコード・レジスタ読み出し）、EX（演算）、MEM（メモリアクセス）、WB（レジスタ書き込み）の5ステージからなる同期型パイプラインプロセッサを考える。1クロックサイクルで1ステージを実行する。

(1) 単一サイクルプロセッサ（全命令を1サイクルで実行、サイクル時間 $T$）を5ステージに均等分割してパイプライン化した。ステージ間レジスタの遅延は無視できるとする。パイプライン化後のクロックサイクル時間と、十分多数の命令を実行したときのスループット（単位時間あたりの命令数）の向上率を答えよ。

(2) 以下の命令列を考える。lw はメモリからのロード命令である。

I1: lw  r1, 0(r2)      # r1 ← Mem[r2+0]
I2: add r3, r1, r4     # r3 ← r1 + r4
I3: sub r5, r3, r6     # r5 ← r3 - r6

(2-1) フォワーディング機構がなく、レジスタへの書き込みはWBステージ、読み出しはIDステージで行われるとする（同一サイクルのWBでの書き込みとIDでの読み出しは、書き込みが先に行われるものとする）。I1のIFを第1サイクルとして、各命令の各ステージが実行されるサイクルを表で示し、I1〜I3の完了までに必要な総サイクル数を答えよ。

(2-2) EX/MEMおよびMEM/WBステージ間レジスタからEXステージ入力へのフォワーディング機構を追加した場合について、(2-1)と同様に表で示し総サイクル数を答えよ。また、フォワーディングを追加してもストールが完全にはなくならない理由を、I1とI2の関係に着目して2〜3行で説明せよ。

(3) ハザードが発生しないと仮定する。$k$ ステージのパイプラインで $N$ 命令を実行するのに必要なサイクル数を $k, N$ で表せ。また、非パイプライン実行（1命令 $k$ サイクル）に対する速度向上率を求め、$N \to \infty$ の極限を示せ。

(4) 分岐命令によって生じるハザードの名称を答えよ。また、その影響を軽減する代表的な手法を1つ挙げ、仕組みを2〜3行で説明せよ。

問題4【選択】計算理論 ― DFA最小化・閉包性（FA年型）

配点：(1-1) 30, (1-2) 15, (2) 40, (3) 40

傾向準拠：FA中心年（2018・2026年度大問4）が続くシナリオ。直積構成の定義記述は2026年度大問4(2)（和集合版）の変形（共通部分版）。閉包性を使った間接証明は発展。

(1) アルファベット $\Sigma = \{a, b\}$ 上のDFA $M$ を次の遷移表で定める。開始状態は $q_0$、受理状態は $\{q_5\}$ である。

状態	a	b
$q_0$	$q_1$	$q_2$
$q_1$	$q_3$	$q_4$
$q_2$	$q_4$	$q_3$
$q_3$	$q_5$	$q_5$
$q_4$	$q_5$	$q_5$
$q_5$	$q_5$	$q_5$

(1-1) 状態の等価類分割（受理・非受理の2分割から始めて細分化を繰り返す方法）により、$M$ と等価な最小DFAを構成せよ。各段階の分割と、最小DFAの状態遷移図を示すこと。

(1-2) $L(M)$ を日本語で簡潔に述べよ。

(2) DFA $M_1 = (Q_1, \Sigma, \delta_1, q_1, F_1)$ と $M_2 = (Q_2, \Sigma, \delta_2, q_2, F_2)$ に対し、$L(M_1) \cap L(M_2)$ を認識するDFA $M = (Q, \Sigma, \delta, q, F)$ を直積構成により定義したい。$Q$、$\delta([r_1, r_2], a)$、$q$、$F$ をそれぞれ定義せよ（2026年度大問4 (2) は和集合版であった。共通部分との違いが分かるように書くこと）。

(3) 言語 $L = \{w \in \{0,1\}^* \mid w \text{ に含まれる0の個数と1の個数が等しい}\}$ が正則でないことを示したい。$\{0^n 1^n \mid n \ge 0\}$ が正則でないことは証明済みとしてよい。正則言語が共通部分について閉じていることを利用して、$L$ が正則でないことを背理法で証明せよ。

問題6【選択】電子回路と論理設計 ― CMOS・加算器・カウンタ（2019型）

配点：(1-1) 15, (1-2) 15, (2-1) 15, (2-2) 15, (3) 15, (4-1) 25, (4-2) 25

傾向準拠：CMOSトランジスタ構成＋加算器＋アップダウンカウンタは2019年度大問6の構成に準拠。ゲート遅延の見積もりは2023年度大問6（CMOS遅延）の系譜。

(1) CMOS回路に関する以下の各小問に答えよ。

(1-1) 2入力NANDをCMOSで構成する場合、pMOSトランジスタとnMOSトランジスタをそれぞれ何個、どのように（直列／並列）接続するかを述べ、回路図を描け。

(1-2) CMOS論理回路で、プルアップ側にpMOS・プルダウン側にnMOSを用いる理由を、各トランジスタが劣化なく通せる論理レベルに着目して2〜3行で説明せよ。

(2) 全加算器（入力 $a, b, c_{\mathrm{in}}$、出力 $s, c_{\mathrm{out}}$）について以下に答えよ。

(2-1) $s$ と $c_{\mathrm{out}}$ の論理式を示せ（$s$ は排他的論理和を用いてよい）。

(2-2) 半加算器2個とORゲート1個を用いて全加算器を構成する方法を、ブロック図で示せ。

(3) 全加算器を4個直列に接続したリップルキャリー加算器を考える。1個の全加算器において入力から桁上げ出力までの遅延を $\tau$ とし、他の遅延は無視する。最下位の桁上げ入力が変化してから最上位の桁上げ出力が確定するまでの最悪遅延を求めよ。また、この遅延を改善する加算器の方式名を1つ挙げよ。

(4) 制御入力 $u$ を持つ同期式2ビットカウンタを設計する。$u = 1$ のときアップカウント（$00 \to 01 \to 10 \to 11 \to 00$）、$u = 0$ のときダウンカウント（$00 \to 11 \to 10 \to 01 \to 00$）とする。状態は2個のDフリップフロップの出力 $(y_1, y_0)$ で表す。

(4-1) 入力 $u$ と現状態 $(y_1, y_0)$ に対する次状態 $(D_1, D_0)$ の状態遷移表を示せ。

(4-2) $D_1, D_0$ の最簡積和形をそれぞれ求めよ（カルノー図を示すこと）。簡単化できない場合はその旨を述べ、排他的論理和を用いた等価な表現も示せ。

問題7【選択】数学解析と信号処理 ― 移動平均フィルタとDTFT

配点：(1) 15, (2) 35, (3) 25, (4) 25, (5) 25

傾向準拠：sin比の周波数応答導出は2025年度大問7（矩形窓のDTFT）の計算の核と同一。移動平均フィルタとして文脈を変えて再演習する設計。線形位相の説明は発展。

インパルス応答 $$h[n] = \begin{cases} \dfrac{1}{N} & (0 \le n \le N-1) \\ 0 & (\text{otherwise}) \end{cases}$$ を持つ離散時間線形時不変システム（$N$ 点移動平均フィルタ）を考える。入力を $x[n]$、出力を $y[n]$ とする。

(1) 出力 $y[n]$ を畳み込み和 $y[n] = \sum_k h[k]\, x[n-k]$ の形で具体的に書き下し、このシステムがFIRフィルタである理由を1〜2行で述べよ。

(2) 周波数応答 $H(e^{j\omega}) = \sum_{n=-\infty}^{\infty} h[n] e^{-j\omega n}$ を等比級数の和を用いて計算し、 $$H(e^{j\omega}) = \frac{1}{N} e^{-j\omega (N-1)/2}\, \frac{\sin(N\omega/2)}{\sin(\omega/2)}$$ となることを導出せよ。

(3) $0 < \omega \le \pi$ の範囲で $|H(e^{j\omega})| = 0$ となる $\omega$ をすべて示せ。また、$\omega = 0$ での $|H(e^{j\omega})|$ の値を求め、このフィルタがローパス特性を持つことを説明せよ。

(4) このフィルタの位相特性が $\omega$ の一次式（線形位相）であることを(2)の結果から指摘し、線形位相であることが信号処理上どのような利点を持つか、通過帯域内の各周波数成分の遅延に着目して2〜3行で説明せよ。