第5回　解答（証明・構成問題の重い年）

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

問題1　再帰とメモ化　解答

(1) 呼び出しの木：fib(5) → fib(4), fib(3)；fib(4) → fib(3), fib(2)；……と展開すると、各引数の呼び出し回数は $$n=5:1,\quad 4:1,\quad 3:2,\quad 2:3,\quad 1:5,\quad 0:3$$ で合計 count = 15。

(2) funcA(n) は自分自身の1回に加えて funcA(n−1) と funcA(n−2) の呼び出し全体を含むので $C(n)=C(n-1)+C(n-2)+1$。$C(0)=C(1)=1$。帰納法で $C(n)\ge F_n$：基底 $C(0)=1\ge0=F_0$、$C(1)=1\ge1=F_1$。帰納段 $C(n)=C(n-1)+C(n-2)+1\ge F_{n-1}+F_{n-2}=F_n$。$F_n$ は $n$ に対して指数的に増加する（$F_n\sim\varphi^n/\sqrt5$）ので、呼び出し回数すなわち時間計算量は $n$ のどの多項式でも抑えられない。

(3-1) (a) memo[n] != -1　(b) funcB(n - 1) + funcB(n - 2)。

(3-2) funcA(5)=5、count=15。funcB(5)=5、count=9。出力：

5 15
5 9

(3-3) 各 $k\ (2\le k\le n)$ について、memo[k] が未計算の状態で funcB(k) が呼ばれるのは高々1回（1度計算すれば以後はmemoが返る）。未計算の呼び出しは $k=2,\dots,n$ の $n-1$ 回あり、それぞれがちょうど2回の再帰呼び出し（子）を発生させる。呼び出し総数＝最初の1回＋子の総数 $=1+2(n-1)=2n-1$。（$n=5$ で $9$、(3-2)と一致。）

(4) 例：

int fib(int n) {
    int a = 0, b = 1, t;
    for (int i = 0; i < n; i++) { t = a + b; a = b; b = t; }
    return a;
}

時間計算量 $O(n)$、空間計算量 $O(1)$。

問題2　ページ置換アルゴリズム　解答

(1) 参照列 $2,3,2,1,5,2,4,5,3,2,5,2$、フレーム3。

フォルト回数：LRU＝7、FIFO＝9、OPT＝6。（括弧は追い出すページ。OPTの5参照目：1は以後参照されないので1を追い出す。7参照目：2,3,5のうち次の参照が最も遠い2を追い出す。）

(2) OPT：今後最も長く参照されない（または二度と参照されない）ページを追い出す。将来の参照列を知る必要があるため、実システムではそのまま実装できない（性能比較の基準として使う）。

(3) 構成例：$2,1,2,3,4,1$（フレーム3）。
LRU：2F, 1F, 2h, 3F, 4で最も昔に使った1を追い出しF、直後の1でF → 5フォルト。
FIFO：2F, 1F, 2h, 3F, 4で最古の2を追い出しF、1はヒット → 4フォルト。
LRUは「2を最近使った」ことを尊重して1を捨てるが、直後に1が来るため裏目に出る。

(4) 各フレームに参照ビットを持たせる。ページが参照されるとハードウェアがビットを1にする。置換時は、針（ポインタ）がフレームを循環的に走査し、参照ビットが1のページはビットを0に戻して見逃し（セカンドチャンス）、0のページを見つけたらそれを追い出して針を進める。「最近使われたページを避ける」というLRUの趣旨を、ビット1個と巡回走査で近似する。

問題4　回文と反復補題　解答

(1) 方針：前半を積み、中央の位置を非決定的に推測して照合に切り替える。偶数長なら文字を消費せずに切替、奇数長なら中央の1文字を読み捨てて切替。$s$ は任意のトップ：

δ(q0, a, s) ∋ (q0, as)      δ(q0, b, s) ∋ (q0, bs)      ← 積む
δ(q0, ε, s) ∋ (q1, s)                                   ← 偶数長：ここが中央と推測
δ(q0, a, s) ∋ (q1, s)       δ(q0, b, s) ∋ (q1, s)       ← 奇数長：中央文字を読み捨て
δ(q1, a, a) ∋ (q1, ε)       δ(q1, b, b) ∋ (q1, ε)       ← 照合
δ(q1, ε, Z) ∋ (q2, Z)        （q2：受理状態）

(2) 反復長 $p$。$w=a^pba^p\in L_{\mathrm{pal}}$ を選ぶ。$|xy|\le p$ より $y=a^k\ (k\ge1)$ は前半の $a$ 列のみからなる。$i=2$ とすると $xy^2z=a^{p+k}ba^p$ で、$b$ の前後の $a$ の個数が異なるため回文でない。矛盾。

(3) 反復長 $p$。$s=a^pb^pa^pb^p\in L$。$s=uvxyz$、$|vxy|\le p$、$|vy|\ge1$。まず $|vy|$ が奇数なら $uv^0xy^0z$ の長さが奇数となり $ww$ 形でないので矛盾。以下 $uv^0xy^0z=s'$（長さ $4p-|vy|$、偶数）を考える。$|vxy|\le p$ より $vxy$ は $s$ の隣接する高々2ブロックの範囲に収まる：
（i）$vxy$ が前半 $a^pb^p$ の範囲内：$s'=a^{p-\alpha}b^{p-\beta}a^pb^p$（$\alpha+\beta=|vy|\ge1$）。$s'=ww$ とすると $|w|=2p-\tfrac{\alpha+\beta}{2}<2p$ なので、$s'$ の後半 $w$ は末尾側の $a^pb^p$ を内部に含む位置から始まり、後半は $a$ をちょうど $p$ 個含む。一方 $s'$ の中央は前半側のブロックに食い込み、前半 $w$ に含まれる $a$ の個数は $p-\alpha$ 個と後半と一致し得ない（丁寧には：前半 $w=a^{p-\alpha}b^{p-\beta}\cdots$、後半 $w=\cdots a^pb^p$ の形の比較で $a$ ブロック長が食い違う）。矛盾。
（ii）$vxy$ が後半 $a^pb^p$ の範囲内：（i）と対称に矛盾。
（iii）$vxy$ が中央の $b^pa^p$ 境界をまたぐ（位置 $p+1$〜$3p$）：$s'=a^pb^{p-\beta}a^{p-\alpha}b^p$。$s'=ww$ なら $|w|=2p-\tfrac{\alpha+\beta}{2}$ で、前半 $w=a^pb^{p-\frac{\alpha+\beta}{2}}$、後半 $w=a^{p-\frac{\alpha+\beta}{2}}b^p$ の形になる。両者が一致するには $a$ の個数から $\alpha+\beta=0$ が必要で、$|vy|\ge1$ に矛盾。
すべての場合で矛盾するので $L=\{ww\}$ は文脈自由でない。

(4) $L_1=\{a^nb^nc^m\}$ は $S\to XY,\ X\to aXb\mid\varepsilon,\ Y\to cY\mid\varepsilon$ で生成できるので文脈自由。$L_2=\{a^mb^nc^n\}$ も対称に文脈自由。ところが $$L_1\cap L_2=\{a^nb^nc^n\mid n\ge0\}$$ であり、これは文脈自由でない（第1回 問題4(3-2)の通り）。文脈自由言語の共通部分が文脈自由でない例が存在するので、CFLは共通部分について閉じていない。

問題6　大小比較器とジョンソンカウンタ　解答

(1) $E=(a_1\odot b_1)\,(a_0\odot b_0)$（$\odot$：XNOR）。$A=B$ ⇔ 上位ビット同士・下位ビット同士がともに一致 ⇔ 各桁のXNORがともに1、の連言そのもの。

(2) $G=1$ となる $(A,B)$ の組は $A>B$ の6通り（minterm：$a_1a_0b_1b_0=0100,1000,1001,1100,1101,1110$）。K-mapでまとめると $$G=a_1\bar{b_1}+a_0\bar{b_1}\bar{b_0}+a_1a_0\bar{b_0}.$$ （意味：上位で勝つ／上位が同じ0で下位で勝つ／上位が同じ1で下位で勝つ、に対応。）

(3-1) $000\to100\to110\to111\to011\to001\to000$（6状態で1周期）。ジョンソンカウンタ（ねじれリングカウンタ）。

(3-2) 未使用状態は $010$ と $101$。$010\to101\to010\to\cdots$ と2状態間を永久に往復し、正規の6状態巡回に戻れない。この問題をロックアウトと呼ぶ。対策例：電源投入時にリセット信号で $000$ に初期化する（または未使用状態を検出して次状態を強制的に正規系列へ入れる自己修正論理を追加する）。

(4) 遷移ごとに変化するFFが常に1個だけなので、状態をデコードする出力に複数ビットが同時に切り替わることによる過渡的なひげ（グリッチ）が生じない。また任意の状態を2入力ANDだけでデコードできるという利点もある。

問題7　フーリエ級数とパーセバルの等式　解答

(1) 偶関数なので $b_n=0$。 $$a_0=\frac{1}{\pi}\int_{-\pi}^{\pi}|x|\,dx=\frac{2}{\pi}\cdot\frac{\pi^2}{2}=\pi.$$ $$a_n=\frac{2}{\pi}\int_0^\pi x\cos nx\,dx=\frac{2}{\pi}\left[\frac{x\sin nx}{n}+\frac{\cos nx}{n^2}\right]_0^\pi=\frac{2}{\pi n^2}(\cos n\pi-1).$$ $n$ 偶数で0、奇数で $-\dfrac{4}{\pi n^2}$。よって $$f(x)=\frac{\pi}{2}-\frac{4}{\pi}\sum_{k=0}^{\infty}\frac{\cos\bigl((2k+1)x\bigr)}{(2k+1)^2}.$$

(2) $x=0$：$0=\dfrac{\pi}{2}-\dfrac{4}{\pi}\sum\dfrac{1}{(2k+1)^2}$ より $$\sum_{k=0}^{\infty}\frac{1}{(2k+1)^2}=\frac{\pi^2}{8}.$$

(3) 左辺：$\dfrac{1}{\pi}\displaystyle\int_{-\pi}^{\pi}x^2dx=\dfrac{2\pi^2}{3}$。右辺：$\dfrac{a_0^2}{2}+\sum a_n^2=\dfrac{\pi^2}{2}+\dfrac{16}{\pi^2}\sum\dfrac{1}{(2k+1)^4}$。等置して $$\frac{16}{\pi^2}\sum\frac{1}{(2k+1)^4}=\frac{2\pi^2}{3}-\frac{\pi^2}{2}=\frac{\pi^2}{6} \;\Longrightarrow\; \sum_{k=0}^{\infty}\frac{1}{(2k+1)^4}=\frac{\pi^4}{96}.$$

(4) $f(x)=|x|$ は周期的に接続しても連続（区分的に滑らかで不連続点がない）。ギブス現象は不連続点における部分和のオーバーシュートなので、不連続点を持たない本関数では生じない（級数は一様収束する）。

← 第5回の問題に戻る