付録C: 練習問題解答

本書の各章末問題から代表的な練習問題を選び、詳細な解答と解説を示します。

注: 本付録は代表解答集です。第1〜12章の章末問題を網羅するものではなく、採録した問題について解答を収録しています。

付録内の各「練習問題X.Y」には、対応する章末問題番号・該当項目・解答種別を冒頭に明記しています。
章末問題の特定小問のみを採録した場合は、「元問題の項目」で対応範囲を明示しています。
「探究課題」は唯一の正解がないため、調査の観点・比較軸・アウトプット例を「回答」として提示します。
「実装課題」は参照実装/テストを併記する場合があります（必要要件は各節に記載）。

この付録の使い方

先に自力で考える: 章末問題を一通り考えてから、詰まった箇所だけを本付録で確認してください。
復習導線と併用する: 章全体の回収は各章末の「参考文献と次の一歩」や付録F: 学習進捗チェックリストと併用すると効果的です。
探究課題の読み方: ここでは唯一の正解ではなく、調査の観点・比較軸・アウトプット例を示します。自分なりの仮説や比較軸を作った後に参照してください。
実装課題の読み方: 先に自分で設計・実装し、その後に参照実装やテスト観点との差分確認に使ってください。

章別クイックナビ

解法パターン索引

「どの章の問題だったか」は曖昧でも、「どの型で解く問題か」を覚えていることがあります。そういうときは、まず次の解法パターンから近いものを開いてください。

証明・反証の型

帰納法で式を閉じる: 練習問題1.3 数学的帰納法
反例を1つ作って限界を示す: 練習問題7.4 ヒープソートの非安定性, 練習問題8.2 Dijkstra が負辺で失敗する例
ループ不変条件で正しさを示す: 練習問題9.3 Hoare 三つ組, 練習問題12.4 ベーカリーアルゴリズム

計算理論・還元の型

オートマトンや文法を構成する: 練習問題2.1 チューリング機械の設計, 練習問題3.1 正規言語の証明, 練習問題3.2 文脈自由文法
ポンピング補題で非文脈自由性を示す: 練習問題3.3 ポンピング補題
Myhill–Nerode で状態数や非正規性を示す: 練習問題3.4 Myhill–Nerode による最小DFA, 練習問題3.5 Myhill–Nerode による非正規性
Rice の定理や還元テンプレで不可判定性を運ぶ: 練習問題4.2 Riceの定理, 練習問題4.7 還元テンプレ（多対一）適用の概略, 練習問題5.2 NP完全性の証明, 練習問題5.3 3-SAT から VERTEX-COVER へのサイズ管理, 練習問題5.5 CLIQUE から VERTEX-COVER へのサイズ変換

解析・設計の型

漸化式を解く: 練習問題6.1 Master定理, 練習問題6.3 置換法（不均等分割）
動的計画法の状態設計に戻る: 練習問題6.2 動的計画法の設計, 練習問題8.1 DAG最長パス・2-SAT・トポロジカルソート
償却解析やポテンシャル法を見直す: 練習問題7.6 フィボナッチヒープ, 練習問題7.14 Union-Find

応用理論でよく使う型

エントロピー・相互情報量を計算する: 練習問題10.1 エントロピー計算, 練習問題10.2 Markov 連鎖と相互情報量, 練習問題10.4 Huffman 符号
暗号の破れ方と対策を整理する: 練習問題11.1 古典暗号の安全性, 練習問題11.2 RSA で e=3 を使う場合の脆弱性, 練習問題11.3 ElGamal の乱数再利用
並行性の落とし穴と同期原語を整理する: 練習問題12.5 Lamport 時計とベクトル時計, 練習問題12.6 コンセンサス数, 練習問題12.7 Michael-Scott ロックフリーキュー, 練習問題12.8 弱メモリモデル

第1章: 数学的基礎

練習問題1.1 集合演算

元問題: 第1章問題1（基礎）

解答種別: 詳細解答

問題: 集合 A = {1, 2, 3, 4} に対して、以下を求めよ。 (a) \(\mathcal{P}(A)\) の要素数 (b) \(A \times A\) の要素数 (c) A 上の反射的関係の個数

解答: (a) \(\lvert \mathcal{P}(A) \rvert = 2^{\lvert A\rvert} = 2^4 = 16\)。

(b) \(\lvert A \times A \rvert = \lvert A \rvert^2 = 4^2 = 16\)。

(c) A 上の関係は \(A \times A\) の部分集合なので、候補となる順序対は 16 個ある。反射的であるためには \((1,1),(2,2),(3,3),(4,4)\) の 4 個を必ず含まなければならない。残り 12 個の順序対は独立に選べるから、反射的関係の個数は \[ 2^{12} = 4096 \] 通りである。

解説: 関係の個数は \(A \times A\) の部分集合の個数の数え上げに帰着する。反射性のような条件は「必ず含めるべき順序対」を固定し、残りの自由度を数えるとよい。

練習問題1.2 関数の性質

元問題: 第1章問題3（基礎）

解答種別: 詳細解答

問題: 関数 \(f: \mathbb{R} \to \mathbb{R}\)、\(f(x) = 2x + 1\) について、次に答えよ。 (a) f は単射であることを示せ (b) f は全射であることを示せ (c) f の逆関数を求めよ

解答:

(a) 単射性

\(f(x_1) = f(x_2)\) と仮定すると、 \[ 2x_1 + 1 = 2x_2 + 1 \] より \(2x_1 = 2x_2\)、したがって \(x_1 = x_2\) である。よって f は単射である。□

(b) 全射性

任意の \(y \in \mathbb{R}\) を取る。\(x = (y-1)/2\) とおけば \(x \in \mathbb{R}\) であり、 \[ f(x) = 2\cdot \frac{y-1}{2} + 1 = y \] となる。したがって任意の実数 y に対して \(f(x)=y\) となる x が存在するので、f は全射である。□

(c) 逆関数

\(y = 2x + 1\) を x について解くと \[ x = \frac{y-1}{2} \] である。したがって逆関数は \[ f^{-1}(y) = \frac{y-1}{2} \] すなわち \[ f^{-1}(x) = \frac{x-1}{2} \] である。

解説: 線形関数 \(ax+b\)（\(a \neq 0\)）は、方程式 \(ax+b=y\) が一意に解けるため、実数全体上で全単射になる。

練習問題1.3 数学的帰納法

元問題: 第1章問題5（基礎）

解答種別: 詳細解答

問題: 数学的帰納法を用いて、すべての \(n \ge 1\) に対して \[ 1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6} \] が成り立つことを証明せよ。

解答:

証明: 数学的帰納法による。

基底ケース \((n=1)\): \[ 1^2 = 1,\qquad \frac{1\cdot 2 \cdot 3}{6} = 1 \] なので成立する。

帰納法の仮定: ある \(k \ge 1\) について \[ 1^2 + 2^2 + \cdots + k^2 = \frac{k(k+1)(2k+1)}{6} \] が成り立つと仮定する。

帰納ステップ \((n=k+1)\): \[ \begin{aligned} 1^2 + 2^2 + \cdots + k^2 + (k+1)^2 &= \frac{k(k+1)(2k+1)}{6} + (k+1)^2
&= (k+1)\left(\frac{k(2k+1)}{6} + (k+1)\right)
&= (k+1)\left(\frac{2k^2 + 7k + 6}{6}\right)
&= (k+1)\left(\frac{(2k+3)(k+2)}{6}\right)
&= \frac{(k+1)(k+2)(2k+3)}{6}. \end{aligned} \] これは \(n=k+1\) のときの式 \[ \frac{(k+1)((k+1)+1)(2(k+1)+1)}{6} \] と一致する。

よって数学的帰納法により、すべての \(n \ge 1\) で主張が成り立つ。□

第2章: 計算理論の基礎

練習問題2.1 チューリング機械の設計

元問題: 第2章問題1（基礎）

元問題の項目: (b)

解答種別: 詳細解答

問題: 以下の言語を認識するチューリング機械を構成せよ。 (b) \({ ww \mid w \in {0,1}^{\ast} }\)

解答:

2 テープ非決定性チューリング機械 \(N\) を構成する。1 本目のテープに入力 x、2 本目のテープは作業用とする。

機械 \(N\) の動作

1 本目のテープを左から右へ読みながら、非決定的に「ここが真ん中である」と宣言する位置を 1 か所選ぶ。
真ん中を宣言するまでは、読んだ記号をそのまま 2 本目のテープへコピーする。
- したがって、真ん中を宣言した時点で 2 本目には前半の文字列 u が記録され、1 本目の読み取り位置には後半候補 v の先頭がある。
2 本目のヘッドを先頭へ戻す。
以後、1 本目の残り部分と 2 本目の内容を左から順に比較する。
- 片方だけが先に尽きたら拒否。
- 対応する記号が異なったら拒否。
- 両方が同時に尽きたら受理。

正当性:

入力が \(x = ww\) なら、真ん中をちょうど前半と後半の境界で選ぶ分岐が存在し、その分岐では 2 本目に最初の w がコピーされ、残りも同じ w なので比較がすべて成功して受理する。
逆にある分岐が受理したなら、その分岐で 2 本目にコピーされた文字列を u、1 本目の残りを v とすると、比較で全記号が一致し同時に尽きているから \(u=v\) である。したがって入力全体は \(uv = uu\) であり、\({ww}\) に属する。

よって \(N\) はちょうど \({ ww \mid w \in {0,1}^{\ast} }\) を認識する。

補足: 多テープ非決定性 TM の構成で十分であり、標準変換により単一テープ TM にも落とせる。ここで重要なのは「境界を仮定して検証する」という設計である。

練習問題2.2 計算可能性

元問題: 第2章問題3（基礎）

解答種別: 詳細解答

問題: 以下の言語が決定可能であることを証明せよ。 (a) ADFA = \({\langle B,w\rangle \mid B \text{ は DFA で、} B \text{ は } w \text{ を受理する}}\) (b) ECFG = \({\langle G\rangle \mid G \text{ は文脈自由文法で、} L(G) = \emptyset}\)

解答:

(a) ADFA は決定可能

決定機 \(D_{ADFA}\) を次で定める。

入力 \(\langle B,w\rangle\) を受け取る。
DFA \(B\) を初期状態から開始し、文字列 w を 1 文字ずつ読ませる。
すべて読み終えたときの状態が受理状態なら受理、そうでなければ拒否する。

DFA の遷移は各文字ごとに一意であり、w は有限長なので、この手続きは必ず停止する。したがって ADFA は決定可能である。□

(b) ECFG は決定可能

CFG \(G=(V,\Sigma,R,S)\) に対し、「終端文字列を導出できる非終端記号」の集合 \(\mathrm{Gen}\) を固定点計算で求める。

初期集合 \(\mathrm{Gen}\) を空にする。
ある規則 \(A \to \alpha\) について、\(\alpha\) に現れる非終端記号がすべてすでに \(\mathrm{Gen}\) に入っており、残りは終端記号だけなら、A を \(\mathrm{Gen}\) に追加する。
追加できる記号がなくなるまで 2 を繰り返す。
最後に \(S \in \mathrm{Gen}\) なら \(L(G) \neq \emptyset\) と判定して拒否し、\(S \notin \mathrm{Gen}\) なら受理する。

正当性:

\(A \in \mathrm{Gen}\) に入るのは、A から終端文字列を導出できる場合に限る。
固定点に達した後も \(S \notin \mathrm{Gen}\) なら、開始記号 S から終端文字列を導出する規則列は存在しないから、\(L(G)=\emptyset\) である。
V は有限集合なので、この反復は高々 \(\lvert V\rvert\) 回の追加で停止する。

よって ECFG も決定可能である。□

第3章: 形式言語とオートマトン理論

練習問題3.1 正規言語の証明

元問題: 第3章問題1（基礎）

元問題の項目: (b)

解答種別: 詳細解答

問題: 以下の言語を認識する DFA を構成せよ。 (b) \({w \in {a,b}^{\ast} \mid w \text{ 中の } a \text{ の個数は } 3 \text{ の倍数}}\)

解答:

a の個数を 3 で割った余りを状態として保持する DFA を作ればよい。DFA \(M=(Q,\Sigma,\delta,q_0,F)\) を次で定める。

\(Q = {q_0,q_1,q_2}\)
\(\Sigma = {a,b}\)
初期状態: \(q_0\)
受理状態: \(F = {q_0}\)
遷移関数:
- \(\delta(q_0,a)=q_1\), \(\delta(q_1,a)=q_2\), \(\delta(q_2,a)=q_0\)
- \(\delta(q_i,b)=q_i\) for \(i=0,1,2\)

状態の意味は次の通りである。

\(q_0\): これまでに読んだ a の個数が \(0 \bmod 3\)
\(q_1\): これまでに読んだ a の個数が \(1 \bmod 3\)
\(q_2\): これまでに読んだ a の個数が \(2 \bmod 3\)

b を読んでも a の個数は増えないので状態は変わらず、a を 1 つ読むたびに余りが 1 だけ進む。入力全体を読み終えた時点で \(q_0\) にいることと、a の個数が 3 の倍数であることは同値である。よってこの DFA が求める言語を認識する。□

練習問題3.2 文脈自由文法

元問題: 第3章問題4（基礎）

解答種別: 詳細解答

問題: 以下の言語を生成する CFG を構成せよ。 (a) \({a^{i}b^{j}c^{k} \mid i = j \text{ または } j = k}\) (b) \({w \in {a,b}^{\ast} \mid w = w^{R}}\)（回文）

解答:

(a) \(i=j\) または \(j=k\) を満たす言語

この言語は \[ L = {a^n b^n c^k \mid n,k \ge 0} \cup {a^i b^n c^n \mid i,n \ge 0} \] と分解できる。したがって、各部分言語を生成する CFG を和で束ねればよい。

次の CFG を考える。 \[ \begin{aligned} S &\to TC \mid AU
T &\to aTb \mid \varepsilon
C &\to cC \mid \varepsilon
A &\to aA \mid \varepsilon
U &\to bUc \mid \varepsilon \end{aligned} \]

\(S \to TC\) の枝では、T が \(a^n b^n\)、C が \(c^k\) を生成するので \(a^n b^n c^k\) を得る。
\(S \to AU\) の枝では、A が \(a^i\)、U が \(b^n c^n\) を生成するので \(a^i b^n c^n\) を得る。

よってこの文法はちょうど \(i=j\) または \(j=k\) を満たす文字列全体を生成する。□

(b) 回文の言語

\({a,b}\) 上の回文全体は、両端に同じ文字を付ける再帰で生成できる。CFG を \[ P \to aPa \mid bPb \mid a \mid b \mid \varepsilon \] とすればよい。

\(\varepsilon\) は長さ 0 の回文、a と b は長さ 1 の回文を与える。
既に回文である文字列の両端に同じ文字 a または b を付ければ、得られる文字列も回文である。
任意の回文は、長さ 0 または 1 まで外側から同じ文字を剥がしていけるので、この規則で導出できる。

したがってこの CFG は回文全体を生成する。□

練習問題3.3 ポンピング補題

元問題: 第3章問題12（発展）

元問題の項目: (a)

解答種別: 詳細解答

問題: 以下の言語が文脈自由言語か決定せよ。 (a) \({a^{n}b^{n}c^{n}d^{n} \mid n \ge 0}\)

解答: この言語は文脈自由言語ではない。

証明: 背理法で示す。もし \[ L = {a^{n}b^{n}c^{n}d^{n} \mid n \ge 0} \] が文脈自由言語なら、文脈自由言語に対するポンピング補題が適用できる。ポンピング長を p とし、 \[ s = a^p b^p c^p d^p \in L \] を取る。すると s は \[ s = uvxyz \] と分解でき、

\(\lvert vxy \rvert \le p\)
\(\lvert vy \rvert \ge 1\)
任意の \(i \ge 0\) について \(uv^i x y^i z \in L\) を満たす。

ここで各ブロック \(a^p, b^p, c^p, d^p\) の長さは p であり、\(\lvert vxy \rvert \le p\) なので、部分文字列 vxy は高々 2 個の隣接するブロックにしかまたがれない。したがって次のいずれかである。

1 種類の文字だけからなる。
a と b にまたがる。
b と c にまたがる。
c と d にまたがる。

いずれの場合も、\(i=0\) または \(i=2\) でポンプすると、4 種類の文字の個数がすべて等しいという条件が壊れる。

1 種類だけなら、その文字の個数だけが変化する。
a/b 境界なら a と b の個数だけが変化し、c と d は不変。
b/c 境界なら b と c の個数だけが変化し、a と d は不変。
c/d 境界なら c と d の個数だけが変化し、a と b は不変。

したがって \(uv^i x y^i z\) はある i で必ず L の外に出る。これはポンピング補題に矛盾する。

よって L は文脈自由言語ではない。□

練習問題3.4 Myhill–Nerode による最小DFA

元問題: 第3章問題8（発展）

元問題の項目: (a), (b)

解答種別: 詳細解答

問題: 章末問題「発展 8.」について、以下を示せ。 (a) \(L_1 = {\,w \in {a,b}^{\ast} \mid \text{w が部分文字列 } aba \text{ を含む}\,}\) の最小DFAは少なくとも4状態を要する。 (b) \(L_2 = {\,w \in {0,1}^{\ast} \mid \text{w 中の 1 の個数が } 0 \pmod{3} \text{ で、最終文字が } 0\,}\) の最小DFAは少なくとも6状態を要する。

解答:

(a) Myhill–Nerode の定理を用いる。接頭辞 \[ \varepsilon,\ a,\ ab,\ aba \] を考える。これらは互いに識別可能である。例えば、

\(aba\) は空接尾辞だけで既に受理側にいるので、他の 3 つと区別できる。
\(ab\) と \(a\) は接尾辞 \(a\) を付けると、\(aba \in L_1\) だが \(aa \notin L_1\) で区別できる。
\(a\) と \(\varepsilon\) は接尾辞 \(ba\) を付けると、\(aba \in L_1\) だが \(ba \notin L_1\) で区別できる。
\(ab\) と \(\varepsilon\) も接尾辞 \(a\) により、\(aba \in L_1\) だが \(a \notin L_1\) で区別できる。

このように少なくとも 4 個の異なる右同値類が必要なので、最小 DFA は少なくとも 4 状態を要する。実際、\(aba\) の照合進捗 \(\varepsilon\), a, ab, 発見済みを表す 4 状態 DFA で達成できる。

(b) 受理条件は

1 の個数の剰余が \(0 \pmod 3\)
最終文字が 0 の 2 条件の組で決まる。したがって右コンテキストとして少なくとも \[ 3 \times 2 = 6 \] 通りを区別する必要がある。

より具体的には、1 の個数の剰余 \(r \in {0,1,2}\) と「直前の文字が 0 か否か」\(b \in {0,1}\) の組 \((r,b)\) は、それぞれ異なる将来の受理可能性を持つ。例えば剰余が異なれば 1 を何個追加すれば受理条件 1 を満たすかが変わり、最終文字情報が異なれば空接尾辞や 0 を 1 文字足したときの受理可否が変わる。よって 6 通りは互いに識別可能であり、最小 DFA は少なくとも 6 状態を要する。□

練習問題3.5 Myhill–Nerode による非正規性

元問題: 第3章問題11（発展）

解答種別: 詳細解答

問題: Myhill–Nerode の定理を用いて、以下の言語が正規言語でないことを示せ。 \[ L = {0^{n}1^{n} \mid n \ge 0} \]

解答:

Myhill–Nerode の定理より、L が正規言語であるための必要十分条件は、右同値関係 \(\equiv_L\) の同値類が有限個であることだ。

各 \(i \ge 0\) に対して \(x_i = 0^i\) と置く。\(i \neq j\) のとき、\(x_i\) と \(x_j\) は識別可能である。実際、接尾辞 \(z = 1^i\) を付けると

\(x_i z = 0^i 1^i \in L\)
\(x_j z = 0^j 1^i \notin L\) が成り立つ。

したがって \(x_i \not\equiv_L x_j\) であり、\(x_0, x_1, x_2, \ldots\) は互いに異なる右同値類へ属する。よって \(\equiv_L\) の同値類は無限個存在する。

したがって Myhill–Nerode の定理により L は正規言語ではない。□

第4章: 計算可能性

練習問題4.1 停止問題

元問題: 第4章問題1（基礎）

元問題の項目: (a)

解答種別: 詳細解答

問題: 以下の言語が決定可能か、認識可能か、またはどちらでもないか判定し、証明せよ。 (a) \({\langle M\rangle \mid M \text{ は偶数長の文字列のみを受理する}}\)

解答: この言語は どちらでもない。すなわち決定可能でも認識可能でもない。

1. 決定可能ではない

性質 \[ P(L) : L \subseteq {x \mid \lvert x \rvert \text{ は偶数}} \] を考える。これはチューリング機械の構文ではなく受理言語そのものだけに依存する意味的性質である。また、

\(\emptyset\) は P を満たす
\({0}\) は P を満たさないので非自明である。したがって Rice の定理より、この性質を持つ機械の集合は決定可能ではない。□

2. 補集合は認識可能

補集合は \[ {\langle M\rangle \mid M \text{ が奇数長の文字列を少なくとも 1 つ受理する}} \] である。これは認識可能である。実際、奇数長文字列を \(w_1,w_2,\dots\) と列挙し、M を各 \(w_i\) 上で dovetailing すれば、どれか 1 つでも受理が見つかった時点で受理できる。

3. 元の言語は認識可能ではない

もし元の言語も認識可能なら、その補集合も認識可能なので両者を並行実行することで決定可能になってしまう。しかし 1 で示したように決定可能ではない。よって元の言語は認識可能でもない。□

練習問題4.2 Riceの定理

元問題: 第4章問題1（基礎）

元問題の項目: (b)

解答種別: 詳細解答

問題: 以下の言語が決定可能か、認識可能か、またはどちらでもないか判定し、証明せよ。 (b) \({\langle M\rangle \mid M \text{ は少なくとも 10 個の文字列を受理する}}\)

解答: この言語は 認識可能だが決定可能ではない。

1. 認識可能である

入力 \(\langle M\rangle\) に対し、すべての文字列を \(w_1,w_2,\dots\) と列挙し、M の計算を dovetailing で並行実行する。受理が確認できた文字列を重複なく記録し、その個数が 10 個に達した時点で受理する。

実際に \(L(M)\) が 10 個以上の文字列を含むなら、いつか 10 個の受理計算が見つかる。
10 個未満なら、その閾値に達しないので走り続ける。

したがってこの集合は認識可能である。□

2. 決定可能ではない

性質 \[ P(L) : \lvert L \rvert \ge 10 \] は受理言語だけに依存する意味的性質であり、

10 個以上の文字列を受理する言語は存在する
0 個しか受理しない言語も存在するので非自明である。したがって Rice の定理により、この集合は決定可能ではない。□

練習問題4.3 REGULAR_TM の非決定可能性（Rice）

元問題: 第4章問題1（基礎）

元問題の項目: (c)

解答種別: 詳細解答

問題: 以下の言語が決定可能か、認識可能か、またはどちらでもないか判定し、証明せよ。 (c) \({\langle M,w,k\rangle \mid M \text{ は } w \text{ を } k \text{ ステップ以内に受理する}}\)

解答: この言語は 決定可能 である。

決定アルゴリズム:

入力 \(\langle M,w,k\rangle\) を受け取る。
M を入力 w 上でちょうど k ステップまでシミュレートする。
その間に受理状態へ入ったら受理する。
k ステップ以内に受理しなければ拒否する。

正当性:

「k ステップ以内に受理するか」は有限回のシミュレーションだけで判定できる。
M が k ステップ以内に停止しなくても、こちらは k ステップで打ち切るので必ず停止する。

したがってこの言語は決定可能である。□

練習問題4.4 固定語包含性 CONTAINS_{w_0} の非決定可能性（Rice）

元問題: 第4章問題2（基礎）

元問題の項目: (a)

解答種別: 詳細解答

問題: \(A_{TM}\) から以下の言語への多対一還元を構成せよ。 (a) \(REGULAR_{TM} = {\langle M\rangle \mid L(M) \text{ は正規言語}}\)

解答:

入力 \(\langle M,w\rangle\) からチューリング機械 \(N\) を次のように構成する。

機械 N の動作（入力 x に対して）:

M を入力 w 上で \(\lvert x \rvert\) ステップだけシミュレートする。
その間に M が w を受理したら、x を無条件に受理する。
受理がまだ起きていなければ、x が \({0^n1^n \mid n \ge 0}\) に属するときに限って受理する。

この変換 \(f(\langle M,w\rangle)=\langle N\rangle\) は計算可能である。

正当性:

もし \(\langle M,w\rangle \in A_{TM}\) なら、M はある有限ステップ t で w を受理する。すると \(\lvert x \rvert \ge t\) を満たすすべての x は N によって無条件受理される。長さ t 未満の文字列についてだけ \({0^n1^n}\) の判定が残るが、その集合は有限である。したがって \[ L(N) = \Sigma^{\ge t} \cup F \] （ただし F は有限集合）となり、正規言語である。
もし \(\langle M,w\rangle \notin A_{TM}\) なら、M は w を受理しない。したがって 2 は一度も発動せず、N は常に \({0^n1^n \mid n \ge 0}\) だけを受理する。これは正規言語ではない。

ゆえに \[ \langle M,w\rangle \in A_{TM} \iff \langle N\rangle \in REGULAR_{TM}. \] よって \(A_{TM} \le_m REGULAR_{TM}\) が示された。□

練習問題4.5 FINITE_TM の非決定可能性（Rice）

元問題: 第4章問題2（基礎）

元問題の項目: (b)

解答種別: 詳細解答

問題: \(A_{TM}\) から以下の言語への多対一還元を構成せよ。 (b) \(ALL_{TM} = {\langle M\rangle \mid L(M) = \Sigma^{\ast}}\)

解答:

入力 \(\langle M,w\rangle\) から機械 \(N\) を次で定める。

機械 N の動作（入力 x に対して）:

x を無視して、M を入力 w 上でシミュレートする。
M が w を受理したら受理する。
それ以外（拒否または無限ループ）の場合は停止しない。

この変換 \(f(\langle M,w\rangle)=\langle N\rangle\) は明らかに計算可能である。

正当性:

\(\langle M,w\rangle \in A_{TM}\) なら、M は w を受理するので、N はすべての入力 x を受理する。したがって \(L(N)=\Sigma^{\ast}\) であり、\(\langle N\rangle \in ALL_{TM}\)。
\(\langle M,w\rangle \notin A_{TM}\) なら、M は w を受理しないので、N はどの入力でも受理しない。したがって \(L(N)=\emptyset\) であり、\(\langle N\rangle \notin ALL_{TM}\)。

よって \[ \langle M,w\rangle \in A_{TM} \iff \langle N\rangle \in ALL_{TM} \] が成り立つ。したがって \(A_{TM} \le_m ALL_{TM}\)。□

練習問題4.6 COFINITE_TM の非決定可能性（Rice）

元問題: 第4章問題5（発展）

元問題の項目: (a)

解答種別: 詳細解答

問題: 以下を証明せよ。 (a) \(A_{TM} \le_m HALT_{TM}\) と \(HALT_{TM} \le_m A_{TM}\) の両方を構成せよ。

解答:

ここで \[ A_{TM} = {\langle M,w\rangle \mid M \text{ は } w \text{ を受理する}} \] \[ HALT_{TM} = {\langle M,w\rangle \mid M \text{ は } w \text{ 上で停止する}} \] とする。

1. \(A_{TM} \le_m HALT_{TM}\)

入力 \(\langle M,w\rangle\) から機械 \(N\) と固定入力 0 を作る。

N は入力 y を受け取ったら y を無視し、M を w 上でシミュレートする。
M が w を受理したら N はただちに停止して受理する。
M が w を拒否した場合も無限ループへ入り、M がもともと停止しない場合もそのままシミュレーションを続ける。

すると \[ \langle M,w\rangle \in A_{TM} \iff \langle N,0\rangle \in HALT_{TM} \] である。ゆえに \(A_{TM} \le_m HALT_{TM}\)。

2. \(HALT_{TM} \le_m A_{TM}\)

入力 \(\langle M,w\rangle\) から機械 \(N\) と固定入力 0 を作る。

N は入力 y を受け取ったら y を無視し、M を w 上でシミュレートする。
M が w 上で受理しても拒否しても、とにかく停止した瞬間に N は y を受理する。
M が停止しなければ N も停止しない。

すると \[ \langle M,w\rangle \in HALT_{TM} \iff \langle N,0\rangle \in A_{TM} \] である。ゆえに \(HALT_{TM} \le_m A_{TM}\)。

どちらの変換も、入力記述から機械 N の記述を機械的に組み立てるだけなので計算可能である。□

練習問題4.7 還元テンプレ（多対一）適用の概略

元問題: 第4章問題9（発展）

解答種別: 詳細解答

問題: 章末問題9「テンプレ練習」として、4.2.3 のテンプレに従い、\(A_{TM} \le_m \overline{E_{TM}}\) または \(A_{TM} \le_m ALL_{TM}\) の構成を概説せよ。

解答の骨子

ここでは両方を同じテンプレートで整理する。入力は \(\langle M,w\rangle\) とする。

共通の構成

還元関数 \(f\) は \(\langle M,w\rangle\) から機械 \(N\) の記述 \(\langle N\rangle\) を出力する。
N は任意の入力 x に対し、x を無視して M を w 上でシミュレートする。
M が w を受理したら N は x を受理する。
M が w を受理しなければ N は受理しない（拒否してもよいし、停止しなくてもよい）。

このとき、M が w を受理すれば \(L(N)=\Sigma^{\ast}\)、受理しなければ \(L(N)=\emptyset\) となる。

(a) \(A_{TM} \le_m \overline{E_{TM}}\)

目標言語は \(\overline{E_{TM}} = {\langle N\rangle \mid L(N) \neq \emptyset}\)。
（\(\Rightarrow\)）\(\langle M,w\rangle \in A_{TM}\) なら \(L(N)=\Sigma^{\ast}\) なので非空。
（\(\Leftarrow\)）\(\langle N\rangle \in \overline{E_{TM}}\) なら N は何らかの入力を受理するが、受理は M が w を受理したときにしか起こらない。よって \(\langle M,w\rangle \in A_{TM}\)。

(b) \(A_{TM} \le_m ALL_{TM}\)

目標言語は \(ALL_{TM} = {\langle N\rangle \mid L(N)=\Sigma^{\ast}}\)。
（\(\Rightarrow\)）\(\langle M,w\rangle \in A_{TM}\) なら \(L(N)=\Sigma^{\ast}\)。
（\(\Leftarrow\)）\(\langle N\rangle \in ALL_{TM}\) なら特に N は何らかの入力を受理するので、やはり M は w を受理している。

計算可能性: \(\langle M,w\rangle\) から「x を無視して M を w で走らせる機械」の記述を生成するのは機械的な構文変換であり、f は計算可能である。

第5章: 計算複雑性理論

練習問題5.1 複雑性クラスの関係

元問題: 第5章問題1（基礎）

元問題の項目: (c)

解答種別: 詳細解答

問題: 以下の包含関係を証明せよ。 (c) \(NP \subseteq PSPACE\)

解答:

\(L \in NP\) とする。すると、ある多項式 p と多項式時間検証器 V が存在して \[ x \in L \iff \exists y\ (\lvert y\rvert \le p(\lvert x\rvert) \land V(x,y)=1) \] が成り立つ。

ここで PSPACE 機械 D を次のように作る。

入力 x に対して、長さ高々 \(p(\lvert x\rvert)\) のすべての証明列 y を辞書式順序で 1 つずつ列挙する。
各 y について V(x,y) を実行する。
どれか 1 つでも受理したら受理し、すべて失敗したら拒否する。

空間解析:

現在調べている y を保持するのに \(O(p(\lvert x\rvert))\) 空間で足りる。
V は多項式時間計算なので、使用空間も多項式に抑えられる。
したがって D 全体の使用空間は多項式である。

時間は証明列の総数だけ指数的になり得るが、PSPACE では時間ではなく空間だけが制約対象である。ゆえに \(L \in PSPACE\) であり、 \[ NP \subseteq PSPACE \] が従う。□

練習問題5.2 NP完全性の証明

元問題: 第5章問題3（基礎）

元問題の項目: (b)

解答種別: 詳細解答

問題: 3-SAT から以下への多項式時間還元を構成せよ。 (b) 頂点被覆問題

解答:

3-CNF 式 \[ \varphi = C_1 \land C_2 \land \cdots \land C_m \] （変数は \(x_1,\dots,x_n\)）から、グラフ G と整数 k を構成する。

構成:

変数ガジェット: 各変数 \(x_i\) について 2 頂点 \(x_i, \lnot x_i\) を作り、その間に 1 本の辺を張る。
節ガジェット: 各節 \(C_j=(\ell_{j1}\vee \ell_{j2}\vee \ell_{j3})\) について、3 頂点 \(c_{j1}, c_{j2}, c_{j3}\) を作り、三角形にする。
接続辺: 節頂点 \(c_{jr}\) を、そのリテラル \(\ell_{jr}\) に対応する変数頂点と結ぶ。
閾値: \(k = n + 2m\) とする。

正当性:

(\(\Rightarrow\)) \(\varphi\) が充足可能だとする。

各変数 \(x_i\) について、真になっている方のリテラル頂点を 1 つ選ぶ。これで各変数ガジェットの辺は被覆される。
各節 \(C_j\) では、少なくとも 1 つのリテラルが真である。その真リテラルに対応する節頂点を 1 つだけ残し、残り 2 頂点を選ぶ。これで三角形の 3 辺はすべて被覆される。
残した節頂点から出る接続辺は、そのリテラルが真なので対応する変数頂点が既に選ばれており、そこで被覆される。

合計で選んだ頂点数は \(n + 2m = k\) であり、頂点被覆が得られる。

(\(\Leftarrow\)) G にサイズ k の頂点被覆があるとする。

各変数ガジェットの辺を被覆するには少なくとも 1 頂点必要。
各節三角形を被覆するには少なくとも 2 頂点必要。

したがってサイズ k の頂点被覆は、各変数ガジェットからちょうど 1 頂点、各節ガジェットからちょうど 2 頂点を選んでいる。各変数ガジェットで選ばれた頂点に応じて真偽値を定める。各節ではちょうど 1 つの節頂点が選ばれずに残るが、その頂点に incident な接続辺は変数側で被覆されなければならない。したがって対応するリテラル頂点が選ばれており、そのリテラルは真である。ゆえに各節は少なくとも 1 つの真リテラルを持ち、\(\varphi\) は充足可能である。

構成は変数と節を 1 回ずつ走査するだけなので多項式時間で計算できる。よって 3-SAT から頂点被覆問題への多項式時間還元が得られる。□

練習問題5.3 3-SAT から VERTEX-COVER へのサイズ管理

元問題: 第5章問題3（基礎）

元問題の項目: (c)

解答種別: 詳細解答

問題: 章末問題「3. (c) サイズ管理」について、(b) の頂点被覆問題への還元で構成されるグラフの頂点数・辺数・k が、元の 3-SAT インスタンス（変数数 n、節数 m）に対して高々線形（O(n+m)）であることを示せ。

解答:

前問の構成を数え上げる。

変数ガジェット: 各変数につき 2 頂点 \((x_i,\lnot x_i)\) と 1 辺。
- 頂点数: \(2n\)
- 辺数: \(n\)
節ガジェット: 各節につき 3 頂点からなる三角形。
- 頂点数: \(3m\)
- 辺数: 各節あたり 3 本なので \(3m\)
接続辺: 各節の 3 リテラルそれぞれから対応する変数頂点へ 1 本ずつ張る。
- 辺数: \(3m\)

したがって全体では \[ \lvert V \rvert = 2n + 3m = O(n+m) \] \[ \lvert E \rvert = n + 3m + 3m = n + 6m = O(n+m) \] である。また閾値は \[ k = n + 2m = O(n+m) \] となる。

ゆえに還元後インスタンスのサイズ増加は線形であり、要求された「高々線形（\(O(n+m)\)）」が成り立つ。□

練習問題5.4 Cook–Levin のサイズ管理（概算）

元問題: 第5章問題6（発展）

解答種別: 詳細解答

問題: Cook-Levin の定理の証明で、チューリング機械の計算を論理式で符号化する際の具体的な構成を説明せよ。

解答:

入力 x を受け取って時間 \(T=p(\lvert x\rvert)\) 以内に動作する決定性チューリング機械 M を考える。Cook-Levin の核心は、「M が x を受理する長さ T の計算履歴が存在する」ことを、CNF 論理式 \(\Phi_{M,x}\) の充足可能性へ変換する点にある。

1. 計算表（tableau）の導入

時間を行、テープ位置を列とする \(T \times T\) の表を考える。各行は 1 時刻の構成（テープ内容、ヘッド位置、状態）を表す。

2. 変数

例えば次の 3 種類のブール変数を用意する。

\(X_{t,i,\sigma}\): 時刻 t、セル i に記号 \(\sigma \in \Gamma\) が書かれている
\(H_{t,i}\): 時刻 t にヘッドがセル i を読んでいる
\(Q_{t,q}\): 時刻 t に機械の状態が q である

ここで \(0 \le t \le T\)、\(1 \le i \le T\) とする。時間 T 以内の計算しか見ないので、必要なセル数も T 個で十分である。

3. 論理式の各成分

\(\Phi_{M,x}\) は次の制約の積として作る。

一意性制約
- 各セルには各時刻ごとにちょうど 1 つの記号が入る。
- 各時刻でヘッド位置はちょうど 1 つ。
- 各時刻で状態も 1 つだけ。
これは「少なくとも 1 つ」と「高々 1 つ」の CNF 制約で表せる。
初期構成制約
- 時刻 0 の行には入力 x が書かれている。
- それ以外のセルは空白記号。
- ヘッドは先頭セル、状態は開始状態 \(q_0\)。
受理制約
- どこかの時刻 t で状態が受理状態 \(q_{acc}\) になっている。
- これは \(\bigvee_{t=0}^{T} Q_{t,q_{acc}}\) で表せる。
遷移制約
- 連続する 2 行が、遷移関数 \(\delta\) に従う合法な更新になっていることを表す。
- ヘッドが読んでいる位置 i とその近傍だけが変化し、それ以外のセル内容は保存される。
- したがって「時刻 t の局所パターン」と「時刻 t+1 の局所パターン」の組として許されないものを禁止すればよい。

この 4 種類の制約をすべて満たす代入が存在することと、M の受理計算履歴が存在することは同値になる。

4. 正当性

受理計算があれば充足可能: 実際の計算表をそのまま変数へ代入すれば、各制約を満たす。
充足可能なら受理計算がある: 充足代入から各時刻の記号・ヘッド位置・状態を読み取ると、一意性制約により各行は正しい構成を定める。初期構成制約と遷移制約により、それらは M の正当な計算履歴になり、受理制約によりどこかで受理している。

5. サイズ評価

変数数は \(O(T^2 \cdot (\lvert \Gamma\rvert + \lvert Q\rvert))\)
節数も、各時刻・各セルについて定数個または多項式個の局所制約を置くだけなので \(O(T^2 \cdot \mathrm{poly}(\lvert \Gamma\rvert + \lvert Q\rvert))\)

T は入力長の多項式 \(p(\lvert x\rvert)\) なので、\(\Phi_{M,x}\) 全体のサイズも入力長の多項式で抑えられる。これにより SAT が NP 困難であることが導かれる。□

練習問題5.5 CLIQUE から VERTEX-COVER へのサイズ変換

元問題: 第5章問題3（基礎）

元問題の項目: (f)

解答種別: 詳細解答

問題: 章末問題「基礎 3.(f)」について、\(\mathrm{CLIQUE}(G,k)\) を \(\mathrm{VERTEX\text{-}COVER}(G^{\prime},k^{\prime})\) に多項式時間還元せよ。\(k^{\prime} = \lvert V\rvert - k\) の変換と、サイズ増加が多項式であることを示せ。

解答:

入力を \((G=(V,E),k)\) とする。補グラフ \(\overline{G}=(V,\overline{E})\) を \[ \overline{E} = {{u,v} \mid u \neq v,\ {u,v} \notin E} \] で定め、 \[ f(G,k) = (\overline{G},\ \lvert V\rvert-k) \] と写す。

正当性:

CLIQUE と INDEPENDENT-SET の対応

G にサイズ k のクリークがあることと、\(\overline{G}\) にサイズ k の独立集合があることは同値である。なぜなら、G で互いに辺がある頂点集合は、補グラフでは互いに辺がない集合になるからである。

INDEPENDENT-SET と VERTEX-COVER の対応

任意のグラフ H=(V,F) と部分集合 \(S \subseteq V\) について、S が独立集合であることと、\(V\setminus S\) が頂点被覆であることは同値である。実際、S の中に辺がないことは、すべての辺が少なくとも 1 端点を \(V\setminus S\) に持つことと同じである。

以上より、 \[ G \text{ にサイズ } k \text{ のクリークがある} \iff \overline{G} \text{ にサイズ } k \text{ の独立集合がある} \iff \overline{G} \text{ にサイズ } \lvert V\rvert-k \text{ の頂点被覆がある} \] が成り立つ。

サイズ増加:

頂点数は不変で \(\lvert V^{\prime}\rvert = \lvert V\rvert\)。
補グラフは全頂点対を調べれば \(O(\lvert V\rvert^2)\) 時間で構成できる。
\(k^{\prime} = \lvert V\rvert-k\) の計算は線形時間以下である。

したがってこの写像は多項式時間還元であり、サイズ増加も多項式である。□

第6章: アルゴリズムの数学的解析

練習問題6.1 Master定理

元問題: 第6章問題2（基礎）

元問題の項目: (e)

解答種別: 詳細解答

問題: 以下の各再帰式について、まず定理6.2の基本形を適用できるか判定し、その理由を述べた上で、指定した方法で漸近解を求めよ。 (e) \(T(n) = 4T(n/2) + n^2\)（基本形のマスター定理）

解答:

この再帰式は \[ T(n) = aT(n/b) + f(n) \] の形にあり、 \[ a=4,\qquad b=2,\qquad f(n)=n^2 \] なので、定理6.2 の基本形をそのまま適用できる。

まず \[ n^{\log_b a} = n^{\log_2 4} = n^2 \] である。したがって \[ f(n) = \Theta\left(n^{\log_2 4}\right) \] となり、マスター定理の ケース2 \[ f(n)=\Theta\left(n^{\log_b a}\log^k n\right)\ (k=0) \] に該当する。

よって \[ T(n)=\Theta\left(n^{\log_2 4}\log n\right)=\Theta(n^2\log n) \] である。□

確認（再帰木）: 深さ i では部分問題数が \(4^i\)、各部分問題サイズが \(n/2^i\) なので、そのレベルの非再帰仕事は \[ 4^i\left(\frac{n}{2^i}\right)^2 = n^2 \] で一定である。深さは \(\log_2 n\) だから、全体は \(n^2\) が \(\Theta(\log n)\) 層分積み重なり、 \[ T(n)=\Theta(n^2\log n) \] となる。

練習問題6.2 動的計画法の設計

元問題: 第6章問題4（基礎）

解答種別: 詳細解答

問題: 最長共通部分列（LCS）問題を動的計画法で解き、時間・空間複雑度を解析せよ。

解答:

2 つの文字列 \[ X=x_1x_2\cdots x_m,\qquad Y=y_1y_2\cdots y_n \] に対し、\(X[1..i]\) と \(Y[1..j]\) の LCS 長を dp[i][j] と定義する。

漸化式

境界条件: dp[0][j] = 0、dp[i][0] = 0
遷移:
- \(x_i = y_j\) なら dp[i][j] = dp[i-1][j-1] + 1
- \(x_i \neq y_j\) なら dp[i][j] = max(dp[i-1][j], dp[i][j-1])

意味は次の通りである。

末尾文字が一致するとき、その文字を LCS の最後に採用できるので 1 を足す。
一致しないときは、\(x_i\) を捨てる場合と \(y_j\) を捨てる場合の良い方を取る。

アルゴリズム

def lcs(X, Y):
    m, n = len(X), len(Y)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if X[i - 1] == Y[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    # 実際の LCS を復元する場合
    i, j = m, n
    ans = []
    while i > 0 and j > 0:
        if X[i - 1] == Y[j - 1]:
            ans.append(X[i - 1])
            i -= 1
            j -= 1
        elif dp[i - 1][j] >= dp[i][j - 1]:
            i -= 1
        else:
            j -= 1

    ans.reverse()
    return dp[m][n], ''.join(ans)

正当性

部分問題 dp[i][j] は「接頭辞どうしの LCS 長」を正確に表す。遷移は LCS の最後の文字が一致するかどうかで場合分けしており、最適部分構造に従っている。したがって表を小さい部分問題から埋めれば dp[m][n] は全体の LCS 長になる。

計算量

表の大きさは \((m+1)(n+1)\) なので、各セルを O(1) で計算すると \[ \text{時間計算量} = \Theta(mn) \]
表全体を保持するので \[ \text{空間計算量} = \Theta(mn) \]

LCS の長さだけが必要なら 1 行前だけを保持すればよく、空間は \(\Theta(\min{m,n})\) まで削減できる。ただし実際の LCS 文字列を復元するには、通常は表全体か復元用情報が必要である。□

練習問題6.3 置換法（不均等分割）

元問題: 第6章問題2（基礎）

元問題の項目: (c)

解答種別: 詳細解答

問題: 章末問題「基礎 2.(c)」\(T(n) = T(n/3) + T(2n/3) + n\) を置換法と再帰木で解き、\(T(n) = \Theta(n \log n)\) を示せ（\(T(1) = \Theta(1)\) とする）。

解答（上界の一例）:

帰納法で \(T(n) \le c\,n \log n\) を示す（\(\log\) の底は固定）。

帰納法の仮定として、すべての \(m < n\) で \(T(m) \le c\,m \log m\) が成り立つとする。すると、 \[ \begin{aligned} T(n) &= T(n/3) + T(2n/3) + n
&\le c\frac{n}{3}\log\frac{n}{3} + c\frac{2n}{3}\log\frac{2n}{3} + n. \end{aligned} \] ここで \[ \frac{n}{3}\log\frac{n}{3} + \frac{2n}{3}\log\frac{2n}{3} = n\log n + n\left(\frac13\log\frac13 + \frac23\log\frac23\right) \] であり、括弧内は負の定数である。よってある \(d>0\) が存在して \[ T(n) \le c n\log n - cdn + n \] と書ける。c を十分大きく取れば右辺は \(c n\log n\) 以下に抑えられるから、上界 \(T(n)=O(n\log n)\) が従う。

下界は再帰木で示す。深さ i に現れる部分問題サイズの総和は \[ \frac{n}{3} + \frac{2n}{3} = n \] という保存則により常に \(n\) である。したがって各レベルの非再帰仕事は \(\Theta(n)\) である。葉に達するまでの深さは少なくとも \(\Omega(\log n)\) なので、全体の仕事量は \(\Omega(n\log n)\) になる。

上界と下界を合わせると \[ T(n)=\Theta(n\log n) \] である。□

第7章: データ構造の理論

練習問題7.1（基礎1）

元問題: 第7章問題1（基礎）

解答種別: 詳細解答

問題: 配列、連結リスト、平衡二分探索木、ハッシュ表について、検索・挿入・削除・最小値検索の時間計算量を比較せよ。

解答（代表例）:

前提（代表的な実装）：

配列は「動的配列（ランダムアクセス可能、途中挿入/削除で要素シフトが発生）」を想定
連結リストは「単方向連結リスト（先頭/挿入位置が分かればO(1)で挿入可能）」を想定
平衡二分探索木は AVL 木 / 赤黒木等を想定
ハッシュ表は「平均O(1)（再ハッシュは償却）」を想定

データ構造	検索	挿入	削除	最小値検索
配列	O(n)	O(n)（末尾追加は償却O(1)）	O(n)	O(n)（整列済みならO(1)）
連結リスト	O(n)	O(1)（位置既知）/O(n)（探索込み）	O(1)（前ノード既知）/O(n)（探索込み）	O(n)
平衡BST	O(log n)	O(log n)	O(log n)	O(log n)
ハッシュ表	平均O(1)、最悪O(n)	平均O(1)、最悪O(n)（再ハッシュは償却）	平均O(1)、最悪O(n)	O(n)（別途最小管理が必要）

補足：

「最小値検索」を頻繁に要求するなら、平衡BST（またはヒープ）等の適材適所が重要。
ハッシュ表で最小値検索をO(1)にしたい場合は、別途 min を保つ構造（例：双方向連結リスト + TreeMap、あるいは order statistic tree）を併用する。

練習問題7.2（基礎2）

元問題: 第7章問題2（基礎）

解答種別: 詳細解答

問題: AVL木の挿入で平衡が崩れたときの回転操作を場合分けして説明せよ。

解答:

不平衡が最初に発生した節点を z、z の「重い側」の子を y、挿入された節点（またはその祖先のうち回転判断に使う節点）を x とする。z の平衡係数が +2（左が重い）/ -2（右が重い）になったとき、次の4ケースに分類できる。

LLケース（z の左部分木の左側に挿入）
z で 右回転（single right rotation）。
RRケース（z の右部分木の右側に挿入）
z で 左回転（single left rotation）。
LRケース（z の左部分木の右側に挿入）
y で 左回転し、z で 右回転する（double rotation）。
RLケース（z の右部分木の左側に挿入）
y で 右回転し、z で 左回転する（double rotation）。

回転後、関係する節点（z,y,x）の高さを更新すれば AVL 条件を回復できる。

練習問題7.3（基礎3）

元問題: 第7章問題3（基礎）

解答種別: 詳細解答

問題: 開番地法のハッシュ表で、二次探査と二重ハッシュ法を比較せよ。

解答:

二次探査（quadratic probing）：

探査列の例：h(k,i) = (h(k) + c1i + c2i^2) mod m
長所：一次探査より primary clustering（一次クラスタリング）を緩和しやすい
短所：同一の初期ハッシュ値を持つキー同士で探査列が一致しやすく、secondary clustering（二次クラスタリング）が残る
また、m や係数の選び方によっては全スロットを走査しない場合がある

二重ハッシュ（double hashing）：

探査列の例：h(k,i) = (h1(k) + i*h2(k)) mod m
長所：h2(k) と m が互いに素になるよう設計できれば、全スロットを巡回しやすく分布も良い
clustering をさらに抑制しやすい
短所：2つ目のハッシュ関数設計が必要（h2(k)=0 を避ける等）

実務上は、実装容易性・衝突分布・テーブルサイズ制約（m の取り方）を含めて選定する。

練習問題7.4（基礎4）

元問題: 第7章問題4（基礎）

解答種別: 詳細解答

問題: ヒープソートが安定でないことを示す例を構成せよ。

解答:

安定性とは、キーが等しい要素の相対順序がソート後も保存される性質である。ヒープソートは、ヒープ構築・ヒープ化の過程で等キー要素を交換し得るため、一般に安定ではない。

例（キー,識別子）で表す：

入力：[(1, A), (1, B), (0, C)]

最大ヒープを作る際や、最大要素を末尾に送る際に (1, A) と (1, B) が交換される可能性があり、出力が

[(0, C), (1, B), (1, A)] となれば、等キー（1）の A と B の順序が反転しているため非安定である。

練習問題7.5（発展5）

元問題: 第7章問題5（発展）

解答種別: 詳細解答

問題: 赤黒木の削除操作の概要を示し、高々3回の回転で済むことを説明せよ。

解答（概略）:

削除は「二分探索木としての削除」+「赤黒条件の修復（fix-up）」に分ける。

1) BSTとしての削除
削除対象 z が2子を持つ場合、後継 y（successor）と入れ替え、実際に削除する節点は高々1子の節点 y にする。
子を x とする（NIL を含む）。

2) 色の補正
y の元の色が赤なら、削除しても黒高さが変わらず終了。
y の元の色が黒なら、黒高さが1つ不足するため「二重黒（double black）」として x 側で修復する。

3) 修復（代表的な4ケース、左右対称）
x の兄弟を w とする（CLRSに準拠）。

Case 1: w が赤
w を黒、親を赤に再彩色し、親で1回回転して w を黒にするケースへ変形（回転1回）。
Case 2: w が黒、w の両子が黒
w を赤にして二重黒を親へ繰り上げ（回転なし、ループ継続）。
Case 3: w が黒、w の「近い側の子」が赤、「遠い側の子」が黒
w と近い側の子を再彩色し、w で1回回転して Case 4 へ（回転1回）。
Case 4: w が黒、w の「遠い側の子」が赤
w を親の色に、親を黒に、遠い側の子を黒に再彩色し、親で1回回転して終了（回転1回）。

回転回数は、最悪でも Case 1 から Case 3 を経て Case 4 に遷移するため 高々3回。

練習問題7.6（発展6）

元問題: 第7章問題6（発展）

解答種別: 詳細解答

問題: フィボナッチヒープの decreaseKey 操作の償却解析を行え。

解答（代表的なポテンシャル法）:

ポテンシャル関数を Φ(H) = t(H) + 2m(H) と置く。

t(H): 根リストにある木（root）の個数
m(H): マークされた節点数

decreaseKey(x, k)（k が小さくなる）では、ヒープ順序を破る場合に x を切断して根へ移し（cut）、親がすでに子を失ってマークされていたら連鎖的に切断する（cascading cut）。

実コスト: O(1 + c)（c は切断回数）
ポテンシャル変化:
- 切断1回で root が増えるため t(H) が +1
- 切断された節点はマーク解除されるので m(H) が -1（解除が起きる場合）
- 親のマークは「初回の子喪失で +1、2回目で切断（=マーク解除）」となり、2m(H) が連鎖切断のコストを支払う

標準的な計算により、連鎖切断によるポテンシャル減少が実コストを相殺し、償却 O(1) が得られる。

練習問題7.7（発展7）

元問題: 第7章問題7（発展）

解答種別: 詳細解答

問題: 接尾辞配列を O(n) 時間で構築するアルゴリズムを説明せよ。

解答（SA-IS の概要）:

SA-IS（induced sorting）法は、接尾辞を S型/L型に分類し、LMS（Leftmost S-type）部分文字列のソートから全体を誘導することで O(n) を達成する。

各位置 i を S型/L型に分類（末尾から走査）
- S型: s[i:] < s[i+1:]
- L型: s[i:] > s[i+1:]
LMS位置（L から S に切り替わる位置）を抽出し、LMS部分文字列をバケットソートで整列
LMS部分文字列に同値類番号を付与して縮約文字列を作り、必要なら再帰的に接尾辞配列を構築
得られた順序を用い、L型接尾辞とS型接尾辞を「誘導整列（induced sorting）」で復元

各ステップが定数回の線形走査とバケット操作で実装できるため全体で O(n)。

練習問題7.8（発展8）

元問題: 第7章問題8（発展）

解答種別: 詳細解答

問題: 動的な順序統計量を効率的にサポートするデータ構造（select/rank）を設計せよ。

解答:

平衡二分探索木（例：赤黒木）に 部分木サイズ size(v) を拡張情報として保持する（order statistic tree）。

size(v) = 1 + size(left(v)) + size(right(v))

select(k):

r = size(left(v)) + 1 を計算
k == r なら v が答え
k < r なら左へ、k > r なら右へ（k ← k - r）

rank(x):

x を探索しながら、右へ進むたびに「左部分木サイズ + 1」を加算していく

平衡性が保たれるため、各操作は O(log n)。

練習問題7.9（探究9）

元問題: 第7章問題9（探究）

解答種別: 調査ガイド

問題: kd木、R木など計算幾何で使われる高度なデータ構造を調査し、性能特性を論ぜよ。

解答（調査ガイド）:

比較観点（例）：

対象データ：点群/矩形/多角形、次元（d）と「次元の呪い」
クエリ：範囲検索（range query）、最近傍探索（kNN）、交差判定
更新：挿入/削除の頻度、バルクロードの可否
理論特性：平均/最悪の計算量、近似の許容
実装特性：メモリ局所性、分岐予測、外部記憶（ディスク）最適化

代表例：

kd木：低次元（d が小さい）での範囲検索・最近傍に有効。高次元では性能が劣化しやすい。
R木：矩形領域の階層インデックス。空間DBで実用的（外部記憶・バルクロードが重要）。

アウトプット例：

「ワークロード（クエリ種別/データ分布）ごとの優劣」「更新頻度を含めた総コスト」「実測（n=10^5〜10^7程度）のスループット/レイテンシ」。

練習問題7.10（探究10）

元問題: 第7章問題10（探究）

解答種別: 調査ガイド

問題: 関数型プログラミングにおける永続的データ構造について調査し、命令型実装との比較を行え。

解答（調査ガイド）:

要点：

永続（persistent）: 破壊的更新をせず、古い版も参照可能にする（構造共有）
実装技法：path copying、fat node、node copying、trie（例：HAMT）
比較軸：更新のオーバーヘッド（定数因子/GC負荷）、参照透過性、スレッド安全性、ロールバック容易性

例：

永続マップ：平衡木（更新でO(log n) 個のノードをコピー）
命令型：更新はO(log n)だが破壊的、並行読み書きには追加同期が必要

練習問題7.11（探究11）

元問題: 第7章問題11（探究）

解答種別: 調査ガイド

問題: CPUキャッシュ階層を考慮したデータ構造最適化技法を調査せよ。

解答（調査ガイド）:

観点：

ポインタ追跡（pointer chasing）を減らす（連結リスト/木のキャッシュミス増大）
ブロッキング/配列化（SoA/ AoS）、B木系（B+木）による局所性向上
cache-oblivious（キャッシュ無関知）レイアウト（van Emde Boas レイアウト等）
false sharing 回避、アラインメント、プリフェッチ

評価方法：

L1/L2/L3 miss rate、TLB miss、分岐予測ミスをプロファイル（perf等）

練習問題7.12（探究12）

元問題: 第7章問題12（探究）

解答種別: 調査ガイド

問題: LSH、Annoy等の近似最近傍探索のデータ構造について調査し、保証と性能のトレードオフを論ぜよ。

解答（調査ガイド）:

比較軸：

近似比（(1+ε)-ANN 等）と成功確率
インデックス構築時間/メモリ量/更新可否
クエリレイテンシ（p95/p99）とリコール（recall）

例：

LSH：確率的保証（距離に応じた衝突確率）。高次元でも理論保証を与えやすいがメモリ増大しやすい。
Annoy：ランダム投影木（forest）で実用性能重視。理論保証は限定的だが実装容易で高速。

練習問題7.13（実装13）

元問題: 第7章問題13（実装）

解答種別: 参照実装

問題: 赤黒木/スプレー木/スキップリスト等を実装し、性能比較を行え。

解答（方針）:

参照実装の最小要件：insert/search/delete を揃え、同一の操作列で比較する
測定：データサイズ（例：10^4,10^5,10^6）、分布（ランダム/昇順/Zipf）、操作比率（検索多め等）
指標：操作当たり時間、メモリ量、最悪ケース（昇順入力など）

期待される性質：

赤黒木：最悪 O(log n) を保証（回転・再彩色）
スプレー木：償却 O(log n)、局所性のあるアクセスで有利
スキップリスト：平均 O(log n)、実装容易だが乱数品質/定数因子に依存

練習問題7.14（実装14）

元問題: 第7章問題14（実装）

解答種別: 参照実装

問題: Union-Find を経路圧縮＋ランク併合で実装し、償却計算量を検証せよ。

解答:

実装の要点：

find(x): 経路圧縮（再帰/反復で親を根に付け替える）
union(x,y): ランク/サイズの小さい木を大きい木へぶら下げる

理論：

m 回の操作（find/union）に対し、償却計算量は O(m α(n))（α は逆Ackermann関数）となる。

備考：

本リポジトリの python/tcs_exercises/union_find.py と python/tests/test_union_find.py が参照実装・テストとして利用できる。

練習問題7.15（実装15）

元問題: 第7章問題15（実装）

解答種別: 参照実装

問題: ブルームフィルタ、Count-Minスケッチ、HyperLogLog を実装し評価せよ。

解答（設計指針）:

Bloom filter
- パラメータ：要素数 n、ビット数 m、ハッシュ本数 k
- 目標偽陽性率 p に対する代表式：m ≈ -(n ln p)/(ln 2)^2、k ≈ (m/n) ln 2
Count-Min sketch
- 幅 w = ⌈e/ε⌉、深さ d = ⌈ln(1/δ)⌉ として、確率 1-δ で誤差 εN
HyperLogLog
- レジスタ数 m=2^p を用い、相対誤差は概ね 1.04/√m

評価（例）：

Bloom：偽陽性率の実測（p と比較）
CMS：頻度推定の最大誤差、p95誤差
HLL：カーディナリティ推定の相対誤差（分布別）

第8章: グラフ理論とネットワーク

練習問題8.1（基礎1）

元問題: 第8章問題1（基礎）

解答種別: 詳細解答

問題: (a) トポロジカルソート (b) 2-SAT の多項式時間解法 (c) DAGの最長パスを実装し、時間計算量を解析せよ。

解答:

(a) トポロジカルソート（Kahn法の例）:

各頂点の入次数 indeg[v] を計算（O(V+E)）
indeg[v]=0 の頂点をキューに入れる
キューから取り出して出力し、出辺 \((v \to u)\) を削除（u の indeg を減らす）
新たに indeg=0 になった頂点をキューに追加

計算量：入次数計算と各辺の処理が1回ずつなので O(V+E)。

(b) 2-SAT（含意グラフ + SCC）:

2-CNF の節 (a ∨ b) を、含意 \((\lnot a \to b)\) と \((\lnot b \to a)\) に変換する
変数 x について x と ¬x が同一 SCC に入る ⟺ 充足不能
充足可能なときは SCC のトポロジカル順（例：Kosarajuの帰りがけ順）で真偽を割り当てる

計算量：含意グラフの頂点は 2n、辺は節数に比例（O(m)）。SCC が O(V+E)=O(n+m)。

DAG である前提のもと、トポロジカル順に頂点を処理して DP を行う
重みなしなら dist[v] = max(dist[u]+1)（\((u \to v)\)）
重み付きなら dist[v] = max(dist[u]+w(u,v))

計算量：トポロジカルソート O(V+E) + 辺緩和 O(E) で O(V+E)。

練習問題8.2（基礎2）

元問題: 第8章問題2（基礎）

解答種別: 詳細解答

問題: Dijkstra が負の重みで失敗する例を構成せよ。

解答:

頂点 s,a,b と辺：

\(s \to a: 2\)
\(s \to b: 5\)
\(b \to a: -4\)

真の最短距離は dist(a)=1（\(s \to b \to a\)）だが、Dijkstra は dist(a)=2 を確定してしまい、その後に b を確定しても a の確定値を更新できない（負辺により「確定済みが最短」という前提が破綻する）。

練習問題8.3（基礎3）

元問題: 第8章問題3（基礎）

解答種別: 詳細解答

問題: 最小全域木（MST）がユニークとなる必要十分条件を示せ。

解答（代表的同値条件）:

以下は同値：

MST が一意である
任意のカットに対して、そのカットを横切る最小重み辺が一意である（cut property の一意性）
任意のサイクルに対して、そのサイクル上の最大重み辺が一意である（cycle property の一意性）

十分条件として「全ての辺重みが相異なる」なら MST は必ず一意（同順位がないため、選択の分岐が生じない）。

練習問題8.4（基礎4）

元問題: 第8章問題4（基礎）

解答種別: 詳細解答

問題: 二部グラフ最大マッチングを最大フローに帰着せよ。

解答:

二部グラフ G=(L∪R,E) に対し、容量1のフロー網を構成する：

s から各 u∈L へ容量1
各 (u,v)∈E（u∈L,v∈R）へ容量1
各 v∈R から t へ容量1

このとき、整数フローの性質より、最大フロー値 = 最大マッチング数となる（フロー1が対応する辺がマッチング）。

練習問題8.5（発展5）

元問題: 第8章問題5（発展）

解答種別: 詳細解答

問題: 固定された平面埋め込みを持つ連結な無向plane graphで、同一faceの境界上にある \(s,t\) のminimum cutをdual shortest pathとして求めるための条件、構成、証明を示せ。

解答:

前提と構成

\(G=(V,E)\) を連結な無向plane graphとし、その平面埋め込みを固定する。各辺 \(e\) のcapacityは \(c(e)\ge 0\) であり、異なる頂点 \(s,t\) は同一face \(f_0\) の境界上にあると仮定する。「planar graphである」だけではdualは一意に定まらないため、fixed embeddingは定理のデータの一部である。

埋め込みに対するdual graph \(G^{\ast}\) は、primalの各faceを1頂点とし、primal edge \(e\) が接する2つのfaceをdual edge \(e^{\ast}\) で結んで得る。橋は同じfaceの両側に接するためdualでは self-loopとなり、primalまたはdualの平行辺も許す。

\(f_0\) の内部に補助辺 \(e_0=(s,t)\) を交差なく描き、拡張したplane graphを \(\widehat{G}\) とする。 \(e_0\) は \(f_0\) を2つのface \(f_L,f_R\) に分ける。\(\widehat{G}\) のdualから \(e_0^{\ast}\) を削除したグラフを \(H=\widehat{G}^{\ast}-e_0^{\ast}\) とし、元の各辺 \(e\in E\) に対応するdual edgeへ

\[ w(e^{\ast})=c(e) \]

を割り当てる。ここで証明する主張は一意に、

\[ \min_{s\in S,\ t\notin S} c(\delta_G(S)) =\operatorname{dist}_{H}(f_L,f_R) \]

というminimum \(s\)-\(t\) cutと \(f_L\)-\(f_R\) shortest pathの対応である。

cutからdual pathへ

非負capacityのminimum \(s\)-\(t\) cutのうち、包含関係について極小な辺集合 \(C\) を選ぶ。 \(C\) はbondであり、\(G-C\) の \(s\) 側と \(t\) 側はそれぞれ連結である。拡張グラフ \(\widehat{G}\) では \(C\cup\{e_0\}\) がbondなので、plane graphの bond–cycle dualityにより、対応するdual edge集合 \(C^{\ast}\cup\{e_0^{\ast}\}\) は \(\widehat{G}^{\ast}\) のsimple cycleになる。このcycleから \(e_0^{\ast}\) を除くと、\(H\) の \(f_L\)-\(f_R\) path \(P\) を得る。

dual pathからcutへ

逆に、非負weightなので \(H\) のshortest \(f_L\)-\(f_R\) path \(P\) はsimpleに選べる。 \(P\cup\{e_0^{\ast}\}\) はdualのsimple cycleであり、Jordan curve theoremにより平面を 2領域に分ける。補助辺 \(e_0\) がこのcycleと交差するため、\(s\) と \(t\) は異なる領域にある。したがって、\(P\) の各dual edgeに対応するprimal edge集合 \(C_P\) は \(s\)-\(t\) cutである。この2方向から、minimum cutとshortest pathの最適値は互いを上から抑え、等しくなる。

容量と重みの一致

対応する辺ごとに \(w(e^{\ast})=c(e)\) と定義したので、上の対応では

\[ w(P)=\sum_{e^{\ast}\in P}w(e^{\ast}) =\sum_{e\in C_P}c(e)=c(C_P) \]

が成り立つ。したがって、dual shortest pathの距離はprimal minimum cutのcapacityそのものである。

4-cycleでの手計算

4-cycleを時計回りに \(s-a-t-b-s\) と埋め込み、 \(c(sa),c(at),c(tb),c(bs))=(2,3,1,4)\) とする。\(e_0=(s,t)\) を外側のfaceへ追加すると、 dualでは \(f_L\) から内側のface \(f_I\) まで重み2と3の平行辺、\(f_I\) から \(f_R\) まで重み1と4の平行辺を得る。よってshortest pathの重みは

\[ \min(2,3)+\min(1,4)=2+1=3 \]

である。primal側の4つの候補cutは、\(S=\{s\},\{s,a\},\{s,b\},\{s,a,b\}\) の順に capacity \(6,7,3,4\) を持つ。したがって \(\delta(\{s,b\})=\{sa,bt\}\) がcapacity 3の minimum cutであり、dual pathが選ぶ重み2の \(sa\) と重み1の \(bt\) に辺ごとに対応する。

成立範囲

ここでshortest pathと言えるのは、\(s,t\) が同一faceの境界上にあり、補助辺 \(e_0\) によって分かれた固定された2つのdual face \(f_L,f_R\)を端点にできるからである。この前提を外した一般のplane graphでは、cut側の表現は \(s,t\) を分離するminimum separating cycleであり、単一の既知face対に対するshortest pathと無条件に同一視してはならない。本問はcofacialな無向の場合だけを扱い、 directed planar flow、一般のminimum separating cycleアルゴリズム、higher-genus surfaceへの一般化は対象外とする。

出典と拡張の境界

この補助辺によるcost-preservingなcut–path対応は、Reif (1983) Section 3, Theorem 2の \((s,t)\)-planar networkに対する定式化に基づく（原論文PDF、 DOI: 10.1137/0212005）。同論文の定理は正のcostを仮定する。本解答で用いた非負capacityへの拡張は、0-weight edgeがあっても minimum cutから包含極小なものを、shortest walkからsimple pathを選べることによる。これは本文で明示した bond–cycleの議論から従う拡張であり、一次文献の定理文をそのまま引用した主張ではない。

練習問題8.6（発展6）

元問題: 第8章問題6（発展）

解答種別: 詳細解答

問題: 木幅（treewidth）の定義・計算複雑性と、有界木幅で効率的に解ける問題を述べよ。

解答:

(a) 定義（木分解）：

袋（bag）集合 {X_i} と木 T からなり、
1. 全頂点がどこかの袋に含まれる
2. 各辺 (u,v) に対し、同一袋に u,v を含む
3. 各頂点 v を含む袋集合は T 上で連結
幅 = max_i \(\lvert X_i\rvert\) - 1、木幅 tw(G) は幅の最小値

計算複雑性：

一般に treewidth の決定問題は NP困難（ただし固定 k に対しては FPT アルゴリズムがある）。

(b) 有界木幅で解ける代表例：

動的計画法により、頂点被覆・独立集合・支配集合などが f(k)·poly(n) で解ける
MSO論理で記述できる多くの性質は Courcelle の定理により線形時間（定数は f(k)）

練習問題8.7（発展7）

元問題: 第8章問題7（発展）

解答種別: 詳細解答

問題: 頂点彩色の近似について、(a) 貪欲法の近似比を示し (b) より良い近似を提案せよ。

解答:

(a) 貪欲彩色（順序に従い最小の使用可能色を割当）では、各頂点 v は高々 Δ 個の隣接頂点しか持たないため、隣接頂点が使っている色数は高々 Δ。従って常に Δ+1 色以内で彩色できる（必要色数は高々 Δ+1）。

(b) 改善案（例）：

退化順序（degeneracy ordering）で貪欲彩色を行うと、使用色数は d+1（d は退化度）に抑えられる
- 平面グラフは d が 5 以下なので 6 色で彩色可能（4色定理を使わない構成的上界）
実務上の改善としては DSATUR 等のヒューリスティクスも有効（ただし近似保証は別途評価が必要）

練習問題8.8（発展8）

元問題: 第8章問題8（発展）

解答種別: 詳細解答

問題: ネットワーク信頼性に関連して (a) 最小カットと辺連結度の関係 (b) k-辺連結判定アルゴリズムを述べよ。

解答:

(a) 無向グラフの 辺連結度 λ(G) は、「グラフを非連結にするために除去すべき最小辺数」であり、これは 最小カット（global min-cut） のサイズに等しい。

(b) 判定アルゴリズム（無向）：

Stoer-Wagner アルゴリズムで global min-cut を計算し、\(\lambda(G) \ge k\) を確認する
- 計算量は実装により O(VE + V^2 log V) 程度が代表的

（補足）有向グラフでは s-t min-cut（max-flow）を全対に取る必要があり、設定により手法が異なる。

練習問題8.9（探究9）

元問題: 第8章問題9（探究）

解答種別: 調査ガイド

問題: ソーシャルネットワーク指標（中心性、クラスタリング係数等）を調査し、計算アルゴリズムを設計せよ。

解答（調査ガイド）:

対象指標（例）と計算：

次数中心性：各頂点の次数（O(V+E)）
媒介中心性：Brandes アルゴリズム（重みなし O(VE)、重みあり O(VE + V^2 log V)）
固有ベクトル中心性/PageRank：反復法（1反復あたり O(E)）
クラスタリング係数：三角形数カウント（疎グラフ向けの工夫が重要）

設計観点：

大規模グラフでは近似（サンプリング、スケッチ）や分散処理が実務上必要

練習問題8.10（探究10）

元問題: 第8章問題10（探究）

解答種別: 調査ガイド

問題: GNN の理論的基礎と表現力の限界を論ぜよ。

解答（調査ガイド）:

論点：

多くのメッセージパッシングGNNは Weisfeiler-Lehman（1-WL）同値性検査と同程度の識別能力に制限される
高次WL（k-WL）/高次GNNで表現力は上がるが計算量・メモリが増大
over-smoothing/over-squashing 等の深層化に伴う課題

アウトプット例：

「識別できないグラフ例（同型でないが1-WLで区別不能）」と、その回避策（位置埋め込み、アテンション、サブグラフ手法等）

練習問題8.11（探究11）

元問題: 第8章問題11（探究）

解答種別: 調査ガイド

問題: 量子アルゴリズムによるグラフ問題の高速化を調査し、比較せよ。

解答（調査ガイド）:

代表的観点：

Grover 探索による平方根高速化（探索型の部分問題に適用可能）
量子ウォークによる高速化（要素探索、特定構造の検出）
入力モデル（オラクル/QRAM）と現実実装可能性が速度議論の前提を左右

比較軸：

クエリ計算量と総計算量、前処理コスト、エラー耐性、現実の入出力仮定

練習問題8.12（探究12）

元問題: 第8章問題12（探究）

解答種別: 調査ガイド

問題: 動的グラフアルゴリズム（辺/頂点の追加削除）を調査し、改善点を述べよ。

解答（調査ガイド）:

対象（例）：

動的連結性（dynamic connectivity）：完全動的で polylog 更新を目指す研究がある
動的最短路：近似や制約付き（増加のみ/減少のみ）で高速化が可能

比較軸：

インクリメンタル/デクリメンタル/完全動的の区別
更新（update）時間、クエリ時間、近似率、メモリ

練習問題8.13（実装13）

元問題: 第8章問題13（実装）

解答種別: 参照実装

問題: Dijkstra、最大フロー、MST、SCC を実装せよ。

解答（方針）:

Dijkstra：ヒープ（優先度付きキュー）で O((V+E) log V)
最大フロー：Dinic で O(E√V)（単位容量）など、実装難度と性能で選定
MST：Kruskal（Union-Find）で O(E log E)、Prim で O(E log V)
SCC：Kosaraju または Tarjan で O(V+E)

備考：

本リポジトリの python/tcs_exercises/graph_algorithms.py / python/tcs_exercises/union_find.py が一部参照実装として利用できる。

練習問題8.14（実装14）

元問題: 第8章問題14（実装）

解答種別: 参照実装

問題: 中心性、コミュニティ検出、可視化、ランダムグラフ生成を実装せよ。

解答（方針）:

中心性：媒介中心性は Brandes を採用、PageRank は反復計算
コミュニティ検出：Girvan-Newman（分割）/ Louvain（モジュラリティ最大化）等
可視化：レイアウト（spring、spectral）とサンプリング（大規模は間引き）
生成：Erdős-Rényi、Barabási-Albert、Watts-Strogatz をパラメータ化

練習問題8.15（実装15）

元問題: 第8章問題15（実装）

解答種別: 参照実装

問題: 最短路/最大フローのアルゴリズムを比較し、実グラフで測定せよ。

解答（方針）:

ベンチマーク設計：

入力：疎/密、重みの分布、グラフサイズ（V,E）
指標：実行時間、メモリ、反復回数、p95/p99
条件：同一環境、ウォームアップ、乱数固定

分析観点：

理論計算量だけでなく、定数因子（データ構造/キャッシュ局所性）が結果を左右する。

第9章: 論理学と形式的手法

練習問題9.1（基礎1）

元問題: 第9章問題1（基礎）

解答種別: 詳細解答

問題: 以下の論理式の充足可能性を判定し、充足可能ならモデルを示せ。

(a) \((p \to q) \land (q \to r) \land (r \to p)\)
(b) (p ∨ q ∨ r) ∧ (¬p ∨ ¬q) ∧ (¬q ∨ ¬r) ∧ (¬r ∨ ¬p)

解答:

(a) 充足可能。
含意を除去すると (¬p∨q)∧(¬q∨r)∧(¬r∨p) であり、p,q,r は同値（p↔q↔r）となる。
モデル例：p=q=r=true（または p=q=r=false）。

(b) 充足可能。
(p∨q∨r) により少なくとも1つ真。残り3式により任意の2つが同時に真になれない。
従って「ちょうど1つ真」。
モデル例：p=true,q=false,r=false（他に q のみ真、r のみ真も可）。

練習問題9.2（基礎2）

元問題: 第9章問題2（基礎）

解答種別: 詳細解答

問題: 以下を前束標準形（prenex normal form）に変換せよ。

(a) \(\forall x\,(P(x) \to \exists y\, Q(x, y)) \land \exists z\, R(z)\)
(b) ¬∀x∃y(P(x, y) ↔ ¬∃z Q(y, z))

解答（同値変形の一例）:

(a)

\(P(x) \to \exists y\,Q(x,y) \equiv \lnot P(x) \lor \exists y\,Q(x,y)\)
y は ¬P(x) に自由出現しないので、¬P(x) ∨ ∃yQ(x,y) ≡ ∃y(¬P(x) ∨ Q(x,y))
よって ∀x∃y(¬P(x) ∨ Q(x,y)) ∧ ∃zR(z)
z は左項に自由出現しないので、全体 ≡ ∀x∃y∃z( (¬P(x) ∨ Q(x,y)) ∧ R(z) )

前束標準形の例：
∴ ∀x ∃y ∃z [ (¬P(x) ∨ Q(x,y)) ∧ R(z) ]

(b)

¬∀x φ ≡ ∃x ¬φ、¬∃y ψ ≡ ∀y ¬ψ より
¬∀x∃y(…) ≡ ∃x∀y ¬(…)
¬(A↔B) ≡ (A∧¬B) ∨ (¬A∧B) を用いる。A=P(x,y)、B=¬∃zQ(y,z)。
すると ¬B=∃zQ(y,z)、B=∀z¬Q(y,z)。
変数名を分離（z1,z2）し、量化子を外に出す： (P(x,y) ∧ ∃z1 Q(y,z1)) ∨ (¬P(x,y) ∧ ∀z2 ¬Q(y,z2)) ≡ (∃z1 (P(x,y) ∧ Q(y,z1))) ∨ (∀z2 (¬P(x,y) ∧ ¬Q(y,z2))) ≡ ∃z1 ∀z2 [ (P(x,y) ∧ Q(y,z1)) ∨ (¬P(x,y) ∧ ¬Q(y,z2)) ]

前束標準形の例：
∴ ∃x ∀y ∃z1 ∀z2 [ (P(x,y) ∧ Q(y,z1)) ∨ (¬P(x,y) ∧ ¬Q(y,z2)) ]

練習問題9.3（基礎3）

元問題: 第9章問題3（基礎）

解答種別: 詳細解答

問題: Hoare 三つ組を証明せよ。

(a) {x = n ∧ n は 0 以上} y := 1; while x > 0 do (y := y * x; x := x - 1) {y = n!}
(b) {true} x := a; y := b; z := x; x := y; y := z {x = b ∧ y = a}

解答（不変条件の例）:

(a) ループ不変条件 I を

I: \(y \cdot x! = n!\) かつ x は 0 以上と置く。初期（y=1,x=n）で I 成立。
反復で \(y^{\prime} = y \cdot x\)、\(x^{\prime} = x - 1\) なので \(y^{\prime} \cdot (x^{\prime})! = y \cdot x \cdot (x-1)! = y \cdot x! = n!\) が保たれる。
終了時 x=0 より \(y\cdot 0! = n!\)、従って y=n!。

(b) 逐次代入の評価で追う：
z:=x により z=a、x:=y により x=b、y:=z により y=a。よって事後条件成立。

練習問題9.4（基礎4）

元問題: 第9章問題4（基礎）

解答種別: 詳細解答

問題: CTL 式 \(AG(\text{request} \to \text{AF}\ \text{grant})\) の意味を説明し、満たす/満たさない遷移系例を示せ。

解答:

意味：すべての実行において、任意時点で request が真なら、将来必ず grant が真になる（要求は必ずいずれ許可される）。

満たす例：request 状態から必ず grant 状態へ遷移する（grant へ到達不能なループが存在しない）。
満たさない例：request=true, grant=false の自己ループ（要求が永続して許可されない実行が存在）。

練習問題9.5（発展5）

元問題: 第9章問題5（発展）

解答種別: 詳細解答

問題: Resolution の健全性と完全性を述べ、Horn節に対する効率的戦略を説明せよ。

解答（概略）:

(a) 健全性： (A∨p),(B∨¬p) ⊨ (A∨B) が成り立つため、解消規則は意味論的含意を保つ。
完全性（反駁完全性）：CNF が充足不能なら、有限回の解消で空節を導出できる。

(b) Horn節は unit resolution/前向き推論で十分：
Horn-SAT は線形時間で解け、含意の伝播で矛盾（⊥）を検出できる。

練習問題9.6（発展6）

元問題: 第9章問題6（発展）

解答種別: 詳細解答

問題: LTL 式から等価な Büchi オートマトンへの変換と複雑性を述べよ。

解答（概要）:

(a) 典型手順：LTL 式 φ の否定 ¬φ を tableau で展開し、満たすべき部分式集合を状態として Büchi オートマトン A_{¬φ} を構成し、システムと直積して受理実行の有無を判定する。
(b) 複雑性：式サイズ n に対し状態数は一般に 2^{O(n)}、モデル検査は概ね O(\(\lvert M\rvert\)·2^{O(n)}) の枠組みで議論される。

練習問題9.7（発展7）

元問題: 第9章問題7（発展）

解答種別: 詳細解答

問題: 分離論理を用いて連結リスト反転を検証せよ。

解答（スケッチ）:

リスト述語 list(x,S) を用い、典型的に

事前：{ list(x,S) }
事後：{ list(x,rev(S)) }

反転（prev,curr）ループの不変条件例：

I: list(prev, rev(prefix)) * list(curr, suffix) かつ S = prefix ⧺ suffix
（* はヒープ領域の分離、⧺ は連結）各反復で curr 先頭を suffix から取り出して prev 側に付け替えれば、不変条件が維持される。

練習問題9.8（発展8）

元問題: 第9章問題8（発展）

解答種別: 詳細解答

問題: Curry-Howard 対応を説明し、具体例で示せ。

解答:

代表対応：

\(A \to B\) ↔ 関数型 \(A \to B\)
A∧B ↔ 積型 A×B
A∨B ↔ 和型 A+B

例：\(A \land B \to B \land A\) に対応するプログラム（swap）
swap(a,b)=(b,a) は「ペアの入れ替え」を実装すると同時に、命題の証明でもある。

練習問題9.9（探究9）

元問題: 第9章問題9（探究）

解答種別: 調査ガイド

問題: 並行プログラム検証手法を調査し、共有メモリ/メッセージパッシングを比較せよ。

解答（調査ガイド）:

比較軸：

仕様（安全性/活性（liveness）、線形化可能性、逐次一貫性）
手法（モデル検査、抽象解釈、証明支援、型/効果）
実装前提（メモリモデル、再送/順序保証、故障モデル）

共有メモリは線形化点・データ競合・メモリ順序が論点になりやすい。メッセージパッシングはプロトコル（順序、タイムアウト、再送）を含めて検証対象が広がる。

練習問題9.10（探究10）

元問題: 第9章問題10（探究）

解答種別: 調査ガイド

問題: 確率的モデル検査を調査し、PCTL と検証アルゴリズムを説明せよ。

解答（調査ガイド）:

対象：DTMC/CTMC/MDP 等
PCTL 例：P_{\ge p}[F φ]（確率 p 以上で最終的に φ）
アルゴリズム：確率到達の計算（線形方程式/反復法）、MDP では最小/最大確率の最適化

代表ツール：PRISM。

練習問題9.11（探究11）

元問題: 第9章問題11（探究）

解答種別: 調査ガイド

問題: 依存型による検証（Coq/Agda）を調査し、実例を示せ。

解答（調査ガイド）:

例の方向性：

長さ付きベクトル型で境界外アクセスを型で排除する
ソートの正しさ（置換性＋単調性）を「実装＋証明」で提示する

論点：

証明の保守コスト、ライブラリ依存（Coq/Agda/Lean 等）、抽象化レベル。

練習問題9.12（探究12）

元問題: 第9章問題12（探究）

解答種別: 調査ガイド

問題: ハイブリッドシステムの形式的検証を調査し、主要アプローチと課題を述べよ。

解答（調査ガイド）:

アプローチ例：

到達可能性解析（過近似/抽象化、領域分割）
微分不変量・バリア証明
SMT/δ-決定手続き（dReal 等）

課題：

連続状態空間の爆発、保守的近似による偽陽性、パラメータ不確かさの扱い。

第10章: 情報理論

練習問題10.1（基礎1）

元問題: 第10章問題1（基礎）

解答種別: 詳細解答

問題: 以下の分布のエントロピーを計算せよ。

(a) P(X) = {1/2, 1/4, 1/8, 1/8}
(b) 幾何分布：P(X=k)=(1-p)^{k-1}p, k=1,2,…

解答（log は \(\log_2\)）:

(a) \[ \begin{aligned} H(X) &= -\sum p \log p \
&= -\left(\frac{1}{2}\log \frac{1}{2} + \frac{1}{4}\log \frac{1}{4} + \frac{1}{8}\log \frac{1}{8} + \frac{1}{8}\log \frac{1}{8}\right) \
&= \frac{1}{2} \cdot 1 + \frac{1}{4} \cdot 2 + \frac{1}{8} \cdot 3 + \frac{1}{8} \cdot 3 \
&= 1.75\ \text{[bit]}. \end{aligned} \]

(b) \(H(X) = -\sum_{k\ge 1} (1-p)^{k-1}p [log p + (k-1)log(1-p)]\)
= -log p - E[k-1]·log(1-p)
幾何分布の期待値 E[k-1]=(1-p)/p より
∴ \(H(X) = -\log p - \frac{1-p}{p}\log(1-p)\)。

練習問題10.2（基礎2）

元問題: 第10章問題2（基礎）

解答種別: 詳細解答

問題: \(X \to Y \to Z\) が Markov 連鎖のとき、\(I(X;Y \mid Z)+I(X;Z)=I(X;Y)\) を証明せよ。

解答:

連鎖律より

\(I(X;Y,Z) = I(X;Z) + I(X;Y \mid Z)\)
\(I(X;Y,Z) = I(X;Y) + I(X;Z \mid Y)\)

Markov 連鎖 \(X \to Y \to Z\) では \(I(X;Z \mid Y)=0\)。従って \(I(X;Y,Z)=I(X;Y)\)。
両式を合わせて \(I(X;Y)=I(X;Z)+I(X;Y \mid Z)\)。

練習問題10.3（基礎3）

元問題: 第10章問題3（基礎）

解答種別: 詳細解答

問題: 二元対称通信路（クロスオーバー確率 0.1）で入力が一様のときの相互情報量を求めよ。

解答:

BSC(p) の一様入力に対して I(X;Y)=1-h(p)。
p=0.1 の二値エントロピー h(0.1)≈0.4689956 より
∴ I(X;Y) ≈ 0.5310 [bit/記号]。

練習問題10.4（基礎4）

元問題: 第10章問題4（基礎）

解答種別: 詳細解答

問題: {a:0.5, b:0.25, c:0.125, d:0.125} の Huffman 符号を構成し平均符号長を求めよ。

解答（一例）:

0.125 と 0.125 を結合して 0.25、0.25 と 0.25 を結合して 0.5、0.5 と 0.5 を結合して 1。

符号例：

a: 0
b: 10
c: 110
d: 111

平均符号長 L = 0.5·1 + 0.25·2 + 0.125·3 + 0.125·3 = 1.75。

練習問題10.5（発展5）

元問題: 第10章問題5（発展）

解答種別: 詳細解答

問題: Fano の不等式を証明し、逆定理への応用を説明せよ。

解答（要点）:

誤り指示変数 E（復号誤りなら1）を導入し、条件付きエントロピーを E で分解することで \(H(X \mid Y) \le h(P_e) + P_e \cdot \log(\lvert X\rvert - 1)\) （P_e は誤り確率）が得られる。
この不等式から、\(H(X \mid Y)\) が小さい（=復号が良い）ためには P_e が小さい必要があることが分かり、チャネル容量の逆定理では「R > C なら \(P_e \to 0\) は不可能」を示す際の上界として用いる。

練習問題10.6（発展6）

元問題: 第10章問題6（発展）

解答種別: 詳細解答

問題: 弱型/強型と AEP を説明し、AEP を証明せよ。

解答（概要）:

弱型（weakly typical）：

A^{(n)}_ε = {x^n : \(\lvert -(1/n)\log p(x^n) - H(X)\rvert \le \varepsilon\)}

強型（strongly typical）：

経験分布（型）が真の分布に ε 近い（記号頻度が各記号で収束）

AEP（漸近等分割性）：

i.i.d. のとき、-(1/n)log p(X^n) は H(X) に収束する（確率1）

証明スケッチ：

\(-\log p(X^n) = \sum_{i=1}^{n} -\log p(X_i)\)。右辺は独立同分布で期待値が \(H(X)\)。
大数の法則により \(\frac{1}{n}\sum_{i=1}^{n} -\log p(X_i)\) は \(H(X)\) に収束する。

練習問題10.7（発展7）

元問題: 第10章問題7（発展）

解答種別: 詳細解答

問題: Slepian-Wolf の定理を説明し、達成可能領域を特徴付けよ。

解答:

相関のある情報源 (X,Y) を別々に符号化し、共同で復号する分散符号化の基本定理。
達成可能なレート領域（無損失）は：

\(R_X \ge H(X \mid Y)\)
\(R_Y \ge H(Y \mid X)\)
\(R_X + R_Y \ge H(X,Y)\)

練習問題10.8（発展8）

元問題: 第10章問題8（発展）

解答種別: 詳細解答

問題: ネットワーク符号化について、(a) 最大流最小カットとの関係 (b) 線形符号の十分性を述べよ。

解答（概要）:

(a) マルチキャストの設定では、受信者集合への同時伝送率は各受信者への最小カットで上界付けされ、ネットワーク符号化によりこの上界（min-cut）を達成可能となる。
(b) 有限体上の線形結合（線形ネットワーク符号）で容量達成が可能（代表的にランダム線形符号で高確率に達成）。

練習問題10.9（探究9）

元問題: 第10章問題9（探究）

解答種別: 調査ガイド

問題: 量子情報理論を調査し、von Neumann エントロピーと古典エントロピーの違いを述べよ。

解答（調査ガイド）:

von Neumann エントロピー：S(ρ) = -Tr(ρ log ρ)（密度行列 ρ）
古典分布の特別な場合（ρ が対角）に Shannon エントロピーと一致
量子ではエンタングルメント、測定基底依存、条件付きエントロピーが負になり得る等の現象がある

練習問題10.10（探究10）

元問題: 第10章問題10（探究）

解答種別: 調査ガイド

問題: Kolmogorov 複雑性と Shannon エントロピーの関係を述べよ。

解答（調査ガイド）:

Kolmogorov 複雑性 K(x)：x を生成する最短プログラム長（非計算可能）
Shannon エントロピーは「分布に対する平均符号長」の最小値
i.i.d. 生成では典型列に対し K(x^n) ≈ nH(X)（平均的には圧縮可能性が一致するが、個別列の最短記述は分布とは独立に揺らぐ）

練習問題10.11（探究11）

元問題: 第10章問題11（探究）

解答種別: 調査ガイド

問題: 極符号（Polar codes）を調査し、通信路分極と容量達成性を説明せよ。

解答（調査ガイド）:

通信路分極：N=2^n 個の合成チャネルが「ほぼ完全」か「ほぼ無価値」に分極する
良いチャネルに情報ビット、悪いチャネルに凍結ビットを割り当てることで容量達成
計算量：符号化/復号が O(N log N)（SC/SC-List 等）

練習問題10.12（探究12）

元問題: 第10章問題12（探究）

解答種別: 調査ガイド

問題: 深層学習の情報理論的解析（情報ボトルネック等）を調査し、応用例を示せ。

解答（調査ガイド）:

論点：

表現 T に対し I(X;T) を抑えつつ I(T;Y) を高める、という目的関数としての解釈
連続値の相互情報量推定の難しさ（推定器バイアス、ノイズ仮定）
正則化（dropout 等）や一般化議論との接続

応用例：

低次元表現学習、蒸留、圧縮、ロバスト性解析など。

第11章: 暗号理論の数学的基礎

練習問題11.1（基礎1）

元問題: 第11章問題1（基礎）

解答種別: 詳細解答

問題: シーザー暗号、Vigenère暗号、ワンタイムパッドの安全性を評価せよ。

解答:

(a) シーザー暗号：鍵空間が小さく（25程度）、総当たり・頻度分析で容易に解読可能。現代運用では不適。
(b) Vigenère暗号：多表式暗号で単純な頻度分析には耐えるが、鍵長推定（Kasiski法等）+ 分割後の頻度分析で破れる。現代運用では不適。
(c) ワンタイムパッド：鍵が真に一様ランダムで平文長と同じ長さ、かつ再利用しないなら情報理論的安全（完全秘匿）を満たす。鍵再利用・乱数不備で破綻する。

練習問題11.2（基礎2）

元問題: 第11章問題2（基礎）

解答種別: 詳細解答

問題: RSA で e=3 を使う場合の脆弱性と対策を述べよ。

解答（代表例）:

脆弱性：

パディングなし/不適切なパディングで小さい平文 m に対し c=m^3 mod N が「mod を跨がず」c=m^3 となると、整数の立方根で復元できる
同一平文を異なる受信者へ送ると Hastad の broadcast attack が成立し得る（e が小さいほど危険）

対策：

OAEP 等の安全なパディングを使用する（RSAES-OAEP）
実務上は e=65537 が一般的（小さいが安全設計・実装互換性が高い）

練習問題11.3（基礎3）

元問題: 第11章問題3（基礎）

解答種別: 詳細解答

問題: ElGamal で同じ乱数 r を再利用した場合の脆弱性を示せ。

解答:

暗号文が (c1,c2)=(g^r, m·y^r) のとき、同じ r を2回使うと c1 が一致する。
2つの暗号文 (c1, m1·y^r), (c1, m2·y^r) から (m1·y^r)/(m2·y^r) = m1/m2 が得られ、平文間の比が漏えいする。片方の平文が既知なら他方も復元できる。

練習問題11.4（基礎4）

元問題: 第11章問題4（基礎）

解答種別: 詳細解答

問題: n ビットハッシュの衝突を 50% で見つける試行回数を求めよ。

解答:

誕生日パラドックスより、必要試行回数は概ね
≈ 1.1774 · 2^{n/2}
（√(π/2)·2^{n/2}）程度である。

練習問題11.5（発展5）

元問題: 第11章問題5（発展）

解答種別: 詳細解答

問題: DDH 仮定から CDH 仮定が導かれることを示し、逆が一般に成り立たないことを述べよ。

解答:

示すべきは「CDH が解けるなら DDH も解ける」なので、その対偶として「DDH が困難なら CDH も困難」と言える。

CDH ソルバ A があると仮定し、DDH 判別器 D を構成する：

入力 (g^a, g^b, g^c) を受け取る
A で g^{ab} を計算し、g^c と一致するか判定する一致なら「DDHタプル」、不一致なら「ランダム」と判定できる。

従って DDH-hard なら CDH-hard。
逆（CDH-hard ならば DDH-hard）は一般に成り立たない（例：ペアリング可能な群では DDH が容易でも CDH は困難な設計があり得る）。

練習問題11.6（発展6）

元問題: 第11章問題6（発展）

解答種別: 詳細解答

問題: Σプロトコルが特殊健全性を持つとき知識抽出器を構成できることを示せ。

解答（概要）:

特殊健全性：同一コミットメント \(a\) に対し、異なるチャレンジ \(e \ne e^{\prime}\) で受理される2つの転写 \((a,e,z)\), \((a,e^{\prime},z^{\prime})\) から証人 \(w\) を効率的に計算できる性質。

知識抽出器の基本形：

悪意ある証明者を巻き戻し（rewind）して同じ \(a\) を再利用させ、異なる \(e, e^{\prime}\) を引き出す
2転写を特殊健全性のアルゴリズムに入力し w を復元する

練習問題11.7（発展7）

元問題: 第11章問題7（発展）

解答種別: 詳細解答

問題: CRT を用いた RSA 復号アルゴリズムと、計算量削減を評価せよ。

解答:

(a) CRT 復号（概略）：

dp = d mod (p-1), dq = d mod (q-1)
m_p = c^{dp} mod p, m_q = c^{dq} mod q
Garner法等で m を mod N=pq に合成

(b) 評価：

mod N の冪剰余（nビット）を2回の mod p, mod q（n/2ビット）へ分解
乗算コストが概ねビット長の2〜3乗で効くため、理想化すると約 3〜4倍程度の高速化が期待できる（実装・最適化に依存）。

練習問題11.8（発展8）

元問題: 第11章問題8（発展）

解答種別: 詳細解答

問題: 双線形ペアリングの定義と性質、IDベース暗号への応用を説明せよ。

解答:

双線形ペアリング \(e: G_1 \times G_2 \to G_T\) の代表性質：

双線形性：e(g1^a, g2^b) = e(g1,g2)^{ab}
非退化性：e(g1,g2) ≠ 1
効率的計算可能性

応用（例：Boneh-Franklin IBE）：

ID（メールアドレス等）を公開鍵として扱い、マスター秘密鍵で秘密鍵を発行
ペアリングにより鍵交換/暗号化に必要な共有値を構成する。

練習問題11.9（探究9）

元問題: 第11章問題9（探究）

解答種別: 調査ガイド

問題: PQC（NIST FIPS 203/204/205）の目的（KEM/署名）と基盤（格子/ハッシュ）を説明せよ。

解答（調査ガイド）:

FIPS 203: ML-KEM（鍵カプセル化）。module-lattice 系の困難性に基づく
FIPS 204: ML-DSA（署名）。module-lattice 系
FIPS 205: SLH-DSA（署名）。ステートレスなハッシュベース署名

比較軸：

鍵サイズ/署名サイズ、性能、実装リスク（サイドチャネル耐性）、移行（ハイブリッド、crypto-agility）。

練習問題11.10（探究10）

元問題: 第11章問題10（探究）

解答種別: 調査ガイド

問題: ブロックチェーンで使用される暗号技術（PoW、Merkle木、BLS署名）を論ぜよ。

解答（調査ガイド）:

PoW：ハッシュ計算でコストを課し、Sybil耐性/合意形成を補助
Merkle木：大量データのコミットメント（部分検証が可能、軽量クライアントで有効）
BLS署名：署名集約（aggregation）が可能で、コンセンサス/投票の帯域削減に寄与（ペアリング前提）。

練習問題11.11（探究11）

元問題: 第11章問題11（探究）

解答種別: 調査ガイド

問題: 差分プライバシーを調査し、暗号理論との関係と応用例を述べよ。

解答（調査ガイド）:

(ε,δ)-DP：隣接データ集合で出力分布が近い（識別困難性）
暗号の indistinguishability と形式が類似する一方、目的は「統計解析結果の漏えい抑制」
応用：統計公開、機械学習（DP-SGD）、テレメトリ等。

練習問題11.12（探究12）

元問題: 第11章問題12（探究）

解答種別: 調査ガイド

問題: 完全準同型暗号（FHE）を調査し、ブートストラッピングと効率化を述べよ。

解答（調査ガイド）:

格子ベース（BGV/BFV/CKKS, TFHE 等）が主流
ブートストラッピング：暗号文ノイズを復元（自己暗号化/評価）して任意回の計算を可能にする
効率化：回路設計、パラメータ最適化、SIMD化、鍵スイッチング最適化、専用方式（TFHEの高速化等）。

第12章: 並行計算の理論

練習問題12.1（基礎1）

元問題: 第12章問題1（基礎）

解答種別: 詳細解答

問題: 共有変数 x=0、P1: x=x+1; x=x+1、P2: x=x*2 が交互実行されるとき、最終的な x の値として可能なものを全て求めよ（各文はアトミックとする）。

解答:

3操作（+1,+1,*2）の順序だけを考えればよい。

操作列「×2, +1, +1」を順に適用すると、値は 0, 0, 1, 2 と変化する（最終 2）
操作列「+1, ×2, +1」を順に適用すると、値は 0, 1, 2, 3 と変化する（最終 3）
操作列「+1, +1, ×2」を順に適用すると、値は 0, 1, 2, 4 と変化する（最終 4）

従って可能な最終値は {2,3,4}。

練習問題12.2（基礎2）

元問題: 第12章問題2（基礎）

解答種別: 詳細解答

問題: CCS で双模倣等価性を判定せよ。

(a) a.b.0 + a.c.0 と a.(b.0 + c.0)
(b) (a.0 | b.0)\{a} と b.0

解答（強双模倣の直観）:

(a) 同値ではない。左辺は最初の \(a\) の直後に \(b\) だけ可能な状態、または \(c\) だけ可能な状態へ分岐する。一方、右辺は \(a\) の後に \(b\) と \(c\) の両方を選べる状態へ進む。したがって、左辺の \(a\) 遷移の一方を右辺の唯一の \(a\) 遷移で模倣すると、遷移後状態の可能アクションが一致しない。 (b) 同値。制限 \{a} により a は外部へ出せず（相手がいないため内部同期もしない）、残る観測可能な行動は b のみで b.0 と同じ振る舞いになる。

練習問題12.3（基礎3）

元問題: 第12章問題3（基礎）

解答種別: 詳細解答

問題: 哲学者の食事問題を Petri ネットでモデル化し、デッドロックが起こることを示せ。

解答（典型モデル）:

モデル例（5人の場合）：

フォーク i を place Fork_i（初期トークン1）
哲学者 i の状態を place Think_i, Hungry_i, Eat_i 等で表す
遷移 TakeLeft_i: Think_i と Fork_i からトークンを取り Hungry_i へ
遷移 TakeRight_i: Hungry_i と Fork_{i+1} からトークンを取り Eat_i へ
遷移 Release_i: Eat_i から Think_i へ戻し、Fork_i と Fork_{i+1} にトークンを返す

全員が左フォークを取った状態（Fork_i が全て0）では、いずれの TakeRight_i も有効化されず停止するためデッドロック（マーキングが行き詰まり）となる。

練習問題12.4（基礎4）

元問題: 第12章問題4（基礎）

解答種別: 詳細解答

問題: n プロセスのベーカリーアルゴリズムが相互排除を満たすことを証明せよ。

解答:

証明の前提と区間

第12章の擬似コードを、故障しない共有メモリ上の逐次一貫性（sequential consistency, SC）を満たす抽象実行として解釈する。すなわち、各プロセスの操作はプログラム順序を保ち、全プロセスの共有変数の読取り・書込みは、その順序と両立する単一の全順序で観測される。特に、number[i] の書込み（2行目）は choosing[i] = false の書込み（3行目）より先に可視になる。ただし、2行目の最大値計算全体を不可分とは仮定しないため、選択が重なった2プロセスが同じ番号を取る場合もある。プロセス i は3行目から6行目まで自分の number[i] を変更しない。

弱メモリ上の実装では、この公開順序をrelease/acquireなどで別途保証する必要がある。Lamportの原論文は重なったregister読取りやプロセス故障について、本文の抽象化より広いモデルを扱うが、ここでは第12章に記載したアルゴリズムのSC下での安全性だけを証明する。

doorway（番号選択区間）: 1行目で choosing[i] = true としてから、3行目で choosing[i] = false とするまで。
bakery（待機・実行区間）: doorwayを出て正の number[i] を保持してから、6行目で number[i] = 0 とするまで。4行目の待機と5行目のクリティカルセクション（CS）を含む。

正の番号とプロセスIDの組 L_i = (number[i], i) を、本文どおり辞書式順序で比較する。この順序は異なる組の間で推移的かつ非対称な厳密全順序である。

不変条件

不変条件: プロセス i がCSにいて、別のプロセス j がbakeryにいるなら、L_i < L_j である。

i が4行目で j に対する最初の待機を通過した時点を基準に、j の現在のdoorwayとの順序で場合分けする。

j が現在のdoorwayを開始済みなら、i は choosing[j] = false になるまで待つため、j の番号確定後に進む。その後も j はbakeryにいて number[j] > 0 を保つので、i が2番目の待機を通過できたなら L_i < L_j でなければならない。
j が現在のdoorwayをまだ開始していないなら、i はすでに正の number[i] を保持している。j が後から2行目で最大値を調べる間、その値は6行目まで安定しているため、number[j] > number[i] となり、やはり L_i < L_j である。j が i の2つの待機の間に1行目を実行する競合もこの場合に含まれる。

doorwayが重なって同じ番号を取った場合は1の場合となり、プロセスIDが同じ番号同士を一意に順序付ける。したがって、どの場合にも不変条件が成立する。

相互排除

異なるプロセス i と j が同時にCSにいると仮定する。両者ともbakeryにいるため、上の不変条件を i から j へ適用すると L_i < L_j、j から i へ適用すると L_j < L_i を得る。これは辞書式順序の非対称性に反する。したがって同時入場の仮定が誤りであり、相互排除が成り立つ。

`choosing[]` の役割

choosing[j] は、j が1行目を先に実行して番号選択を開始済みなら、2行目の number[j] が確定するまで i を最初の待機に留める。これにより、i がそのdoorwayの中間状態にある number[j] = 0 を「要求なし」と誤認して進むことを防ぐ。

ただし、i が choosing[j] = false を読んだ直後、2つの待機の間に j が1行目を実行する競合では、i が古い number[j] = 0 を読んで進む場合がある。この場合は安全性を損なわない。i はすでに正の番号を保持しており、後から番号を選ぶ j がその値を最大値計算に含めて number[j] > number[i] とするため、先の不変条件の第2の場合になる。したがって、choosing[]によるdoorway完了の引渡しと、後発選択者が既存番号より大きい番号を取る規則の組合せが、中間状態の観測を安全に処理する。

2プロセスのinterleaving

P0 と P1 が同時に要求し、両者が2行目で同じ最大値0を読んで、ともに番号1を書いた場合を追う。

P0 と P1 は1行目でそれぞれ choosing[0] = true、choosing[1] = true とする。
両者は2行目で number[0] = 1、number[1] = 1 とし、3行目でそれぞれの choosing を false にする。
P0 は4行目で choosing[1] = false を確認する。(number[0], 0) = (1, 0) < (1, 1) = (number[1], 1) なので2番目の待機も通過し、5行目のCSへ入る。
P1 も choosing[0] = false を確認するが、number[0] != 0 かつ (1, 1) < (1, 0) は偽なので、4行目で待つ。
P0 がCSを出て6行目で number[0] = 0 とした後に限り、P1 は待機を通過できる。

番号が1と2に分かれた場合も、小さい組を持つ側だけが先に進み、もう一方はその番号が0へ戻るまで待つ。以上は安全性である相互排除の証明であり、starvation freedomやbounded waitingの完全証明ではない。

一次資料: Leslie Lamport, A New Solution of Dijkstra’s Concurrent Programming Problem。

練習問題12.5（発展5）

元問題: 第12章問題5（発展）

解答種別: 詳細解答

問題: Lamport 時計の定義と性質、ベクトル時計との違いを述べよ。

解答:

Lamport 時計：

各イベントで C := C+1
メッセージ送信でタイムスタンプを添付
受信で C := max(C, ts)+1

性質：

事象の因果順 \(a \to b\) なら C(a) < C(b)（逆は一般に成り立たない）

ベクトル時計：

各プロセスがベクトル V を持ち、自分の成分をインクリメントし、受信時に成分ごとに max を取る
\(a \to b\) なら V(a) < V(b)（成分ごとの \(\le\) かつどこか <）、並行性（incomparable）も識別可能。

練習問題12.6（発展6）

元問題: 第12章問題6（発展）

解答種別: 詳細解答

問題: コンセンサス数について、(a) 各同期プリミティブのコンセンサス数 (b) 階層定理を説明せよ。

解答（代表例）:

(a) 代表的な同期プリミティブのコンセンサス数：

read/write レジスタ：1
test-and-set / swap / fetch-and-add：2（代表例）
compare-and-swap（CAS）/ LL-SC：∞（任意人数の wait-free コンセンサスが実装可能）

(b) 階層定理（Herlihy）：

コンセンサス数 n のオブジェクトだけでは、n を超える人数の wait-free コンセンサスを実装できない
従って同期原語は「実現できる合意人数」により階層化される。

練習問題12.7（発展7）

元問題: 第12章問題7（発展）

解答種別: 詳細解答

問題: Michael-Scott ロックフリーキューを説明し、ABA問題と対策を述べよ。

解答（概要）:

Michael-Scott キュー：

ダミーノードを先頭に置き、Head/Tail ポインタを CAS で更新
Enqueue は Tail.next を CAS し、必要に応じて Tail を前進
Dequeue は Head を CAS し、空判定や Tail 遅延を補正する

ABA問題：

共有ポインタ値が \(A \to B \to A\) と変化すると、CAS では「変化なし」に見えて誤判定する

対策例：

タグ付きポインタ（version/counter を付与して \(A\) と \(A^{\prime}\) を区別）
Hazard pointer / epoch-based reclamation による安全なメモリ回収（解放済み再利用を抑止）

練習問題12.8（発展8）

元問題: 第12章問題8（発展）

解答種別: 詳細解答

問題: 弱メモリモデルについて (a) TSO と PSO (b) メモリバリアの必要性を述べよ。

解答:

(a) TSO（Total Store Order）：

各CPUに store buffer があり、store-load の順序が観測上入れ替わり得る
PSO（Partial Store Order）：
store-store も異なるアドレス間で入れ替わり得るなど、TSOより緩い

(b) 必要性（例）：

メッセージパッシングで data=...; flag=1; と書いたつもりでも、受信側が flag=1 を見た時点で data が可視でない可能性がある
従って release/acquire あるいは fence を挿入して可視性/順序を保証する必要がある。

練習問題12.9（探究9）

元問題: 第12章問題9（探究）

解答種別: 調査ガイド

問題: ブロックチェーンの合意（PoW/PoS/PBFT）を比較せよ。

解答（調査ガイド）:

比較軸：

故障モデル（ビザンチン/クラッシュ）、最終性（確率的/決定的）、スループット/レイテンシ
分散性（参加コスト）、検閲耐性、経済的インセンティブ設計

概略：

PoW：確率的最終性、エネルギーコスト、参加容易
PoS：資本を担保に、最終性や効率を改善する設計が多い
PBFT：決定的最終性、参加者数が増えると通信コストが増大

練習問題12.10（探究10）

元問題: 第12章問題10（探究）

解答種別: 調査ガイド

問題: トランザクショナルメモリ（STM/HTM）を比較せよ。

解答（調査ガイド）:

STM：汎用だがオーバーヘッド（ログ/検証/リトライ）
HTM：高速だがハード制約（容量、I/O不可、フォールバック必要）
比較軸：競合率、再試行頻度、フォールバック時の性能、プログラミングモデル。

練習問題12.11（探究11）

元問題: 第12章問題11（探究）

解答種別: 調査ガイド

問題: アクターモデルと共有メモリモデルを比較し、実装例を述べよ。

解答（調査ガイド）:

アクター：状態はアクター内に閉じ、非同期メッセージで相互作用（データ競合を構造的に回避）
共有メモリ：共有状態をロック/アトミックで保護（同期設計が中心）

実装例：

Erlang/Elixir、Akka（JVM）等。

練習問題12.12（探究12）

元問題: 第12章問題12（探究）

解答種別: 調査ガイド

問題: TLA+、SPIN、NuSMV などを調査し、産業界の応用例を示せ。

解答（調査ガイド）:

例：

TLA+：分散システムの仕様検証（整合性、リーダ選出、リトライ設計等）
SPIN：プロトコル/並行アルゴリズムのモデル検査（Promela）
NuSMV：CTL/LTL によるモデル検査（ハードウェア/制御系）

応用例は「対象システム」「安全性/活性（liveness）仕様」「状態爆発対策」「検証結果のフィードバック」を含めて記述すると整理しやすい。

本付録の解答は、定義・定理の理解を前提に、証明の骨子、アルゴリズム設計、計算量評価までを一貫して確認できるよう構成しています。必要に応じて各章本文・用語集も参照してください。

付録C: 練習問題解答

この付録の使い方

章別クイックナビ

Part I: 数学的基礎

Part II: 計算理論

Part III: 高度なトピック

Part IV: 応用理論

解法パターン索引

証明・反証の型

計算理論・還元の型

解析・設計の型

応用理論でよく使う型

第1章: 数学的基礎

練習問題1.1 集合演算

練習問題1.2 関数の性質

練習問題1.3 数学的帰納法

第2章: 計算理論の基礎

練習問題2.1 チューリング機械の設計

練習問題2.2 計算可能性

第3章: 形式言語とオートマトン理論

練習問題3.1 正規言語の証明

練習問題3.2 文脈自由文法

練習問題3.3 ポンピング補題

練習問題3.4 Myhill–Nerode による最小DFA

練習問題3.5 Myhill–Nerode による非正規性

第4章: 計算可能性

練習問題4.1 停止問題

練習問題4.2 Riceの定理

練習問題4.3 REGULAR_TM の非決定可能性（Rice）

練習問題4.4 固定語包含性 CONTAINS_{w_0} の非決定可能性（Rice）

練習問題4.5 FINITE_TM の非決定可能性（Rice）

練習問題4.6 COFINITE_TM の非決定可能性（Rice）

練習問題4.7 還元テンプレ（多対一）適用の概略

解答の骨子

第5章: 計算複雑性理論

練習問題5.1 複雑性クラスの関係

練習問題5.2 NP完全性の証明

練習問題5.3 3-SAT から VERTEX-COVER へのサイズ管理

練習問題5.4 Cook–Levin のサイズ管理（概算）

1. 計算表（tableau）の導入

2. 変数

3. 論理式の各成分

4. 正当性

5. サイズ評価

練習問題5.5 CLIQUE から VERTEX-COVER へのサイズ変換

第6章: アルゴリズムの数学的解析

練習問題6.1 Master定理

練習問題6.2 動的計画法の設計

漸化式

アルゴリズム

正当性

計算量

練習問題6.3 置換法（不均等分割）

第7章: データ構造の理論

練習問題7.1（基礎1）

練習問題7.2（基礎2）

練習問題7.3（基礎3）

練習問題7.4（基礎4）

練習問題7.5（発展5）

練習問題7.6（発展6）

練習問題7.7（発展7）

練習問題7.8（発展8）

練習問題7.9（探究9）

練習問題7.10（探究10）

練習問題7.11（探究11）

練習問題7.12（探究12）

練習問題7.13（実装13）

練習問題7.14（実装14）

練習問題7.15（実装15）

第8章: グラフ理論とネットワーク

練習問題8.1（基礎1）

練習問題8.2（基礎2）

練習問題8.3（基礎3）

練習問題8.4（基礎4）

練習問題8.5（発展5）

前提と構成

cutからdual pathへ

dual pathからcutへ

容量と重みの一致

4-cycleでの手計算