第2回　予想問題（対抗シナリオ）

想定シナリオ：各大問の第2候補が揃った年（対抗）。問題1は未出のマージソート、問題2は排他制御（2022以来）、問題4はCNF/CYK、問題6はアナログ復活、問題7は2026の統計路線が継続。

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

問題1【必須】アルゴリズムとプログラミング ― マージソート

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

傾向準拠：マージソートは2008年度 問題1に出題実績があり、2018年度以降は未出（実績あるテーマの再来候補）。小問構成（特定行の実行回数→トレース→Σ導出→性質の説明）は2026年度 大問1の4段構成に準拠。

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

 1: #include <stdio.h>
 2: int count = 0;
 3:
 4: void merge(int A[], int left, int mid, int right, int tmp[]) {
 5:     int i = left, j = mid + 1, k = left;
 6:     while (i <= mid && j <= right) {
 7:         count++;
 8:         if (A[i] <= A[j]) tmp[k++] = A[i++];
 9:         else              tmp[k++] = A[j++];
10:     }
11:     while (i <= mid)   tmp[k++] = A[i++];
12:     while (j <= right) tmp[k++] = A[j++];
13:     for (k = left; k <= right; k++) A[k] = tmp[k];
14: }
15:
16: void funcA(int A[], int left, int right, int tmp[]) {
17:     if (left < right) {
18:         int mid = (left + right) / 2;
19:         funcA(A, left, mid, tmp);
20:         funcA(A, mid + 1, right, tmp);
21:         merge(A, left, mid, right, tmp);
22:     }
23: }
24:
25: int main(void) {
26:     int A[6] = {5, 2, 7, 1, 8, 3};
27:     int tmp[6];
28:     funcA(A, 0, 5, tmp);
29:     for (int k = 0; k < 6; k++) printf("%d ", A[k]);
30:     printf("\n");
31:     printf("%d\n", count);
32:     return 0;
33: }

図1　プログラム

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

(1-1) 長さ $n_1$ と $n_2$ の2つのソート済み区間を merge で併合するとき、7行目が実行される回数の最大値と最小値をそれぞれ $n_1, n_2$ を用いて示せ。

(1-2) 図1のプログラムを実行したときの funcA の分割の様子を図2に示す。空欄①〜④に入る部分配列を答えよ。

5, 2, 7, 1, 8, 3 5, 2, 7 1, 8, 3 ① 7 ② 3 ③ ④ ← merge後 ← merge後 図2　分割の様子（下段はmerge直後の部分配列。①〜④を埋めよ。最上段のmerge結果は省略）

(2) 図1のプログラムが開始してから終了するまでに出力される内容をすべて記述せよ。count の値については、各 merge 呼び出しでの比較回数の内訳も示すこと。

(3) $n = 2^k$（$k$ は正の整数）のとき、サイズ $n$ の配列に対する count の最大値が $n\log_2 n - n + 1$ となることを、各段の merge の比較回数を総和して導出せよ。

(4) 8行目の比較が A[i] <= A[j]（等号を含む）であることに着目し、このプログラムが安定ソート（stable sort）である理由を2〜3行で説明せよ。

(5) このプログラムがクイックソートと比べて不利な点を、記憶領域の観点から1つ挙げ、図1のどの変数がその原因かを明示して理由とともに述べよ。

問題2【必須】計算機システム ― セマフォ・排他制御

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

傾向準拠：P/V操作の穴埋め＋2セマフォでの昇順出力は2022年度 大問2の実出題形式に準拠。デッドロック・飢餓は2019年度 大問2の系譜。排他制御は2010・2014・2019・2022年度とほぼ4年周期で、2026〜2027年度は周期のただ中（旧年度分析で補強）。

単一プロセッサ上で動作する並行プロセスを考える。共有変数の更新は直ちに他プロセスから見えるものとする。セマフォ変数 $s$ に対する操作を以下のように定義する。

(1) サイズ1のバッファ buf を介して、生産者プロセスが書き込んだ値を消費者プロセスが読み出す。セマフォ empty（初期値1）と full（初期値0）を用いる。

生産者（10回繰り返す）          消費者（10回繰り返す）
for (i = 0; i < 10; i++) {     for (j = 0; j < 10; j++) {
    [ (a) ];                       [ (c) ];
    buf = i;                       x = buf;
    [ (b) ];                       [ (d) ];
}                                  printf("%d\n", x);
                                }

(1-1) P・V操作が不可分（atomic）に実行される必要がある理由を2〜3行で説明せよ。

(1-2) 0から9がすべて重複・欠落なくこの順で出力されるように、空欄 (a)〜(d) に入るP/V操作を答えよ。

(1-3) 空欄 (a) と (b) の操作を入れ替えた場合に何が起こるか。プロセスの実行順の具体例を挙げて2〜3行で説明せよ。

(2) デッドロックが発生するための4つの必要条件をすべて挙げよ。また、そのうち1つを崩してデッドロックを予防する具体的な方策を1つ述べよ。

(3) 二つのセマフォ s1（初期値1）と s2（初期値0）を用い、書き込みプロセス（関数g1）と読み出しプロセス（関数g2）を並行実行して、共有変数 n 経由で0から9を必ず昇順に出力したい。

void g1(void) {                 void g2(void) {
    int i;                          int j, x;
    for (i = 0; i < 10; i++) {     for (j = 0; j < 10; j++) {
        [ (あ) ];                      [ (う) ];
        n = i;                         x = n;
        [ (い) ];                      [ (え) ];
    }                                  printf("%d\n", x);
}                                   }
                                }

(3-1) 空欄 (あ)〜(え) に入るP/V操作を答えよ。

(3-2) s1 と s2 の初期値を両方とも0にした場合に何が起こるか、理由とともに2〜3行で述べよ。

問題4【選択】計算理論 ― CNF変換＋CYK法

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

傾向準拠：CNF変換とCYK表埋めは2020年度 大問4・2024年度 大問4で出題（4年間隔）。CYK表の一部を与えて残りを埋めさせる形式は2024年度に準拠。

文脈自由文法 $G = (V, T, P, S)$ を考える。生成規則がすべて $X \to YZ$（$Y, Z$ は変数）または $X \to a$（$a$ は終端記号）の形である文法をChomsky標準形（CNF）と呼ぶ。

(1) 文法 $G_1$：変数 $\{S, A\}$、終端記号 $\{a, b\}$、生成規則 $$S \to AbA, \qquad A \to a \mid \varepsilon$$ を、$L(G_1)$ を変えずに（$\varepsilon \notin L(G_1)$ に注意）CNFに変換せよ。ε規則の除去 → 終端記号の変数化 → 長さ3以上の規則の分解、の各段階の結果を示すこと。

(2) CNFの文法 $G_2$：変数 $\{S, A, B, C\}$、終端記号 $\{a, b\}$、生成規則 $$S \to AB \mid BC, \quad A \to BA \mid a, \quad B \to CC \mid b, \quad C \to AB \mid a$$ と語 $w = baaba$ に対してCYK法を実行する。$V_{i,j}$ を「$w$ の $i$ 文字目から $j$ 文字目までの部分語を導出できる変数の集合」とする。表1の空欄をすべて埋めよ（長さ1の行は埋めてある）。

長さ＼開始位置1 (b)2 (a)3 (a)4 (b)5 (a)
1{B}{A, C}{A, C}{B}{A, C}
2
3
4
5
表1　CYK表（灰色セルは使用しない）

(3) 表1の結果に基づき、$w = baaba \in L(G_2)$ かどうかを判定し、根拠を述べよ。

(4) 語の長さを $n$、文法の規則数を $|P|$ とするとき、CYK法の時間計算量が $O(n^3 |P|)$ となる理由を、アルゴリズムのループ構造に基づいて2〜3行で説明せよ。

(5) CYK法を適用する前に文法をCNFに変換しておく必要がある理由を、$V_{i,j}$ の計算方法に着目して2〜3行で説明せよ。

問題6【選択】電子回路と論理設計 ― フェーザ・共振＋論理設計

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

傾向準拠：2018〜2024年度の「電子回路＋論理設計」2部構成への回帰シナリオ。交流回路は2023年度 大問6、K-map最簡化＋NAND構成は2024年度 大問6の型。(2-3)の系列検出は2013年度 問題6（連続する1/0の検出回路）に同型の実出題あり。

(1) 図1に示すRLC直列回路について、フェーザ表示を用いて以下に答えよ。

～ V̇ R L C → İ 図1　RLC直列回路（電源は角周波数 ω，実効値 V の正弦波）

(1-1) 合成インピーダンス $\dot{Z}$ を $R, L, C, \omega$ で示せ。

(1-2) 電流の大きさが最大となる共振角周波数 $\omega_0$ を導出せよ。

(1-3) $\omega < \omega_0$ と $\omega > \omega_0$ のそれぞれで、電流の位相が電源電圧に対して進むか遅れるか、理由とともに答えよ。

(1-4) 共振時のコンデンサ両端電圧の大きさが $V_C = QV$（$Q = \omega_0 L / R$）となることを導出せよ。

(2) 論理設計に関する以下の各小問に答えよ。

(2-1) $f(a,b,c,d) = \sum m(0,2,5,7,8,10,13,15)$ の最簡積和形をカルノー図を用いて求めよ。カルノー図も示すこと。

(2-2) (2-1)の結果を2入力NANDゲートのみで実現する回路を示し、ゲート数を答えよ（NOTは入力を束ねた2入力NANDで実現してよい）。

(2-3) 入力系列に部分列 $101$ が現れた時点で1を出力するMealy型同期式順序回路を設計する（重なりを許す：$10101$ では2回検出）。
(a) 状態数最小の状態遷移図を、各状態が「何を覚えているか」とともに示せ。
(b) 状態割り当て $S_0=(0,0)$, $S_1=(0,1)$, $S_2=(1,0)$ のもとDフリップフロップ2個で実現するときの $D_1, D_0, z$ の最簡積和形を求めよ。未使用状態 $(1,1)$ はドントケアとしてよい。

問題7【選択】数学解析と信号処理 ― 最尤推定・最小二乗・標本化

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

傾向準拠：2026年度 大問7（正規分布の最尤推定・最小二乗との一致・標本化）の路線継続シナリオ。導出の型は同一のまま、題材を指数分布に変更。エイリアシングの図示は2026年度の図の形式に準拠。

(1) パラメータ $\lambda > 0$ の指数分布の確率密度関数を $$f(x; \lambda) = \lambda e^{-\lambda x} \quad (x \ge 0)$$ とする。互いに独立な観測データ $\mathcal{D} = \{x_1, \dots, x_n\}$（$x_i \ge 0$）が与えられたとき、以下に答えよ。導出の過程も示すこと。

(1-1) 対数尤度 $\log L(\lambda) = \log \prod_{i=1}^{n} f(x_i; \lambda)$ を $\lambda$ と $\sum_i x_i$ を用いて表せ。

(1-2) 対数尤度を最大化する $\hat{\lambda}$ を求めよ。また、求めた停留点が極大であることを2階微分により確認せよ。

(2) 原点を通る直線モデル $\hat{y} = \phi x$ で観測データ $(x_1, y_1), \dots, (x_n, y_n)$ を近似する。

(2-1) 残差二乗和 $E(\phi) = \sum_{i=1}^{n} (y_i - \phi x_i)^2$ を最小にする $\hat{\phi}$ を導出せよ。

(2-2) 残差 $r_i = y_i - \phi x_i$ が独立に平均0・分散 $\sigma^2$ の正規分布に従うと仮定するとき、$\phi$ の最尤推定が(2-1)の最小二乗解と一致することを示せ。

(3) 周波数 $f_0 = 3$ [Hz] の正弦波 $y^*(t) = \sin(2\pi f_0 t)$ を、サンプリング周波数 $f_s = 4$ [Hz] で標本化した（図1の●）。

t [s] y 00.51.0 原信号 y*(t)（実線, f₀ = 3 Hz） 破線の正弦波（周波数 f₁） ● 標本点（fₛ = 4 Hz）
図1　原信号（実線）、標本点（●）、および標本点をすべて通る低周波の正弦波（破線）

(3-1) 原信号を標本から一意に復元するためにサンプリング周波数が満たすべき条件（標本化定理）を示せ。

(3-2) 図1の破線のように、標本点だけを見ると原信号は別の低い周波数 $f_1$ の正弦波と区別できない。$f_1$ の値を求め、この現象の名称を答えよ。

(3-3) $f_s = 4$ [Hz] のまま標本化の前処理によって(3-2)の現象の影響を防ぐ方法を、フィルタの種類と遮断周波数の条件を明示して2〜3行で述べよ。