第4回　予想問題（理論・変換系の重量級年）

想定シナリオ：理論・変換系の重量級年。問題4が2022型の理論寄り（決定性・prefix-free）、問題7が2024型の複素解析、問題2はアドレス変換・EATの計算重視、問題6は2026型データパスの変奏、問題1は未出の基数ソート。

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

問題1【必須】アルゴリズムとプログラミング ― 基数ソート（未出テーマ）

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

傾向準拠：基数ソートは2016年度 問題1に出題実績があり、2018年度以降は未出（約10年ぶりの再来候補）。コード穴埋め形式は2023年度 大問1（ハッシュのinsert穴埋め）に準拠。

図1はANSI Cで記述されたプログラムであり、10進数で最大 $d$ 桁の非負整数 $n$ 個を最下位桁から順に整列するLSD基数ソート（radix sort）を実装している。各桁の整列には、値の範囲が0〜9であることを利用したカウンティングソート（counting sort）を用いる。図1のプログラムに関する以下の各問に答えよ。

 1: #include <stdio.h>
 2: #define N 7
 3:
 4: int digit(int x, int p) { return (x / p) % 10; }
 5:
 6: void counting_sort(int A[], int B[], int n, int p) {
 7:     int C[10] = {0};
 8:     for (int i = 0; i < n; i++) C[digit(A[i], p)]++;
 9:     for (int v = 1; v < 10; v++) [ (a) ];
10:     for (int i = n - 1; i >= 0; i--) {
11:         C[digit(A[i], p)]--;
12:         B[ [ (b) ] ] = A[i];
13:     }
14: }
15:
16: void funcA(int A[], int n, int d) {
17:     int B[N];
18:     int p = 1;
19:     for (int r = 0; r < d; r++) {
20:         counting_sort(A, B, n, p);
21:         for (int i = 0; i < n; i++) A[i] = B[i];
22:         [ (c) ];
23:     }
24: }
25:
26: int main(void) {
27:     int A[N] = {329, 457, 657, 839, 436, 720, 355};
28:     funcA(A, N, 3);
29:     for (int i = 0; i < N; i++) printf("%d ", A[i]);
30:     printf("\n");
31:     return 0;
32: }

図1　プログラム

(1) プログラムが正しく動作するように、空欄 (a), (b), (c) を埋めよ。（ヒント：9行目終了時点で C[v] は「着目桁の値が $v$ 以下である要素の個数」になっている必要がある。）

(2) 図1のプログラムを実行したとき、19行目のループの各反復（$r = 0, 1, 2$）が終わった時点での配列 A の内容をそれぞれ示せ。また、プログラムの出力を記述せよ。

(3) 10行目のループが $i = n-1$ から降順に走査している理由を、整列の安定性（stability）と関連付けて2〜3行で説明せよ。

(4) 各桁の整列に安定でないソートを用いると基数ソートが正しく動作しないことを、2要素からなる具体的な反例を挙げて説明せよ。

(5) 要素数 $n$、桁数 $d$、各桁の値の種類数 $k$ とするとき、funcA 全体の時間計算量をオーダ表記で示し、根拠を述べよ。

(6) 比較に基づくソートの最悪比較回数には $\Omega(n \log n)$ の下界が存在することが知られている。基数ソートがこの下界より高速になり得るのはなぜか、下界の導出が置いている前提に着目して2〜3行で説明せよ。

問題2【必須】計算機システム ― アドレス変換・TLB・実効アクセス時間

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

傾向準拠：アドレス変換・TLBは2023年度 大問2の実出題。EAT（実効アクセス時間）の数値計算はその発展。2段ページテーブルは未出の発展テーマ。

ページング方式の仮想記憶システムを考える。仮想アドレスは32ビット、ページサイズは4 KiB、物理メモリは1 GiBとする。

(1) ページ内オフセット、仮想ページ番号、物理フレーム番号のビット数をそれぞれ求めよ。

(2) 1エントリ4バイトの1段ページテーブルを考える。

(2-1) 1プロセスあたりのページテーブルのサイズを求めよ。

(2-2) (2-1)の問題を緩和するために、仮想ページ番号を上位10ビットと下位10ビットに分けた2段ページテーブルを用いる。外側ページテーブル（1段目）のエントリ数と、プロセスが仮想アドレス空間のごく一部しか使用しない場合に2段方式がメモリを節約できる理由を2〜3行で述べよ。

(3) TLB（Translation Lookaside Buffer）のアクセス時間を20 ns、主記憶のアクセス時間を100 nsとする。TLBヒット時は「TLB＋主記憶1回」、TLBミス時は「TLB＋ページテーブル参照（主記憶1回）＋主記憶1回」の時間がかかるものとする（1段ページテーブル）。TLBヒット率が98%のときの実効メモリアクセス時間（EAT）を求めよ。

(4) TLBの影響を無視し、主記憶アクセスを100 ns、ページフォルト処理時間を10 msとする。ページフォルト率を $p$ とするとき、実効アクセス時間を $p$ の式で表せ。さらに、実効アクセス時間を200 ns以下にするために許容される $p$ の上限を求めよ（有効数字2桁）。この結果からページフォルト率について言えることを1行で述べよ。

問題4【選択】計算理論 ― PDA理論（2022型）

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

傾向準拠：2022年度 大問4（空スタック受理・DPDA）の型に準拠。(4)のprefix-free証明は2022年度の実出題テーマ（出回っている解答例に誤りが多い論点）。

プッシュダウンオートマトン（PDA）を $(Q, \Sigma, \Gamma, \delta, q_0, Z, F)$ で表す。$Z \in \Gamma$ はスタックの開始記号である。遷移のラベル $r, s/t$ は「入力から $r$ を読み、スタックトップの $s$ を取り除いて $t$ を積む」ことを意味する（2025年度 大問4と同じ記法）。

(1) 中央に区切り記号を持つ回文の言語 $L_1 = \{w c w^R \mid w \in \{a, b\}^*\}$（$w^R$ は $w$ の反転）を最終状態受理で認識する決定性PDAを構成し、すべての遷移を列挙せよ。

(2) 区切り記号のない偶数長回文の言語 $L_2 = \{w w^R \mid w \in \{a, b\}^*\}$ は、決定性PDAでは認識できないことが知られている。$L_1$ と異なり決定性では認識できない直感的な理由を、「どの時点でスタックへの積み込みから照合に切り替えるか」に着目して2〜3行で述べよ。

(3) 空スタック受理のPDA $M$ が与えられたとき、$M$ と同じ言語を最終状態受理で認識するPDA $M'$ を構成する一般的な方法を述べよ。新しい底記号・開始状態・受理状態をどのように導入するかを明示すること。

(4) 言語 $L$ が空スタック受理の決定性PDAで認識されるならば、$L$ は語頭独立（prefix-free：$L$ のどの語も、$L$ の他の語の真の接頭辞にならない）であることを証明せよ。（ヒント：$u \in L$ かつ $uv \in L$（$v \ne \varepsilon$）となる語が存在すると仮定し、決定性と空スタック受理の定義から矛盾を導く。）

問題6【選択】電子回路と論理設計 ― スタックの専用ハードウェア（2026型変奏）

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

傾向準拠：2026年度 大問6（カウンタ2個＋メモリでFIFOキュー）の変奏（カウンタ1個でLIFOスタック）。空/満判定の積和標準形は2026年度の必出小問に準拠。

図1に示すデータパスは、4ビットアップダウンカウンタSPと、8ビットデータを8語格納できるメモリMemory Aから構成される。CLKに同期して動作し、次の仕様を持つ抽象データ型を実現する。

• SP：4ビットカウンタ（値の範囲は0〜15）。rst = 1 で0に初期化。up = 1 でカウントアップ、down = 1 でカウントダウン（同時に1になることはない）。
• Memory A：w_en = 1 のときCLKに同期して、アドレス入力 adr（SPの下位3ビット）の番地に w_dat の8ビット値を書き込む。読み出しは常時、adr 番地の内容を r_dat に出力する。
• push操作：w_en = 1, up = 1 とする。SPの現在値の番地への書き込みと、SPのカウントアップが同一クロックで行われる。
• pop操作：down = 1 とする（このサイクルでSPがデクリメントされ、次のサイクルで r_dat にトップの値が現れる）。

(1) リセット直後から push 3 → push 7 → push 2 → pop → pop を順に実行した。各操作の完了直後のSPの値と、メモリの0〜2番地の内容を表で示せ。

(2) SPの値を $(s_3, s_2, s_1, s_0)$ とする。「スタックが空」を表す信号 $E$ と「スタックが満杯（8語すべて使用中）」を表す信号 $F$ の論理式を、積和標準形でそれぞれ示せ。

(3) SPを3ビットではなく4ビットにしている理由を、(2)の $E$ と $F$ の区別に着目して2〜3行で説明せよ。

(4) このデータパスが実現している抽象データ型の名称を答えよ。また、2026年度に出題された「カウンタ2個＋メモリ」の構成が実現する抽象データ型と、データの取り出し順序の違いを1〜2行で述べよ。

(5) 空の状態でpop（アンダーフロー）、満杯の状態でpush（オーバーフロー）が要求されたとき、状態を変化させず要求を無視するように制御回路を改造したい。$E, F$ と外部からの要求信号 req_push, req_pop を用いて、up, down, w_en の論理式を示せ。

問題7【選択】数学解析と信号処理 ― 複素解析・留数とラプラス変換（2024型）

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

傾向準拠：複素線積分・特異点は2024年度 大問7・2022年度 大問7の型。留数定理からの実積分は発展。逆ラプラスの部分分数分解は2022年度 大問7に準拠。

以下の各問に答えよ。ただし導出の過程も示すこと。$j$ を虚数単位とする（複素解析の慣例に従い $i$ と書いてもよい）。

(1) 複素関数 $f(z) = \dfrac{1}{z^2 + 1}$ の特異点をすべて求め、それぞれの点における留数を計算せよ。

(2) 以下の複素線積分の値を留数定理を用いて求めよ。積分路はいずれも反時計回りとする。

(2-1) $\displaystyle\oint_{|z - i| = 1} \frac{dz}{z^2 + 1}$

(2-2) $\displaystyle\oint_{|z| = 2} \frac{dz}{z^2 + 1}$

(3) $F(s) = \dfrac{1}{(s+1)(s^2+4)}$ の逆ラプラス変換 $f(t)$（$t \ge 0$）を、部分分数分解を用いて求めよ。

(4) 実軸上の広義積分 $\displaystyle\int_{-\infty}^{\infty} \frac{dx}{x^2 + 1}$ を、上半平面の半円周を含む閉路に留数定理を適用して求めよ。半円周上の積分が半径 $R \to \infty$ で0に収束することの根拠も述べること。