第2回 解答（対抗シナリオ）
📄 解答PDF版をダウンロード対応する問題：第2回 予想問題。記述式の小問（「〜行で説明せよ」）は解答例であり、同じ内容が伝わる表現なら形は問わない。誤りを見つけたら作成者（Claude）に報告してほしい。
問題1 マージソート 解答
(1-1) 最大 $n_1+n_2-1$ 回（最後の1個が残るまで交互に比較が続く場合）、最小 $\min(n_1,n_2)$ 回（片方が先に尽きる場合）。
(1-2) ①$\{5,2\}$ ②$\{1,8\}$ ③$\{2,5,7\}$ ④$\{1,3,8\}$。
(2) merge の比較回数の内訳：merge(0,0,1)＝1回（$[5],[2]$）、merge(0,1,2)＝2回（$[2,5],[7]$）、merge(3,3,4)＝1回（$[1],[8]$）、merge(3,4,5)＝2回（$[1,8],[3]$）、merge(0,2,5)＝5回（$[2,5,7],[1,3,8]$）。合計 11。出力：
1 2 3 5 7 8 11
(3) 併合後サイズ $2^l$ の段（$l=1,\dots,k$）では merge が $n/2^l$ 回行われ、各回の比較は最大 $2^l-1$。段ごとの合計は $\dfrac{n}{2^l}(2^l-1)=n-\dfrac{n}{2^l}$。全段の総和： $$\sum_{l=1}^{k}\Bigl(n-\frac{n}{2^l}\Bigr)=kn-n\Bigl(1-\frac{1}{2^k}\Bigr)=kn-(n-1)=n\log_2 n-n+1.$$
(4) 等しいキーのときは A[i] <= A[j] が真となり左区間（元の並びで前方）の要素が先に tmp へ移される。よって同値要素の相対順序が保存され、安定ソートである。
(5) 補助配列 tmp（入力と同じサイズ $n$）が必要で、追加記憶領域が $O(n)$。クイックソートは配列内の交換だけで動作し（再帰スタックの $O(\log n)$ を除き）追加領域を要しない点で有利。
問題2 セマフォ・排他制御 解答
(1-1) 「$s>0$ の検査」と「$s$ の減算」が分割できると、2つのプロセスが同時に $s=1>0$ を確認してともに通過する、といった競合が起こり、相互排除や個数管理の意味が壊れるため。検査と更新は一体（不可分）でなければならない。
(1-2) (a) P(empty) (b) V(full) (c) P(full) (d) V(empty)。
(1-3) 生産者が V(full); buf = i; P(empty) の順になると、buf への書き込みより前に消費者の P(full) が通過できてしまう。例：生産者が V(full) を実行した直後に消費者が P(full)→x=buf を実行すると、まだ書き込まれていない（または前回の）値を読む。値の重複・欠落が起こり得る。
(2) ①相互排除（資源は同時に1プロセスのみ使用）②保持と待機（資源を保持したまま別資源を待つ）③横取り不可（資源を強制的に奪えない）④循環待機（待ちの環が存在）。方策例：すべての資源に全順序を定め、必ず昇順にのみ獲得させる（④循環待機を崩す）。
(3-1) (あ) P(s1) (い) V(s2) (う) P(s2) (え) V(s1)。書き手と読み手が交互にしか進めなくなり、n への書き込みと読み出しが1回ずつ厳密に交替する。
(3-2) 両方の初期値が0だと、g1 は P(s1) で、g2 は P(s2) で最初から待ち続け、どちらも V を実行できない。互いに相手の V を待つ形になりデッドロックする。
問題4 CNF変換＋CYK法 解答
(1) ε規則除去：nullable は $\{A\}$。$A$ の出現を場合分けして $S\to AbA \mid Ab \mid bA \mid b$、$A\to a$（$A\to\varepsilon$ を削除）。単位規則はない。終端記号の変数化：$U_b\to b$ を導入し $S\to AU_bA \mid AU_b \mid U_bA \mid b$。長さ3の規則を分解：$X\to U_bA$ を導入して、最終形： $$S\to AX \mid AU_b \mid U_bA \mid b,\quad X\to U_bA,\quad A\to a,\quad U_b\to b.$$
(2)（$V_{i,j}$ を「開始位置 $i$・長さ $j$」で表記）
| 長さ＼開始 | 1 (b) | 2 (a) | 3 (a) | 4 (b) | 5 (a) |
|---|---|---|---|---|---|
| 1 | {B} | {A,C} | {A,C} | {B} | {A,C} |
| 2 | {S,A} | {B} | {S,C} | {S,A} | — |
| 3 | ∅ | {B} | {B} | — | — |
| 4 | ∅ | {S,A,C} | — | — | — |
| 5 | {S,A,C} | — | — | — | — |
（例：長さ2の「ba」＝$B\cdot\{A,C\}$：$A\to BA$ と $S\to BC$ が該当して $\{S,A\}$。以降も同様に、2分割ごとに右辺2変数の規則と照合する。）
(3) $S \in V_{1,5}$ なので $baaba \in L(G_2)$。
(4) 「長さ」「開始位置」「分割点」の3重ループがそれぞれ最大 $n$ 通りで $O(n^3)$、各組合せで全規則を走査するので $O(n^3|P|)$。
(5) CYKは各部分語を「2つの連続する部分語への分割」の全列挙で埋める。CNFでは変数の規則が必ず $X\to YZ$（2変数）なので、この2分割だけで導出可能性を完全に判定できる。右辺の長さが3以上の規則や単位・ε規則があると2分割との対応が崩れる。
問題6 フェーザ・共振＋論理設計 解答
(1-1) $\dot{Z}=R+j\left(\omega L-\dfrac{1}{\omega C}\right)$。
(1-2) $|\dot{Z}|=\sqrt{R^2+(\omega L-1/\omega C)^2}$ が最小 ⇔ 虚部が0 ⇔ $\omega L=\dfrac{1}{\omega C}$。よって $\omega_0=\dfrac{1}{\sqrt{LC}}$。
(1-3) $\omega<\omega_0$ では $\dfrac{1}{\omega C}>\omega L$ で虚部が負（容量性）→ 電流は電圧より進む。$\omega>\omega_0$ では誘導性 → 遅れる。
(1-4) 共振時 $\dot{Z}=R$ なので $I=V/R$。コンデンサ電圧は $$V_C=\frac{I}{\omega_0 C}=\frac{V}{\omega_0 CR}.$$ $\omega_0=1/\sqrt{LC}$ より $\dfrac{1}{\omega_0 C}=\sqrt{\dfrac{L}{C}}=\omega_0 L$。よって $V_C=\dfrac{\omega_0 L}{R}V=QV$。
(2-1) K-mapで $b=d$ のマス（$b'd'$ の4マスと $bd$ の4マス）がちょうど覆われる：$f=\bar{b}\bar{d}+bd$。
(2-2) $f=\left(\overline{(\bar b \bar d)}\cdot\overline{(bd)}\right)'$ とみなす。$\bar b=\mathrm{NAND}(b,b)$、$\bar d=\mathrm{NAND}(d,d)$、$t_1=\mathrm{NAND}(\bar b,\bar d)$、$t_2=\mathrm{NAND}(b,d)$、$f=\mathrm{NAND}(t_1,t_2)$。5ゲート。
(2-3) (a) 状態：$S_0$（有効な接頭なし）、$S_1$（末尾が「1」）、$S_2$（末尾が「10」）。遷移／出力（Mealy、$x/z$）：$S_0$: $1/0\to S_1$, $0/0\to S_0$。$S_1$: $1/0\to S_1$, $0/0\to S_2$。$S_2$: $1/\mathbf{1}\to S_1$（101検出。末尾の1は次の系列の先頭として使えるので $S_1$ へ）, $0/0\to S_0$。3状態が最小。
(b) 遷移を符号で書き下すと（未使用 $(1,1)$ はドントケア）： $$D_1=\bar{x}\,y_0,\qquad D_0=x,\qquad z=x\,y_1.$$ （$x=1$ なら次状態は常に $S_1=(0,1)$、$x=0$ なら $S_1$ からのみ $S_2=(1,0)$ へ、が式に表れている。）
問題7 最尤推定・最小二乗・標本化 解答
(1-1) $\log L(\lambda)=\sum_{i}\log(\lambda e^{-\lambda x_i})=n\log\lambda-\lambda\sum_{i=1}^{n}x_i$。
(1-2) $\dfrac{d}{d\lambda}\log L=\dfrac{n}{\lambda}-\sum x_i=0$ より $\hat\lambda=\dfrac{n}{\sum x_i}=\dfrac{1}{\bar x}$。2階微分は $-\dfrac{n}{\lambda^2}<0$ で常に負なので、この停留点は極大（かつ大域最大）。
(2-1) $\dfrac{dE}{d\phi}=-2\sum x_i(y_i-\phi x_i)=0$ より $\hat\phi=\dfrac{\sum x_iy_i}{\sum x_i^2}$。（2階係数 $2\sum x_i^2>0$ で極小。）
(2-2) 尤度は $L(\phi)=\prod\dfrac{1}{\sqrt{2\pi\sigma^2}}\exp\!\left(-\dfrac{(y_i-\phi x_i)^2}{2\sigma^2}\right)$ で、 $$\log L(\phi)=\text{const}-\frac{1}{2\sigma^2}\sum_i (y_i-\phi x_i)^2.$$ $\phi$ に関する最大化は $\sum(y_i-\phi x_i)^2$ の最小化と同値なので、最尤推定＝最小二乗解。
(3-1) $f_s>2f_{\max}$（信号に含まれる最高周波数の2倍より大きいこと）。
(3-2) $f_1=|f_0-f_s|=|3-4|=1$ Hz。この現象はエイリアシング（折り返し）。（標本点上では $\sin(2\pi\cdot3t)$ と $-\sin(2\pi\cdot1\cdot t)$ が一致する。）
(3-3) 標本化の前段にアナログのローパスフィルタ（アンチエイリアシングフィルタ）を挿入し、遮断周波数を $f_s/2=2$ Hz 以下に設定して $f_s/2$ を超える成分をあらかじめ除去する。