第4回　解答（理論・変換系の重量級年）

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

問題1　基数ソート　解答

(1)
1の位：720, 355, 436, 457, 657, 329, 839
10の位：720, 329, 436, 839, 355, 457, 657
100の位：329, 355, 436, 457, 657, 720, 839

(2) (a) C[v] += C[v-1];（累積和：C[v] が「着目桁 ≤ v の個数」になる）　(b) C[digit(A[i], p)]（11行目で1減じた後の値が格納位置）　(c) p *= 10;。出力：

329 355 436 457 657 720 839 

(3) 累積和後の $C[d]$ は桁値 $d$ のグループの「最後の要素が入る位置＋1」を指す。後ろから走査すると、入力で後方にあった同値要素ほど後ろの位置に置かれるため、同じ桁値の要素の相対順序が保存される（＝安定）。前から走査すると順序が反転する。

(4) 例：$\{21, 25\}$。1の位で整列すると $21, 25$。次に10の位（どちらも2で同値）を不安定なソートで整列すると $25, 21$ になり得る。前パスの結果（1の位の順序）が同値グループ内で壊れ、最終結果が誤る。

(5) 1パスはカウント $O(n)$＋累積和 $O(k)$＋配置 $O(n)$ で $O(n+k)$。これを $d$ 回繰り返すので $O(d(n+k))$。

(6) $\Omega(n\log n)$ の下界は「要素同士の比較だけで順序を決める」計算モデル（決定木の葉が $n!$ 通り必要）に対するもの。基数ソートは比較を行わず、桁の値そのものを配列の添字として使うため、このモデルの前提の外にあり、下界の制約を受けない。

問題2　アドレス変換・TLB・EAT　解答

(1) オフセット12ビット（4 KiB）、仮想ページ番号 $32-12=20$ ビット、物理フレーム番号 $30-12=18$ ビット（1 GiB $=2^{30}$）。

(2-1) $2^{20}$ エントリ × 4 B ＝ 4 MiB／プロセス。

(2-2) 外側テーブルは $2^{10}=1024$ エントリ。2段方式では、実際に使用している仮想アドレス領域に対応する内側テーブル（各1024エントリ）だけを割り当てればよく、未使用領域の分のテーブルを一切持たずに済むため、疎な使い方をするプロセスでメモリを大きく節約できる。

(3) $\mathrm{EAT}=0.98\times(20+100)+0.02\times(20+100+100)=0.98\times120+0.02\times220=117.6+4.4=\textbf{122 ns}$。

(4) $10\ \mathrm{ms}=10^7\ \mathrm{ns}$ として $$\mathrm{EAT}=(1-p)\times100+p\times(10^7+100)\approx 100+p\times10^7\ \mathrm{[ns]}.$$ $100+10^7p\le200$ より $p\le\textbf{1.0}\times\textbf{10}^{-\textbf{5}}$。ページフォルトは10万アクセスに1回以下という極めて低い頻度に抑えなければ、平均アクセス時間はすぐに悪化する。

問題4　PDA理論　解答

(1) スタック記号 $\Gamma=\{Z,a,b\}$、受理状態 $q_2$。$s$ は任意のスタックトップ（$Z,a,b$）：

δ(q0, a, s) = (q0, as)      δ(q0, b, s) = (q0, bs)      ← 前半を積む
δ(q0, c, s) = (q1, s)                                   ← マーカーで照合へ切替
δ(q1, a, a) = (q1, ε)       δ(q1, b, b) = (q1, ε)       ← 逆順に照合
δ(q1, ε, Z) = (q2, Z)                                   ← 全部消えたら受理

各（状態, 入力, トップ）で遷移は高々1つ、$q_1$ でε遷移を持つのはトップが $Z$ のときだけで入力遷移（トップ $a,b$）と競合しない → 決定性。

(2) $L_1$ ではマーカー $c$ を読んだ瞬間に「積み込み → 照合」の切替点が確定する。$L_2$ には切替点（$w$ と $w^R$ の境界＝中央）を示す情報が入力に存在せず、機械は中央の位置を推測しなければならない。決定性PDAは推測ができないため、非決定性が本質的に必要になる。

(3) 新しい底記号 $Z_0$、新開始状態 $q_0'$、新受理状態 $q_f$ を導入する。まず $\delta(q_0',\varepsilon,Z_0)=(q_0,\ ZZ_0)$ で元の底記号 $Z$ を積んでから $M$ を起動する。$M$ がスタックを空にすると $Z_0$ が露出するので、$M$ のすべての状態 $q$ に $\delta(q,\varepsilon,Z_0)=(q_f,Z_0)$ を追加する。$q_f$ を唯一の受理状態とすれば、「$M$ が空スタックで受理」⇔「$M'$ が $q_f$ に到達」となる。

(4) 証明：$u\in L$ かつ $uv\in L$（$v\ne\varepsilon$）となる語が存在すると仮定する。決定性より、入力の各時点での動作は一意なので、$uv$ を読む計算の最初の $|u|$ 文字分は $u$ を読む計算と完全に一致する。$u\in L$ は空スタック受理なので、$u$ を読み終えた時点でスタックは空である。しかし遷移関数はスタックトップの記号を取り除くことを要求するため、スタックが空の状態ではいかなる遷移（ε遷移を含む）も実行できない。したがって残りの $v$ を読み進めることができず、$uv$ は受理されない。仮定に矛盾。ゆえに $L$ は prefix-free である。∎

問題6　スタックの専用ハードウェア　解答

(1)

（popはSPを戻すだけで、メモリの内容は消えない。次のr_datにはMem[SP]＝トップが現れる。）

(2) $E=\bar{s_3}\,\bar{s_2}\,\bar{s_1}\,\bar{s_0}$（SP=0000）、$F=s_3\,\bar{s_2}\,\bar{s_1}\,\bar{s_0}$（SP=1000）。

(3) 8語すべて使用中のときSPは8（=1000）になる。3ビットだと 8 が折り返して 000 となり、空（SP=0）と満杯が同じ符号になって $E$ と $F$ を区別できない。0〜8の9通りを表すために4ビット目が必要。

(4) スタック（LIFO：後入れ先出し）。2026年度の「カウンタ2個＋メモリ」はFIFOキューで、格納した順（先入れ先出し）に取り出す。本問は最後に格納したものから取り出す点が異なる。

(5) 満杯時のpushと空時のpopを無効化する： $$\mathrm{up}=\mathrm{w\_en}=\mathrm{req\_push}\cdot\bar{F},\qquad \mathrm{down}=\mathrm{req\_pop}\cdot\bar{E}.$$ （同時要求を仕様上pushを優先するなら $\mathrm{down}=\mathrm{req\_pop}\cdot\bar{E}\cdot\overline{\mathrm{req\_push}\cdot\bar F}$ とする。）

問題7　留数・複素積分＋ラプラス　解答

(1) $z^2+1=(z-i)(z+i)$ より特異点は $z=\pm i$（ともに1位の極）。 $$\mathrm{Res}_{z=i}=\lim_{z\to i}\frac{z-i}{z^2+1}=\frac{1}{2i},\qquad \mathrm{Res}_{z=-i}=\frac{1}{-2i}.$$

(2-1) $|z-i|=1$ の内部にある極は $z=i$ のみ：$\displaystyle\oint=2\pi i\cdot\frac{1}{2i}=\boldsymbol{\pi}$。

(2-2) $|z|=2$ の内部には両方の極：$\displaystyle\oint=2\pi i\left(\frac{1}{2i}+\frac{1}{-2i}\right)=\boldsymbol{0}$。

(3) $\dfrac{1}{(s+1)(s^2+4)}=\dfrac{A}{s+1}+\dfrac{Bs+C}{s^2+4}$ とおく。$A=\dfrac{1}{(-1)^2+4}=\dfrac15$、係数比較で $B=-\dfrac15$、$C=\dfrac15$。よって $$f(t)=\frac15 e^{-t}-\frac15\cos 2t+\frac{1}{10}\sin 2t\quad(t\ge0).$$

(4) 実軸上 $[-R,R]$ と上半平面の半円 $C_R$ からなる閉路に留数定理を適用。内部の極は $z=i$ のみで閉路積分 $=2\pi i\cdot\dfrac{1}{2i}=\pi$。半円上では $|z^2+1|\ge R^2-1$ より $$\left|\int_{C_R}\frac{dz}{z^2+1}\right|\le\frac{\pi R}{R^2-1}\xrightarrow{R\to\infty}0.$$ よって $\displaystyle\int_{-\infty}^{\infty}\frac{dx}{x^2+1}=\boldsymbol{\pi}$。

← 第4回の問題に戻る　｜　第5回の解答 →