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

想定シナリオ：証明・構成問題の重い年。問題4が2019型の回文＋反復補題フル、問題2が2024型の参照列構成、問題7が2020型のフーリエ級数＋級数値、問題6はカウンタの異常系（ロックアウト）まで踏み込む年、問題1は再帰・計算量の漸化式。

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

問題1【必須】アルゴリズムとプログラミング ― 再帰とメモ化

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

傾向準拠：再帰の呼び出し回数を漸化式で扱う形式。カウンタ変数＋出力記述＋改良という構成は2026年度大問1に準拠。メモ化・動的計画法の系譜は2015年度問題1（0-1ナップサック）に実績あり。

フィボナッチ数を $F_0 = 0,\ F_1 = 1,\ F_n = F_{n-1} + F_{n-2}\ (n \ge 2)$ で定める。図1はANSI Cで記述されたプログラムである。大域変数 count は関数の呼び出し回数を数えるカウンタである。図1のプログラムに関する以下の各問に答えよ。

 1: #include <stdio.h>
 2: int count = 0;
 3: int memo[50];
 4:
 5: int funcA(int n) {
 6:     count++;
 7:     if (n <= 1) return n;
 8:     return funcA(n - 1) + funcA(n - 2);
 9: }
10:
11: int funcB(int n) {
12:     count++;
13:     if (n <= 1) return n;
14:     if ([ (a) ]) return memo[n];
15:     return memo[n] = [ (b) ];
16: }
17:
18: int main(void) {
19:     for (int i = 0; i < 50; i++) memo[i] = -1;
20:     count = 0;
21:     printf("%d %d\n", funcA(5), count);
22:     count = 0;
23:     printf("%d %d\n", funcB(5), count);
24:     return 0;
25: }

図1　プログラム

(1) funcA(5) の呼び出しの木（どの引数の呼び出しがどの引数の呼び出しを生むか）を図示し、引数0〜5それぞれについて funcA が呼び出される回数を示せ。

(2) funcA(n) を1回呼び出したときの funcA の総呼び出し回数を $C(n)$ とする。$C(0) = C(1) = 1$、$C(n) = C(n-1) + C(n-2) + 1$（$n \ge 2$）が成り立つことを示し、これより $C(n) \ge F_n$ であること、したがって funcA の時間計算量が $n$ の多項式で抑えられないことを説明せよ（$F_n$ が $n$ に対して指数的に増加することは用いてよい）。

(3) 関数 funcB はメモ化（memoization）による改良版である。ただし、21行目の実行によって memo が書き換えられることはない。以下の各小問に答えよ。

(3-1) プログラムが正しく動作するように空欄 (a), (b) を埋めよ。

(3-2) 図1のプログラムが開始してから終了するまでに出力される内容をすべて記述せよ。

(3-3) $n \ge 2$ に対して funcB(n) の総呼び出し回数が $2n - 1$ となることを、「memo[k] が未計算の状態で funcB(k) が呼ばれるのは高々1回である」ことに基づいて説明せよ。

(4) 再帰を用いず、ループで $F_n$ を計算するCの関数を書け。ただし使用するint型の局所変数は3個以内（引数 $n$ とループ変数を除く）とし、時間計算量と空間計算量をオーダ表記で示せ。

問題2【必須】計算機システム ― ページ置換アルゴリズム（2024型）

配点：(1) 45, (2) 15, (3) 40, (4) 25

傾向準拠：LRU/FIFO/OPTの比較と「指定条件を満たす参照列を構成せよ」は2024年度大問2の実出題形式に準拠。クロックアルゴリズムは発展。

ページング方式の仮想記憶において、ページ枠（フレーム）数を3とする。最初、すべてのフレームは空である。

(1) ページ参照列 $$R = 2,\ 3,\ 2,\ 1,\ 5,\ 2,\ 4,\ 5,\ 3,\ 2,\ 5,\ 2$$ に対して、LRU・FIFO・OPT（最適置換）の各方式でページフォルトの発生回数を求めよ。各時刻のフレーム内容を表で示すこと。

(2) OPT方式がページを追い出す際の選択規則を1〜2行で述べよ。また、OPTが実際のシステムでそのまま実装できない理由を1行で述べよ。

(3) フレーム数3のとき、FIFOのページフォルト回数がLRUのページフォルト回数より少なくなるページ参照列を1つ構成せよ。構成した参照列に対する両方式のフレーム内容の推移とフォルト回数を示すこと。（ヒント：LRUが「最近使ったから残す」判断を裏切られるように、追い出した直後のページを再参照させる。）

(4) LRUが実装できない、あるいはコストが高い場合の近似としてクロックアルゴリズム（セカンドチャンス）が用いられる。参照ビットを用いたその動作を3〜4行で説明せよ。

問題4【選択】計算理論 ― 回文と反復補題（2019型）

配点：(1) 30, (2) 30, (3) 45, (4) 20

傾向準拠：回文のPDA＋反復補題フルセットは2019年度大問4の構成に準拠。(3)の{ww}の証明は本番の水準よりやや重い（場合分けの練習用）。

アルファベット $\Sigma = \{a, b\}$ とする。語 $w$ の反転を $w^R$ と表す。

(1) 回文全体の言語 $L_{\mathrm{pal}} = \{w \in \Sigma^* \mid w = w^R\}$（偶数長・奇数長の両方を含む）を最終状態受理で認識する非決定性PDAを構成せよ。スタックの使い方と非決定性をどこで用いるかの方針を2〜3行で述べたうえで、すべての遷移を列挙すること。

(2) $L_{\mathrm{pal}}$ が正則でないことを、正則言語の反復補題を用いて証明せよ。（ヒント：反復長を $p$ として $w = a^p b a^p$ を選ぶ。）

(3) 言語 $L = \{ww \mid w \in \Sigma^*\}$ が文脈自由でないことを、文脈自由言語の反復補題を用いて証明せよ。（ヒント：反復長を $p$ として $s = a^p b^p a^p b^p$ を選び、$vxy$ の位置で場合分けする。）

(4) 文脈自由言語は共通部分について閉じていない。このことを、$L_1 = \{a^n b^n c^m \mid n, m \ge 0\}$ と $L_2 = \{a^m b^n c^n \mid n, m \ge 0\}$ を用いて説明せよ。$L_1, L_2$ が文脈自由であること、および $L_1 \cap L_2$ が文脈自由でないこと（既知の結果を引用してよい）の両方に触れること。

問題6【選択】電子回路と論理設計 ― 大小比較器とジョンソンカウンタ

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

傾向準拠：大小比較器は2016年度問題6に同型の実出題あり。シフト型カウンタは2019年度大問6（アップダウンカウンタ）の系譜。ロックアウトの検討は発展。

(1) 2ビット符号なし2進数 $A = (a_1, a_0)$ と $B = (b_1, b_0)$ を比較し、$A = B$ のとき1となる出力 $E$ を考える。$E$ の論理式を、排他的論理和の否定（XNOR）を用いて示せ。また、その式が正しい理由を各ビットの一致条件から1〜2行で説明せよ。

(2) $A > B$ のとき1となる出力 $G$ の最簡積和形を、カルノー図を用いて求めよ（変数順は $a_1, a_0, b_1, b_0$。カルノー図も示すこと）。

(3) 3個のDフリップフロップ $(y_2, y_1, y_0)$ を用いた同期式カウンタを、次の接続で構成する： $$D_2 = \overline{y_0}, \qquad D_1 = y_2, \qquad D_0 = y_1$$

(3-1) 初期状態 $(y_2, y_1, y_0) = (0, 0, 0)$ から始めたとき、状態がどのように遷移するかを1周期分すべて列挙せよ。この形式のカウンタの名称を答えよ。

(3-2) このカウンタには(3-1)の巡回に含まれない状態が2つ存在する。それらの状態を挙げ、そこから始めた場合の遷移を調べよ。その結果どのような問題（名称も答えること）が生じるかを述べ、対策を1つ具体的に示せ。

(4) (3)のカウンタは、バイナリカウンタと比べて「状態の遷移ごとに変化するフリップフロップが常に1個だけ」という性質を持つ。この性質が回路設計上どのような利点をもたらすか、デコード時のグリッチ（ひげ状のノイズ）に着目して2〜3行で説明せよ。

問題7【選択】数学解析と信号処理 ― フーリエ級数とパーセバルの等式（2020型）

配点：(1) 40, (2) 20, (3) 40, (4) 25

傾向準拠：2020年度大問7（x²のフーリエ級数から級数値を求める）の型に準拠。フーリエ級数は2011・2016・2020年度のほぼ5年周期で周期超過。パーセバルの適用は発展。

図1に示す周期 $2\pi$ の関数 $f(x) = |x|$（$-\pi \le x \le \pi$）、$f(x) = f(x + 2\pi)$ について、以下の各問に答えよ。ただし導出の過程も示すこと。

(1) $f(x)$ のフーリエ級数展開を求めよ。$f(x)$ が偶関数であることを利用してよい。（参考：結果は $f(x) = \dfrac{\pi}{2} - \dfrac{4}{\pi}\displaystyle\sum_{k=0}^{\infty} \frac{\cos((2k+1)x)}{(2k+1)^2}$ の形になる。この形を導出せよ。）

(2) (1)の結果に $x = 0$ を代入し、級数 $\displaystyle\sum_{k=0}^{\infty} \frac{1}{(2k+1)^2}$ の値を求めよ。

(3) パーセバルの等式 $$\frac{1}{\pi}\int_{-\pi}^{\pi} f(x)^2\, dx = \frac{a_0^2}{2} + \sum_{n=1}^{\infty} (a_n^2 + b_n^2)$$ を(1)の結果に適用し、級数 $\displaystyle\sum_{k=0}^{\infty} \frac{1}{(2k+1)^4}$ の値を求めよ。