第1回　解答（本命シナリオ）

対応する問題：第1回 予想問題。記述式の小問（「〜行で説明せよ」）は解答例であり、同じ内容が伝わる表現なら形は問わない。誤りを見つけたら作成者（Claude）に報告してほしい。

問題1　クイックソートと二分探索　解答

(1-1) $\mathrm{right} - \mathrm{left}$ 回。（ループ変数 $j$ が left から right$-1$ まで動く。）

(1-2) pivot $=A[5]=2$。$j=3$ のとき $A[3]=1<2$ で swap が起こり、ループ後に $A[1]$ と $A[5]$ を交換。 直後の配列は {1, 2, 8, 5, 7, 3}、返り値は 1。

(2) 昇順済み配列では pivot（右端）が常に区間の最大値なので、partition は区間サイズ $m$ に対して $m-1$ 回比較し、右側は空・左側はサイズ $m-1$ で再帰する。よって $$\mathrm{countA} = \sum_{m=2}^{n}(m-1) = \sum_{k=1}^{n-1}k = \frac{n(n-1)}{2}.$$

(3-1) 最悪 $O(N^2)$。

(2) の出力トレース　partition(A,0,5) の続き：funcA(2,5) で pivot=3、比較3回、配列は {1,2,3,5,7,8}・返り値2。funcA(3,5) で pivot=8、比較2回。funcA(3,4) で pivot=7、比較1回。合計 $\mathrm{countA}=5+3+2+1=11$。funcB(A,6,7) は mid=2（$A[2]=3<7$）→ mid=4（$A[4]=7$ 一致）で返り値4、$\mathrm{countB}=2$。プログラム全体の出力：

1 2 3 5 7 8 
4
11 2

(3-1) $\lfloor \log_2 n \rfloor + 1$ 回。（1回の比較ごとに探索範囲が半分以下になる。）

(3-2) $O(\log N)$。

(4) 例：8行目で pivot を区間内から一様ランダムに選んだ要素にする（選んだ要素を $A[\mathrm{right}]$ と交換してから現行の処理を行う）。分割の偏りが入力の並びではなく乱数で決まるため、どの入力に対しても偏った分割が連続する確率は指数的に小さく、期待時間計算量は $O(N\log N)$ になる。（三値中央値法でもよい。）

問題2　キャッシュ＋仮想記憶　解答

(1-1) オフセット4ビット（ブロック16B）、インデックス6ビット（$1\,\mathrm{KiB}/16\,\mathrm{B}=64$行）、タグ6ビット（$16-6-4$）。

(1-2) インデックス $=(\mathrm{addr}\gg4)\ \&\ \mathtt{0x3F}$、タグ $=\mathrm{addr}\gg10$。6アクセスすべてインデックス4に写像され、タグは順に 0, 0, 1, 0, 2, 1。
結果：ミス → ヒット → ミス → ミス → ミス → ミス（同一ラインの奪い合い＝コンフリクトミス）。

(1-3) 2ウェイではセット数32、インデックス5ビット、タグ7ビット。全アクセスがセット4、タグは 0,0,2,0,4,2。LRUで追うと：0ミス → 0ヒット → 2ミス（{0,2}）→ 0ヒット → 4ミス（LRUの2を追い出し{0,4}）→ 2ミス（0を追い出し{4,2}）。
結果：ミス → ヒット → ミス → ヒット → ミス → ミス（ヒットが1回増える）。

(2-1) $\mathtt{0x2C8F}=0010\,1100\,1000\,1111_2$。オフセット＝下位10ビット $=\mathtt{0x28F}$、ページ番号＝上位6ビット $=\mathtt{0x0B}$。

(2-2) $(\mathtt{0x05}\ll 10)+\mathtt{0x28F}=\mathtt{0x1400}+\mathtt{0x28F}=\mathtt{0x168F}$。

(2-3) フレーム3：フォルトは 1,2,3,4,1,2,5,3,4 の9回。フレーム4：フォルトは 1,2,3,4,5,1,2,3,4,5 の10回。フレームを増やしたのにフォルトが増える現象＝Beladyの異常。（フレーム内容の推移表は本文の順に1行ずつ書けばよい。フレーム4では後半、直後に使うページを毎回追い出す悪循環になる。）

(2-4) LRUで保持されるのは「直近に使われた $k$ ページ」であり、これは「直近に使われた $k+1$ ページ」の部分集合。よって任意の時点でフレーム $k$ の内容 ⊆ フレーム $k+1$ の内容が成り立ち（スタック性質）、フレームを増やしてフォルトが増えることはない。

問題4　CFG/PDA＋反復補題　解答

(1-1) 状態数 6。状態を $(i,j)$（$i$：0の個数の偶奇、$j$：1の個数 mod 3）とし、入力0で $i$ を反転、入力1で $j\to j+1 \bmod 3$。開始・受理はともに $(0,0)$。6状態はどの2つも区別可能（対応する余りの組が異なる語で分離できる）なので最小。

(1-2) 到達可能な部分集合は $\{p\},\{p,q\},\{p,q,r\}$ の3つ。遷移：$\{p\}\xrightarrow{0}\{p,q\}$、$\{p\}\xrightarrow{1}\{p\}$、$\{p,q\}\xrightarrow{0}\{p,q,r\}$、$\{p,q\}\xrightarrow{1}\{p\}$、$\{p,q,r\}\xrightarrow{0}\{p,q,r\}$、$\{p,q,r\}\xrightarrow{1}\{p\}$。受理は $r$ を含む $\{p,q,r\}$。言語：00で終わる語全体。

(2-1) 例：$S \to aSb \mid Sb \mid b$。$abb$ の最左導出：$S \Rightarrow aSb \Rightarrow abb$。（$a$ を1つ足すとき $b$ も1つ足し、$Sb$ で $b$ だけを増やせるので常に $i

(2-2) 方針：$a$ の個数だけ記号 $X$ を積み、$b$ で1個ずつ消す。$X$ が尽きて（$i$ 個の $b$ を消費して）からもう1個以上 $b$ を読んだら受理状態へ。遷移（$Z$：底記号、受理状態 $q_2$）：

δ(q0, a, Z) ∋ (q0, XZ)      δ(q0, a, X) ∋ (q0, XX)
δ(q0, b, X) ∋ (q1, ε)       δ(q0, b, Z) ∋ (q2, Z)   ← i = 0 の場合
δ(q1, b, X) ∋ (q1, ε)       δ(q1, b, Z) ∋ (q2, Z)   ← ここで j > i が確定
δ(q2, b, Z) ∋ (q2, Z)

(3-1) 反復長を $p$ とし $w=a^{p+1}b^{p}\in L_3$ を選ぶ。$w=xyz$、$|xy|\le p$ より $y=a^k$（$k\ge1$）。$i=0$ とすると $xz=a^{p+1-k}b^{p}$ で、$a$ の個数 $p+1-k\le p$ となり「$n>m$」が破れる。反復補題に矛盾するので $L_3$ は正則でない。

(3-2) 反復長を $p$ とし $s=a^pb^pc^p$ を選ぶ。$s=uvxyz$、$|vxy|\le p$、$|vy|\ge1$。$|vxy|\le p$ より $vxy$ は高々2種類の文字にしかまたがらない。
（i）$vxy$ に $c$ が含まれない場合：$uv^2xy^2z$ では $a$ または $b$ の個数だけが増え $c$ は $p$ 個のまま → 3文字の個数が一致せず $L_4$ に属さない。
（ii）$vxy$ に $a$ が含まれない場合：同様に $a$ が $p$ 個のまま取り残される。
いずれも矛盾するので $L_4$ は文脈自由でない。

問題6　乗算器のデータパス＋制御回路　解答

(1)

$P=00001111_2=15=5\times3$。

(2) 第 $i$ サイクル開始時点で A は被乗数の $2^i$ 倍、B の最下位ビットは $b_i$。$b_i=1$ のときだけ $A\cdot 2^i$ が P に加算されるので、4サイクル後に $P=\sum_{i=0}^{3}b_i\,(A\cdot2^i)=A\sum b_i2^i=A\times B$。

(3) IDLE $\xrightarrow{\text{start}=1}$ S0 → S1 → S2 → S3 → DONE → IDLE（start=0 なら IDLE 自己ループ）。出力（Moore）：IDLE では load=1, clear=1（開始時に取り込み・初期化）、S0〜S3 では en_shift=1、DONE では done=1、他はすべて0。

(4) 遷移：000→(start?001:000), 001→010, 010→011, 011→100, 100→101, 101→000。ドントケア 110, 111 を活用して：

（検算：各状態を代入して遷移表と一致することを確認できる。）

(5) データパスに「Bの全4ビットのNOR」＝$z$（B=0検出信号）を追加して制御回路へ入力する。制御回路は計算状態 S0〜S3 において $z=1$ なら直ちに DONE へ遷移する。B の残りビットがすべて0なら以後 en_add が立つことはなく P は変化しないので、結果は変わらずサイクル数だけ削減できる。

問題7　ラプラス・z変換・フーリエ級数　解答

(1-1) $\dfrac{1}{s(s+2)}=\dfrac{1}{2}\left(\dfrac{1}{s}-\dfrac{1}{s+2}\right)$ より $f(t)=\dfrac{1-e^{-2t}}{2}$。

(1-2) 変換して $sY+3Y=\dfrac{1}{s+1}$、$Y=\dfrac{1}{(s+1)(s+3)}=\dfrac{1}{2}\left(\dfrac{1}{s+1}-\dfrac{1}{s+3}\right)$。よって $y(t)=\dfrac{e^{-t}-e^{-3t}}{2}$。

(2-1) $Y=X+az^{-1}Y$ より $H(z)=\dfrac{1}{1-az^{-1}}=\dfrac{z}{z-a}$。

(2-2) $h[n]=a^n u[n]$。

(2-3) 極は $z=a$。因果システムのBIBO安定 ⇔ 極が単位円の内側 ⇔ $|a|<1$。このとき $\sum_{n\ge0}|h[n]|=\sum|a|^n=\dfrac{1}{1-|a|}<\infty$。

(2-4) $|H(e^{j\omega})|^2=\dfrac{1}{|1-ae^{-j\omega}|^2}=\dfrac{1}{1-2a\cos\omega+a^2}$。よって $$|H(e^{j\omega})|=\frac{1}{\sqrt{1-2a\cos\omega+a^2}},\quad |H(e^{j0})|=\frac{1}{1-a},\quad |H(e^{j\pi})|=\frac{1}{1+a}.$$ $0ローパスフィルタ。

(3-1) $f$ は奇関数なので $a_n=0$。$b_n=\dfrac{2}{\pi}\displaystyle\int_0^\pi \sin nx\,dx=\dfrac{2}{n\pi}(1-\cos n\pi)$。$n$ 偶数で0、奇数で $\dfrac{4}{n\pi}$。 $$f(x)=\frac{4}{\pi}\sum_{k=0}^{\infty}\frac{\sin\bigl((2k+1)x\bigr)}{2k+1}.$$

(3-2) $x=\pi/2$ で $f=1$、$\sin\bigl((2k+1)\pi/2\bigr)=(-1)^k$ なので $1=\dfrac{4}{\pi}\sum\dfrac{(-1)^k}{2k+1}$、よって $\displaystyle\sum_{k=0}^{\infty}\frac{(-1)^k}{2k+1}=\frac{\pi}{4}$。

← 第1回の問題に戻る　｜　第2回の解答 →