第1回　予想問題（本命シナリオ）

想定シナリオ：各大問の最有力空白テーマが揃った年（本命）。問題1はクイック再出（4年空き）、問題2はキャッシュ復活（9年空き）、問題4はCFG/PDA回帰＋反復補題、問題6はデータパス型継続、問題7は変換系複合。

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

問題1【必須】アルゴリズムとプログラミング ― クイックソートと二分探索

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

傾向準拠：ソート＋二分探索のペア構成は2024年度大問1（挿入ソート＋二分探索）・2026年度大問1（バブルソート＋二分探索）の定型に準拠。クイックソート自体は2019・2022年度大問1に出題があり、4年空きでの再出を想定。

図1はANSI Cで記述されたプログラムである。大域変数 countA, countB はそれぞれ11行目・33行目の条件式が評価された回数を数えるカウンタである。図1のプログラムに関する以下の各問に答えよ。

 1: #include <stdio.h>
 2:
 3: int countA = 0, countB = 0;
 4:
 5: void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }
 6:
 7: int partition(int A[], int left, int right) {
 8:     int pivot = A[right];
 9:     int i = left - 1;
10:     for (int j = left; j < right; j++) {
11:         countA++;
12:         if (A[j] < pivot) {
13:             i++;
14:             swap(&A[i], &A[j]);
15:         }
16:     }
17:     swap(&A[i + 1], &A[right]);
18:     return i + 1;
19: }
20:
21: void funcA(int A[], int left, int right) {
22:     if (left < right) {
23:         int p = partition(A, left, right);
24:         funcA(A, left, p - 1);
25:         funcA(A, p + 1, right);
26:     }
27: }
28:
29: int funcB(int A[], int n, int target) {
30:     int low = 0, high = n - 1;
31:     while (low <= high) {
32:         int mid = (low + high) / 2;
33:         countB++;
34:         if (A[mid] == target) return mid;
35:         else if (A[mid] < target) low = mid + 1;
36:         else high = mid - 1;
37:     }
38:     return -1;
39: }
40:
41: int main(void) {
42:     int A[6] = {5, 3, 8, 1, 7, 2};
43:     funcA(A, 0, 5);
44:     for (int k = 0; k < 6; k++) printf("%d ", A[k]);
45:     printf("\n");
46:     printf("%d\n", funcB(A, 6, 7));
47:     printf("%d %d\n", countA, countB);
48:     return 0;
49: }

図1　プログラム

(1) 以下の各小問に答えよ。

(1-1) partition(A, left, right) の1回の呼び出しにおいて、11行目が実行される回数を、引数 left, right を用いて示せ。

(1-2) サイズ $n$ の昇順ソート済み配列を第一引数として funcA(A, 0, n-1) を呼び出したとき、終了時の countA の値を $n$ を用いて示せ。各再帰段階での partition の比較回数を総和する導出過程も示すこと。

(1-3) 関数 funcA が実装するアルゴリズムの最悪時間計算量のオーダ表記として最も適しているものを、下記の選択肢から一つ選択せよ。ただし配列のサイズを $N$ とする。
$O(1)$　$O(\log N)$　$O(N)$　$O(N\log N)$　$O(N^2)$　$O(N^3)$　$O(2^N)$　$O(N!)$

(2) 図1のプログラムが開始してから終了するまでに出力される内容をすべて記述せよ。途中経過（funcA 内の最初の partition(A, 0, 5) が返った直後の配列の内容と返り値）も併せて示すこと。

(3) 以下の各小問に答えよ。

(3-1) サイズ $n$ のソート済み配列に対して funcB を呼び出したとき、33行目が評価される最大の回数を $n$ を用いて示せ。

(3-2) 関数 funcB が実装するアルゴリズムの最悪時間計算量のオーダ表記として最も適しているものを、(1-3) の選択肢から一つ選択せよ。

(4) ソート済みに近い入力に対しても funcA の最悪時間計算量の発生を避けたい。8行目をどのように変更すればよいか、具体的な方法を一つ挙げ、その方法により最悪ケースが回避される（または発生確率が無視できるほど小さくなる）理由を2〜3行で説明せよ。

問題2【必須】計算機システム ― キャッシュ＋仮想記憶

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

傾向準拠：キャッシュの本格出題は2018年度大問2が最後（9年空白＝最大の狙い目）。アドレス分割・ヒット/ミス判定の形式は2018年度大問2、ページング・アドレス変換は2023年度大問2、置換アルゴリズムは2024年度大問2の型に準拠。

(1) キャッシュメモリに関する以下の各小問に答えよ。主記憶はバイトアドレッシング、アドレスは16ビット。キャッシュはダイレクトマップ方式、容量1 KiB、ブロックサイズ16バイトとする。

(1-1) 図1のア〜ウ（タグ・インデックス・オフセットのビット数）を答えよ。

(1-2) キャッシュが空の状態から次の順にアクセスした。各アクセスのヒット／ミスを順に答えよ。
0x0040 → 0x0044 → 0x0440 → 0x0048 → 0x0840 → 0x0444

(1-3) 容量とブロックサイズを変えず2ウェイセットアソシアティブ方式（置換はLRU）に変更した場合の、同じアクセス列に対するヒット／ミスを順に答えよ。

(2) ページング方式の仮想記憶に関する以下の各小問に答えよ。論理アドレス16ビット、ページサイズ1 KiBとする。

(2-1) 論理アドレス 0x2C8F のページ番号とページ内オフセットを16進数で答えよ。

(2-2) (2-1)のページに対応するフレーム番号が 0x05 のとき、物理アドレスを16進数で答えよ。

(2-3) ページ参照列 1,2,3,4,1,2,5,1,2,3,4,5 に対してFIFO置換を行う。フレーム数3と4のそれぞれでページフォルト回数を答えよ（各時刻のフレーム内容を表で示すこと）。また、この結果に見られる現象の名称を答えよ。

(2-4) LRUでは(2-3)の現象が発生しない。フレーム数 $k$ のとき保持されるページ集合と $k+1$ のときの集合の包含関係に着目して、理由を2〜3行で説明せよ。

問題4【選択】計算理論 ― CFG/PDA＋反復補題

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

傾向準拠：骨格3本（FA構築／PDA構築／反復補題）で構成。状態数を意識したDFA構成は2025年度大問4、サブセット構成は2026年度大問4、CFG・PDA構成は2021〜2025年度大問4の継続テーマ。明示的な反復補題は2015・2017・2019年度と隔年期があったのに2019年度以来6年空白（旧年度分析で補強）。

(1) 有限オートマトンに関する以下の各小問に答えよ。アルファベットは $\Sigma = \{0, 1\}$ とする。

(1-1) 「0の個数が偶数、かつ1の個数が3の倍数である語」を認識する最小DFAの状態数を答え、状態遷移図を示せ。

(1-2) 図1のNFA $N$（開始状態 $p$、受理状態 $r$）に対し、サブセット構成法で等価なDFAを構成せよ。到達可能な部分集合のみで状態遷移図を描くこと。また $N$ が認識する言語を日本語で簡潔に述べよ。

図1　NFA $N$ の状態遷移図

(2) 言語 $L_2 = \{a^i b^j \mid 0 \le i < j\}$ について以下に答えよ。

(2-1) $L_2$ を生成する文脈自由文法 $G$ を示し、語 $abb$ の最左導出を一つ示せ。

(2-2) $L_2$ を最終状態受理で認識するPDAを構成し、すべての遷移を $\delta(q, a, X) \ni (q', \gamma)$ の形式で列挙せよ。スタックを何に使うか、設計方針も2〜3行で述べること。

(3) 反復補題に関する以下の各小問に答えよ。

(3-1) $L_3 = \{a^n b^m \mid n > m \ge 0\}$ が正則でないことを、正則言語の反復補題を用いて証明せよ。

(3-2) $L_4 = \{a^n b^n c^n \mid n \ge 0\}$ が文脈自由でないことを、文脈自由言語の反復補題を用いて証明せよ。場合分けを明示すること。

問題6【選択】電子回路と論理設計 ― 乗算器のデータパス＋制御回路

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

傾向準拠：「データパス＋制御回路」型は2025年度大問6（フィボナッチ生成専用HW）・2026年度大問6（カウンタ＋メモリのFIFO）の直系。状態遷移表→D-FF入力の最簡積和形という流れは両年とも出題。

4ビット符号なし2進数どうしの乗算 $P = A \times B$ を行う専用ハードウェア（逐次加算シフト方式）を設計する。図1のデータパスと制御回路から構成され、クロック信号CLKに同期して動作する。

図1　乗算器のデータパス

レジスタP（8ビット）：積を蓄積。clear=1 でCLKに同期して0に初期化。en_add=1 のときCLKに同期して加算器ADDの出力を取り込む。
レジスタA（8ビット）：被乗数を保持。load=1 で入力（4ビットの被乗数の上位4ビットを0で埋めた値）を取り込む。en_shift=1 のとき1ビット左論理シフト。
レジスタB（4ビット）：乗数を保持。load=1 で入力を取り込む。en_shift=1 のとき1ビット右論理シフト（最上位に0）。
加算器ADD：PとAの値を加算（桁上げは無視）。
制御回路はBの最下位ビット $b_0$ を参照でき、en_shift=1 かつ $b_0 = 1$ のときのみ en_add=1 とする。

動作概要：load で $A, B$ を取り込み clear で $P$ を初期化後、4サイクルにわたり「$b_0=1$ なら $P \leftarrow P+A$、同時に $A$ を左シフト・$B$ を右シフト」を繰り返すと、4サイクル後に $P = A \times B$ となる。

(1) $A = 0101_2$、$B = 0011_2$ とする。初期化完了直後を第0サイクルとし、第1〜第4サイクル終了時のP・A・Bの値を2進数で表にまとめよ。

(2) 最終的に $P = A \times B$ が得られる理由を、乗数の2進展開 $B = \sum_{i=0}^{3} b_i 2^i$ に基づいて2〜3行で説明せよ。

(3) 制御回路をMoore型同期式順序回路として設計する。状態は $S_{\mathrm{IDLE}}$、計算状態 $S_0$〜$S_3$、$S_{\mathrm{DONE}}$ の6状態。外部入力 start を受け、$S_{\mathrm{IDLE}}$ で start=1 なら $S_0$ へ遷移して計算開始、$S_3$ の次に $S_{\mathrm{DONE}}$ で done=1 を1サイクル出力して $S_{\mathrm{IDLE}}$ に戻る。状態遷移図を、各状態の出力（clear, load, en_shift, done）とともに示せ。

(4) 状態割り当てを $S_{\mathrm{IDLE}}=(y_2,y_1,y_0)=(0,0,0)$、$S_0=(0,0,1)$、$S_1=(0,1,0)$、$S_2=(0,1,1)$、$S_3=(1,0,0)$、$S_{\mathrm{DONE}}=(1,0,1)$ とし、Dフリップフロップ3個で実現する。$D_2, D_1, D_0$ と done の最簡積和形を $y_2, y_1, y_0$, start で表せ。未使用状態 $(1,1,0),(1,1,1)$ はドントケアとしてよい。

(5) $B = 0001_2$ のような場合でもこの設計は常に4サイクルを要する。Bの残りビットがすべて0になった時点で計算を打ち切り done を出力するには、データパスと制御回路にどのような変更が必要か、具体的に述べよ。

問題7【選択】数学解析と信号処理 ― ラプラス・z変換・フーリエ級数

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

傾向準拠：ラプラス（逆変換・微分方程式）は2018・2021・2022年度大問7、z変換・伝達関数・BIBO安定・振幅特性は2023年度大問7の型。フーリエ級数は2011・2016・2020年度とほぼ5年周期で、2020年度から既に周期超過（旧年度分析で補強）。

(1) ラプラス変換に関する以下の各小問に答えよ。導出の過程も示すこと。

(1-1) $F(s) = \dfrac{1}{s(s+2)}$ の逆ラプラス変換 $f(t)$（$t \ge 0$）を求めよ。

(1-2) 微分方程式 $\dfrac{dy}{dt} + 3y(t) = e^{-t}$、$y(0) = 0$ をラプラス変換を用いて解け。

(2) 因果的な離散時間システム $y[n] = x[n] + a\,y[n-1]$（$a$ は実数）について以下に答えよ。

(2-1) 伝達関数 $H(z)$ を求めよ。

(2-2) インパルス応答 $h[n]$ を求めよ。

(2-3) BIBO安定であるための $a$ の条件を極の位置に基づいて示し、そのとき $\sum_{n=0}^{\infty}|h[n]|$ が収束することを確認せよ。

(2-4) $0 < a < 1$ とする。$|H(e^{j\omega})|$ を $a, \omega$ で表し、$\omega = 0, \pi$ での値を求めよ。さらにローパス・ハイパスのどちらの特性か、計算結果に基づいて答えよ。

(3) 図1に示す周期 $2\pi$ の方形波 $$f(x) = \begin{cases} 1 & (0 < x < \pi) \\ -1 & (-\pi < x < 0) \end{cases}, \qquad f(x) = f(x+2\pi)$$ について以下に答えよ。

図1　方形波 $f(x)$

(3-1) $f(x)$ のフーリエ級数展開を求めよ。係数 $a_n, b_n$ の計算過程も示すこと。