付録C: 練習問題解答

本書の各章末に掲載された練習問題の詳細な解答と解説を示します。

注: 本付録では第1〜12章の章末問題の解答を収録しています。

• 「探究課題」は唯一の正解がないため、調査の観点・比較軸・アウトプット例を「回答」として提示します。
• 「実装課題」は参照実装/テストを併記する場合があります（必要要件は各節に記載）。

第1章: 数学的基礎

練習問題1.1 集合演算

問題: A = {1, 2, 3, 4}, B = {3, 4, 5, 6}に対して、以下を求めよ。 (a) A ∪ B (b) A ∩ B (c) A \ B (d) B \ A (e) A ⊕ B（対称差）

解答: (a) A ∪ B = {1, 2, 3, 4, 5, 6} (b) A ∩ B = {3, 4} (c) A \ B = {1, 2} (d) B \ A = {5, 6} (e) A ⊕ B = (A \ B) ∪ (B \ A) = {1, 2, 5, 6}

解説: 対称差A ⊕ Bは、AとBのいずれか一方にのみ属する要素の集合です。

練習問題1.2 関数の性質

問題: f: ℝ → ℝ, f(x) = x² について、以下を示せ。 (a) fは単射ではない (b) fは全射ではない (c) f: ℝ≥0 → ℝ≥0として制限すれば全単射である

解答:

(a) fは単射ではない

証明: 単射でないことを示すには、f(a) = f(b)かつa ≠ bとなる例を見つければよい。 f(2) = 4, f(-2) = 4であり、2 ≠ -2なので、fは単射ではない。□

(b) fは全射ではない

証明: 全射でないことを示すには、fの値域に含まれない実数を見つければよい。 任意のx ∈ ℝに対してf(x) = x² ≥ 0なので、例えば-1はfの値域に含まれない。 よってfは全射ではない。□

(c) 制限された関数は全単射

証明: f: ℝ≥0 → ℝ≥0, f(x) = x²について：

単射性: x₁, x₂ ∈ ℝ≥0とし、f(x₁) = f(x₂)とする。 x₁² = x₂²であり、x₁, x₂ ≥ 0なので、x₁ = x₂。よって単射。

全射性: 任意のy ∈ ℝ≥0に対して、x = √y ∈ ℝ≥0とすると、 f(x) = (√y)² = yなので全射。

よって制限された関数は全単射である。□

練習問題1.3 数学的帰納法

問題: 数学的帰納法を用いて、以下を証明せよ。 ∀n ∈ ℕ, ∑_{i=1}^n i = n(n+1)/2

解答:

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

基底ケース (n = 1): 左辺: ∑_{i=1}^1 i = 1 右辺: 1(1+1)/2 = 1 よって成立。

帰納ステップ: n = kで成立すると仮定する。すなわち、 ∑_{i=1}^k i = k(k+1)/2

n = k+1の場合を考える： ∑{i=1}^{k+1} i = ∑{i=1}^k i + (k+1) = k(k+1)/2 + (k+1) （帰納仮定より） = (k+1)[k/2 + 1] = (k+1)(k+2)/2

これはn = k+1での右辺に一致する。

よって数学的帰納法により、すべての自然数nに対して成立する。□

第2章: 計算理論の基礎

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

問題: 文字列w ∈ {0,1}*に対して、ww（wを2回連結した文字列）を認識するチューリング機械を設計せよ。

解答:

解法: 入力が2n文字であることを確認し、前半n文字と後半n文字が一致することを確認する。

アルゴリズム:

1. 入力の長さが偶数であることを確認
2. 最初の文字をマークし、対応する位置（中央より後）の文字と比較
3. 一致すれば次の文字に進む
4. すべての文字が一致すれば受理

チューリング機械M = (Q, Σ, Γ, δ, q₀, qaccept, qreject):

• Q: 状態集合
• Σ = {0, 1}: 入力アルファベット
• Γ = {0, 1, X, Y, ⊔}: テープアルファベット
• q₀: 初期状態
• δ: 遷移関数（詳細な状態遷移表は省略）

主な状態の役割:

• q₀: 開始状態、入力の長さをチェック
• q₁: 前半の文字をマーク
• q₂: 対応する後半の文字を探す
• q₃: 文字の一致をチェック
• qaccept: 受理状態
• qreject: 拒否状態

練習問題2.2 計算可能性

問題: 以下の関数が計算可能であることを証明せよ。 f(n) = 2n if n is even, 3n+1 if n is odd

解答:

証明: チューリング機械によってf(n)を計算できることを示す。

アルゴリズム:

1. 入力nを読む
2. nが偶数か奇数かを判定
3. 偶数の場合: n × 2を計算
4. 奇数の場合: n × 3 + 1を計算
5. 結果を出力

詳細:

偶数判定: nを2で割り、余りが0かどうかをチェック（除算はチューリング機械で実現可能）

乗算の実現: チューリング機械で乗算は実現可能（加算を繰り返す）

加算の実現: チューリング機械で加算は実現可能

すべての構成要素がチューリング機械で実現可能なので、f(n)は計算可能である。□

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

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

解答:

方法1: DFAによる証明

DFA M = (Q, Σ, δ, q₀, F)を構成する：

• Q = {q₀, q₁} （q₀: 偶数個, q₁: 奇数個）
• Σ = {a, b}
• δ(q₀, a) = q₁, δ(q₀, b) = q₀, δ(q₁, a) = q₀, δ(q₁, b) = q₁
• 初期状態: q₀
• 受理状態: F = {q₀}

このDFAはLを認識するので、Lは正規言語である。□

方法2: 正規表現による証明

Lを表す正規表現: b(bbabab)*

この正規表現は：

• 任意個のb
• 0回以上の（任意個のb, a, 任意個のb, a, 任意個のb）の繰り返し

これはaが偶数個（0個を含む）含まれる文字列を正確に表現する。□

練習問題3.2 文脈自由文法

解答:

文脈自由文法G = (V, Σ, R, S):

• V = {S} (非終端記号)
• Σ = {a, b} (終端記号)
• R: 生成規則
  • S → aSb
  • S → ε
• S: 開始記号

導出例:

• n = 0: S ⇒ ε
• n = 1: S ⇒ aSb ⇒ aεb = ab
• n = 2: S ⇒ aSb ⇒ aaSbb ⇒ aaεbb = aabb
• n = 3: S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaaεbbb = aaabbb

正当性: 任意のn ≥ 0に対してaⁿbⁿが生成可能であり、この文法から生成される文字列はすべてこの形式である。□

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

解答:

証明: 文脈自由言語のポンピング補題により、Lが文脈自由言語であると仮定する。

ポンピング長をpとする。文字列s = aᵖbᵖcᵖ ∈ Lを考える。 |s| = 3p ≥ pなので、s = uvxyzと分解でき：

1. vxy

   ≤ p

2. vy

   ≥ 1

3. ∀i ≥ 0, uvⁱxyⁱz ∈ L

条件1により、vxyはaᵖbᵖcᵖの長さp以下の部分文字列である。 したがって、vxyは次のいずれかに含まれる：

• aᵖの一部とbᵖの一部
• bᵖの一部とcᵖの一部
• aᵖ, bᵖ, cᵖのいずれか1つの内部

場合分析:

場合1: vxyがaとbにまたがる場合 v, yがそれぞれa, bのみを含むとすると、uv²xy²zではaとbの個数が増加するが、cの個数は変わらない。よってuv²xy²z ∉ L。

場合2: vxyがbとcにまたがる場合 同様に、uv²xy²zでbとcの個数が増加するが、aの個数は変わらない。よってuv²xy²z ∉ L。

場合3: vxyが1つの文字種のみを含む場合 v, yが同じ文字のみを含むとすると、uv²xy²zではその文字の個数のみが増加し、他の文字の個数は変わらない。よってuv²xy²z ∉ L。

すべての場合で矛盾が生じるため、Lは文脈自由言語ではない。□

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

問題: 章末問題「発展 8.」について、以下を示せ。 (a) L₁ = { w ∈ {a,b}* | w が部分文字列 “aba” を含む } の最小DFAは少なくとも4状態を要する。 (b) L₂ = { w ∈ {0,1}* | #1(w) ≡ 0 (mod 3) かつ最終文字が 0 } の最小DFAは少なくとも6状態を要する。

解答:

(a) 右同値関係 ≡ₗ の同値類が少なくとも 4 つ存在することを示す。 接頭辞集合 S = {ε, a, ab, aba} をとる。 任意の 2 つ異なる接頭辞 x ≠ y ∈ S について、z を適切に選ぶと xz ∈ L₁ かつ yz ∉ L₁（または逆）が成り立つ： 例えば x=ab, y=a のとき z=b で区別できる。したがって 4 個の同値類が必要で、最小DFAは少なくとも 4 状態。

(b) 条件は「1 の個数の剰余 ≡ 0 (mod 3)」と「最終文字が 0」の合成。 右同値類は直積的に分かれ、少なくとも 3（剰余）×2（最終文字）= 6 通りを区別する必要がある。 互いに識別可能性は、末尾に追加する z によって受理/不受理が分かれる例を与えることで示せる。 よって最小DFAは少なくとも 6 状態。□

補足: 最小DFAの下界（L₃: mod 5）

【理由】右同値関係 ≡ₗ で、接尾辞の付加により 5 つの剰余類（mod 5）の右コンテキストが相互に区別可能である。 従って同値類の個数 ≥ 5 ⇒ 最小DFAの状態数 ≥ 5（実際に 5 状態で実現可能）。□

補足: 最小DFAの下界（L₄: mod 7）

【理由】mod 7 の 7 つの剰余類が、それぞれ右コンテキストとして相互に識別可能になる。 従って同値類 ≥ 7 ⇒ 下界 7（実際に 7 状態のDFAで実現可能）。□

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

解答:

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

各 i ≥ 0 に対し xᵢ = 0ⁱ とおく。i ≠ j のとき xᵢ と xⱼ が識別可能であることを示す。 z = 1ⁱ とすると、

• xᵢz = 0ⁱ1ⁱ ∈ L
• xⱼz = 0ʲ1ⁱ ∉ L（j ≠ i のため 0 と 1 の個数が一致しない）

よって xᵢ ≠ₗ xⱼ（右同値類が異なる）。したがって {x₀, x₁, x₂, …} は互いに異なる右同値類に属し、同値類の数は無限個である。

従って L は正規言語ではない。□

第4章: 計算可能性

練習問題4.1 停止問題

問題: 以下の問題が決定不可能であることを証明せよ。 EMPTY = {⟨M⟩ | M はチューリング機械でL(M) = ∅}

解答:

証明: 停止問題ATMからEMPTYへの還元を示す。

還元関数f: ⟨M,w⟩ → ⟨M’⟩を以下のように構成：

M’の動作（入力x）:

1. xを無視してwをテープに書く
2. Mをw上でシミュレート
3. Mがwを受理すれば受理
4. Mがwを拒否すれば拒否

解析:

• ⟨M,w⟩ ∈ ATM ⟺ Mはwを受理 ⟺ M’はすべての入力を受理 ⟺ L(M’) ≠ ∅ ⟺ ⟨M’⟩ ∉ EMPTY
• ⟨M,w⟩ ∉ ATM ⟺ Mはwを受理しない ⟺ M’はどの入力も受理しない ⟺ L(M’) = ∅ ⟺ ⟨M’⟩ ∈ EMPTY

よって⟨M,w⟩ ∈ ATM ⟺ ⟨M’⟩ ∉ EMPTY。

ATMが決定不可能でこの還元が計算可能なので、EMPTYも決定不可能である。□

練習問題4.2 Riceの定理

問題: Riceの定理を用いて、以下の問題が決定不可能であることを証明せよ。 INFINITE = {⟨M⟩ | L(M)は無限言語}

解答:

証明: Riceの定理を適用する。

INFINITEに対して：

• P: 「言語が無限である」という性質
• L₁ = Σ* (無限言語)
• L₂ = ∅ (有限言語)

L₁はPを満たし、L₂はPを満たさない。また、Pは非自明（Pを満たす言語と満たさない言語が両方存在）で、かつ L(M) にのみ依存する意味的性質である。

よってRiceの定理により、INFINITEは決定不可能である。□

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

解答: 決定不可能。

証明: Rice の定理を適用する。性質 P を「正規言語である」とする。 P は L(M)（言語）にのみ依存する意味的性質であり、非自明（∅ や a* は正規、{a^n b^n | n≥0} は非正規）である。したがって {⟨M⟩ | L(M) が P} は決定不可能。□

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

解答: 決定不可能。

証明: 性質 P を「w₀ を含む」とする。 P は言語の意味的性質であり、非自明（Σ* は満たす、∅ は満たさない）。よって {⟨M⟩ | L(M) が P} は Rice の定理により決定不可能。□

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

（問題要約）4.2.3 のテンプレに従い、ATM ≤ₘ E̅_TM または ATM ≤ₘ ALL_TM の構成を概説せよ。

【解答の骨子】

• 目的: A ≤ₘ B。A = ATM、B = E̅_TM または ALL_TM。
• f の定義（例: ⟨M,w⟩ ↦ ⟨M’⟩）: M’ は x を無視して M を w でシミュレート、M が受理なら受理（E̅_TM向けは受理/拒否で L(M’)≠∅ を実現）。
• (⇒): ⟨M,w⟩ ∈ ATM ⇒ M’ の言語が非空（または Σ*） ⇒ f(⟨M,w⟩) ∈ B。
• (⇐): f(⟨M,w⟩) ∈ B ⇒ M’ が非空（または全受理） ⇒ M が w を受理 ⇒ ⟨M,w⟩ ∈ A。
• 計算可能性: f は構成に基づく決定的変換で計算可能（サイズ増も多項式）。

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

解答: 決定不可能。

証明: 性質 P を「言語が有限である」とする。P は L(M) にのみ依存する意味的性質で、 非自明（例: ∅ は有限、Σ* は非有限）。よって Rice の定理により {⟨M⟩ | L(M) が P} は決定不可能。□

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

解答: 決定不可能。

証明: 性質 P を「補集合が有限（補有限）」とする。P は言語の意味的性質であり、 非自明（Σ* は満たす、∅ は満たさない）。従って Rice の定理により {⟨M⟩ | L(M) が P} は決定不可能。□

第5章: 計算複雑性理論

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

問題: P ⊆ NP ⊆ PSPACE を証明せよ。

解答:

P ⊆ NP の証明: L ∈ Pとする。Lを多項式時間で決定するTM Mが存在する。 以下の非決定性TM M’を構成：

• M’は入力xに対してMを実行し、Mと同じ結果を返す
• M’の実行時間はMと同じで多項式時間

よってL ∈ NP。□

NP ⊆ PSPACE の証明: L ∈ NPとする。Lを多項式時間で検証するTM Vが存在し、証拠yの長さはp(|x|)以下（pは多項式）。

以下のPSPACE TM M’を構成：

• 入力x（長さn）について
• 長さp(n)以下のすべての文字列yを列挙（指数的に多い）
• 各yについてV(x,y)を実行し、受理すれば受理

空間解析:

• yの列挙にはp(n)の空間（現在のyを保存）
• V(x,y)の実行にはp(n)の空間（Vは多項式時間）
• 全体でO(p(n))の多項式空間

よってL ∈ PSPACE。□

補足: 3-SAT → Vertex-Cover のサイズ管理（概算）

【主張】標準的な 3-SAT→Vertex-Cover 還元で、頂点数・辺数・k は元のインスタンス（変数数 n、節数 m）に対し O(n+m)。

【概算】

• 変数ガジェット: 各変数につき定数個の頂点・辺 ⇒ O(n)
• 節ガジェット: 各節につき定数個の頂点・辺 ⇒ O(m)
• 交差辺も各節間で定数本のルールで追加 ⇒ 合計 O(n+m)
• k は n, m に線形の式で表せる（構成に依存）

従って線形拡大に抑えられる。□

補足: 3-SAT から CLIQUE への還元（概略）

（問題）3-SAT φ から、G と k を構成して φ が充足可能 ⇔ G にサイズ k のクリークが存在 を示す。

【構成】

• 各節 Cᵢ の各リテラルに対応する頂点 v_{i,ℓ} を作る（節ごとに3頂点）。
• 異なる節に属し、かつ矛盾しないリテラル対に辺を張る。
• k = 節数 m。

【正当性】

• (⇒) 充足割当てから各節の真リテラル頂点を選べば互いに接続 ⇒ k-クリーク。
• (⇐) k-クリークは各節から矛盾しない1頂点ずつの選択を与える ⇒ 対応する割当てで充足。
• 構成は多項式時間。□

補足: 3-SAT から INDEPENDENT-SET への還元（概略）

【構成】節ごとに3頂点を置き、異なる節間で矛盾するリテラル対に辺を張るのではなく、同一節内の3頂点は互いに隣接させて（クリーク）節から高々1つしか取れないようにする。k = 節数 m とし、矛盾するリテラル対にも辺を張って同時選択を禁止する。

【正当性】

• (⇒) 充足割当てがあれば各節から真リテラル1つを選べる。矛盾する選択はないため m-独立集合が得られる。
• (⇐) m-独立集合は各節から1頂点ずつ（節内はクリークなので1つ）で構成され、矛盾を避けているため対応する割当てで充足。
• サイズ管理: 頂点・辺・k は O(n+m)。□

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

問題: VERTEX-COVERがNP完全であることを証明せよ。 VERTEX-COVER = {⟨G,k⟩ | Gはサイズk以下の頂点被覆を持つ}

解答:

VERTEX-COVER ∈ NP の証明: 証拠：サイズk以下の頂点集合S 検証：Sの各頂点を確認し、すべての辺が被覆されているかチェック 時間：O(|V| + |E|)で多項式時間

NP困難性の証明（3-SATからの還元）: 3-SATのインスタンス φ = C₁ ∧ C₂ ∧ … ∧ Cₘ（各Cᵢは3つのリテラルの選言）から、グラフG = (V,E)とk = |V| − mを構成：

構成:

1. 各変数xᵢについて：2つの頂点xᵢ, x̄ᵢを作成し、エッジ(xᵢ, x̄ᵢ)を追加
2. 各節Cⱼについて：3つの頂点を作成し、完全グラフにする
3. 各節の頂点を、対応するリテラルの頂点に接続

正当性: ⇒: φが充足可能ならば、真の割当てに対応する変数頂点と、各節で偽になるリテラル以外の頂点を選ぶ

よってVERTEX-COVERはNP完全である。□

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

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

解答:

構成の復習：

• 各変数につき 2 頂点（xᵢ, x̄ᵢ）と 1 辺（相互排他エッジ）→ 頂点 2n、辺 n
• 各節につき 3 頂点（リテラル）を三角形で結ぶ → 頂点 3m、辺 3m
• 節リテラル頂点から対応変数頂点への「適合」辺 → 各節3本で最大 3m 辺
• パラメータ k = n + 2m

合計：頂点数 |V| = 2n + 3m = O(n+m)、辺数 |E| = n + 3m + ≤3m = O(n+m)、k = n + 2m = O(n+m)。 よってサイズ増加は線形である。□

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

問題: 章末問題「6. Cook–Levin」について、入力長 n、時間境界 p(n)（多項式）を満たす計算を CNF に符号化する際、変数数・節数が多項式オーダーで抑えられることを概算で示せ。

解答（一例の見積もり）:

テープ×時間の格子（p(n)×p(n) の領域）に対し、各セルに「記号/状態」を割り当てる多値変数を 0/1 変数にエンコードする。

• 変数数：O(p(n)^2 · s) 個（s は記号+状態の選択肢の定数倍）
• 制約：
  • 配置一意性（各セルはちょうど1ラベル）: 各セルあたり O(s) 節 → O(p(n)^2)
  • 初期条件（t=0 行）: O(p(n)) 節
  • 遷移制約（3×3 局所窓）: 各時間 t ごとに O(p(n)) 個の窓、各窓に定数個の節 → O(p(n)^2)
  • 受理条件（いずれかの t で受理状態）: O(p(n)) 節

合計で節数は O(p(n)^2) の多項式オーダー、変数数も O(p(n)^2) 程度に抑えられる（エンコード詳細によって定数や指数は変わるが多項式である）。 したがって、Cook–Levin の還元はサイズ面でも多項式時間還元の要件を満たす。□

練習問題5.5 CLIQUE → VERTEX-COVER のサイズ変換

解答:

入力を (G=(V,E), k) とする。補グラフ Ḡ=(V, Ē) を次で定義する： Ē = { {u,v} | u≠v かつ {u,v} ∉ E }。

1) CLIQUE と INDEPENDENT-SET の対応

G にサイズ k のクリークが存在する ⇔ Ḡ にサイズ k の独立集合が存在する。 （G で互いに全て辺がある集合は、補グラフでは互いに辺が無い集合になる。）

2) INDEPENDENT-SET と VERTEX-COVER の対応

任意のグラフ H=(V,F) について、S ⊆ V が独立集合であることと、V\S が頂点被覆であることは同値である。 従って、H にサイズ k の独立集合が存在する ⇔ H にサイズ |V| − k の頂点被覆が存在する。

サイズ管理:

• V’

  =

  V

• 補グラフの構成は O(

  V

  ²) 時間で可能（全ての頂点対を走査して辺の有無を反転）

• k’ =

  V

  − k は線形で計算できる

よってサイズ増加は多項式である。□

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

練習問題6.1 Master定理

問題: 以下の漸化式をMaster定理で解け。 T(n) = 8T(n/2) + n²

解答:

Master定理の適用: T(n) = aT(n/b) + f(n)の形で、a = 8, b = 2, f(n) = n²

比較:

• nᶜ = n^(log₂ 8) = n³ （∵ log₂ 8 = 3）
• f(n) = n²

f(n) = O(nᶜ⁻ᵋ) for ε = 1なので、ケース1が適用される。

結果: T(n) = Θ(n³)

検証: T(n) = 8T(n/2) + n² = 8[8T(n/4) + (n/2)²] + n² = 64T(n/4) + 2n² + n² = 64T(n/4) + 3n² ⋮ = 8ᵏT(n/2ᵏ) + n²∑ᵢ₌₀ᵏ⁻¹(8/4)ⁱ

k = log₂ nのとき、T(1) = O(1)なので： T(n) = O(nᵏ) + n²((8/4)ᵏ - 1)/(8/4 - 1) = O(n³) + n²(2ᵏ - 1) = O(n³) + n²(n - 1) = Θ(n³) □

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

問題: 最適二分探索木問題に対する動的計画法アルゴリズムを設計し、時間複雑性を解析せよ。

解答:

問題設定: n個のキーk₁ < k₂ < … < kₙに対し、各キーkᵢの検索確率がpᵢで与えられたとき、期待検索コストを最小化する二分探索木を構築する。

部分問題: opt[i][j] = キーkᵢ, …, kⱼから構成される最適二分探索木のコスト

漸化式: opt[i][j] = min{opt[i][r-1] + opt[r+1][j] + ∑ₖ₌ᵢʲ pₖ} for i ≤ r ≤ j

アルゴリズム:

def optimal_bst(p):
    n = len(p)
    opt = [[0] * n for _ in range(n)]
    sum_p = [[0] * n for _ in range(n)]
    
    # 前処理：確率の累積和を計算
    for i in range(n):
        for j in range(i, n):
            sum_p[i][j] = sum(p[i:j+1])
    
    # 動的計画法
    for length in range(1, n+1):  # 部分問題のサイズ
        for i in range(n - length + 1):
            j = i + length - 1
            opt[i][j] = float('inf')
            
            for r in range(i, j+1):  # 根の選択
                cost = sum_p[i][j]
                if r > i:
                    cost += opt[i][r-1]
                if r < j:
                    cost += opt[r+1][j]
                
                opt[i][j] = min(opt[i][j], cost)
    
    return opt[0][n-1]

時間複雑性解析:

• 3重ループ：O(n³)
• 各内側の計算：O(1)
• 全体：Θ(n³)

空間複雑性: Θ(n²) □

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

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

解答（上界の一例）:

帰納法で T(n) ≤ c·n log n を示す（log は底を固定した対数）。

帰納法の仮定として、すべての m < n で T(m) ≤ c·m log m が成り立つとする。すると、

T(n) = T(n/3) + T(2n/3) + n
≤ c·(n/3)log(n/3) + c·(2n/3)log(2n/3) + n

ここで、 (n/3)log(n/3) + (2n/3)log(2n/3) = n log n + n·( (1/3)log(1/3) + (2/3)log(2/3) ) であり、括弧内は負の定数（< 0）である。よってある定数 a > 0 が存在して

T(n) ≤ c·n log n − c·a·n + n

となる。c を十分大きく（例: c ≥ 1/a）取れば、右辺は c·n log n 以下に抑えられ、帰納が閉じる。 従って T(n) = O(n log n)。□

補足: 置換法の例（T(n) = 3T(n/2) + n）

• 期待される解: T(n) = Θ(n^{log₂3})（≃ Θ(n^{1.585})）
• 置換法の一例: 帰納法で T(n) ≤ c·n^{log₂3} − k·n を仮定し、 T(n) = 3T(n/2) + n ≤ 3(c(n/2)^{log₂3} − k·(n/2)) + n = 3c·n^{log₂3}/2^{log₂3} − (3k/2)n + n = c·n^{log₂3} − (3k/2 − 1)n k を十分大きく取れば帰納が閉じる（下界も同様に示せる）。

補足: 再帰式バリエーションの目安

1) T(n) = 4T(n/2) + n^2
a=4, b=2, f(n)=n^2、n^{log_b a} = n^2 ⇒ ケース2（同次数）で T(n)=Θ(n^2 log n)

2) T(n) = T(n/2) + n / log n
a=1, b=2, f(n)=n/log n、n^{log_b a}=n^0=1。拡張版のマスター定理や置換法で T(n)=Θ(n) を示せる（調和級数的寄与が主任項）

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

練習問題7.1（基礎1）

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

解答（代表例）:

前提（代表的な実装）：

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

補足：

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

練習問題7.2（基礎2）

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

解答:

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

1. LLケース（z の左部分木の左側に挿入）
   z で 右回転（single right rotation）。
2. RRケース（z の右部分木の右側に挿入）
   z で 左回転（single left rotation）。
3. LRケース（z の左部分木の右側に挿入）
   y で 左回転 → z で 右回転（double rotation）。
4. RLケース（z の右部分木の左側に挿入）
   y で 右回転 → z で 左回転（double rotation）。

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

練習問題7.3（基礎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）

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

解答:

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

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

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

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

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

練習問題7.5（発展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）

問題: フィボナッチヒープの 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）

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

解答（SA-IS の概要）:

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

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

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

練習問題7.8（発展8）

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

解答:

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

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

select(k):

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

rank(x):

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

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

練習問題7.9（探究9）

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

解答（調査ガイド）:

比較観点（例）：

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

代表例：

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

アウトプット例：

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

練習問題7.10（探究10）

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

解答（調査ガイド）:

要点：

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

例：

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

練習問題7.11（探究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）

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

解答（調査ガイド）:

比較軸：

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

例：

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

練習問題7.13（実装13）

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

解答（方針）:

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

期待される性質：

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

練習問題7.14（実装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）

問題: ブルームフィルタ、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）

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

解答:

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

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

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

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

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

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

(c) DAG最長パス（DP + トポロジカル順）:

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

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

練習問題8.2（基礎2）

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

解答:

頂点 s,a,b と辺：

• s→a: 2
• s→b: 5
• b→a: -4

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

練習問題8.3（基礎3）

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

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

以下は同値：

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

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

練習問題8.4（基礎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）

問題: プラナーグラフの双対グラフの定義と、最短路と最小カットの双対性を説明せよ。

解答（概要）:

(a) 双対グラフ G*：

• 平面埋め込みされた連結平面グラフ G の各面（face）を G* の頂点とする
• G の各辺 e は、隣接する2面 f,g を分けるので、G* に辺 e*（f と g を結ぶ）を置く
  • 境界に接する場合も含め、埋め込みに依存する点に注意

(b) 双対性（代表例）：

• 平面グラフにおける s-t カットは、双対では「s と t を分離する閉路」に対応する
• 辺重みを保って双対に移すと、最小 s-t カットが双対グラフ上の最短路/最小閉路に対応する（埋め込み上の対応付けが必要）

練習問題8.6（発展6）

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

解答:

(a) 定義（木分解）：

• 袋（bag）集合 {X_i} と木 T からなり、
  1. 全頂点がどこかの袋に含まれる
  2. 各辺 (u,v) に対し、同一袋に u,v を含む
  3. 各頂点 v を含む袋集合は T 上で連結

• 幅 = max_i

  X_i

  - 1、木幅 tw(G) は幅の最小値

計算複雑性：

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

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

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

練習問題8.7（発展7）

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

解答:

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

(b) 改善案（例）：

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

練習問題8.8（発展8）

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

解答:

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

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

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

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

練習問題8.9（探究9）

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

解答（調査ガイド）:

対象指標（例）と計算：

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

設計観点：

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

練習問題8.10（探究10）

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

解答（調査ガイド）:

論点：

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

アウトプット例：

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

練習問題8.11（探究11）

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

解答（調査ガイド）:

代表的観点：

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

比較軸：

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

練習問題8.12（探究12）

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

解答（調査ガイド）:

対象（例）：

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

比較軸：

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

練習問題8.13（実装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）

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

解答（方針）:

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

練習問題8.15（実装15）

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

解答（方針）:

ベンチマーク設計：

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

分析観点：

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

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

練習問題9.1（基礎1）

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

(a) (p → q) ∧ (q → r) ∧ (r → 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）

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

(a) ∀x(P(x) → ∃y Q(x, y)) ∧ ∃z R(z)
(b) ¬∀x∃y(P(x, y) ↔ ¬∃z Q(y, z))

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

(a)

1. P(x)→∃yQ(x,y) ≡ ¬P(x) ∨ ∃yQ(x,y)
2. y は ¬P(x) に自由出現しないので、¬P(x) ∨ ∃yQ(x,y) ≡ ∃y(¬P(x) ∨ Q(x,y))
3. よって ∀x∃y(¬P(x) ∨ Q(x,y)) ∧ ∃zR(z)
4. z は左項に自由出現しないので、全体 ≡ ∀x∃y∃z( (¬P(x) ∨ Q(x,y)) ∧ R(z) )

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

(b)

1. ¬∀x φ ≡ ∃x ¬φ、¬∃y ψ ≡ ∀y ¬ψ より
   ¬∀x∃y(…) ≡ ∃x∀y ¬(…)
2. ¬(A↔B) ≡ (A∧¬B) ∨ (¬A∧B) を用いる。A=P(x,y)、B=¬∃zQ(y,z)。
   すると ¬B=∃zQ(y,z)、B=∀z¬Q(y,z)。
3. 変数名を分離（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）

問題: 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 * x! = n! かつ x ≥ 0 と置く。初期（y=1,x=n）で I 成立。
  反復で y’=yx, x’=x-1 なので y’(x’)! = yx(x-1)! = yx! = n! が保たれる。
  終了時 x=0 より y0! = n!、従って y=n!。

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

練習問題9.4（基礎4）

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

解答:

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

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

練習問題9.5（発展5）

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

解答（概略）:

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

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

練習問題9.6（発展6）

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

解答（概要）:

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

練習問題9.7（発展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）

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

解答:

代表対応：

• A→B ↔ 関数型 A→B
• A∧B ↔ 積型 A×B
• A∨B ↔ 和型 A+B

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

練習問題9.9（探究9）

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

解答（調査ガイド）:

比較軸：

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

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

練習問題9.10（探究10）

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

解答（調査ガイド）:

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

代表ツール：PRISM。

練習問題9.11（探究11）

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

解答（調査ガイド）:

例の方向性：

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

論点：

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

練習問題9.12（探究12）

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

解答（調査ガイド）:

アプローチ例：

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

課題：

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

第10章: 情報理論

練習問題10.1（基礎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₂）:

(a) H(X) = -∑ p log p
= -(1/2·log(1/2) + 1/4·log(1/4) + 1/8·log(1/8) + 1/8·log(1/8))
= 1/2·1 + 1/4·2 + 1/8·3 + 1/8·3
= 1.75 [bit]

(b) H(X) = -∑_{k≥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 - ((1-p)/p)·log(1-p)。

練習問題10.2（基礎2）

解答:

連鎖律より

• I(X;Y,Z) = I(X;Z) + I(X;Y

  Z)

• I(X;Y,Z) = I(X;Y) + I(X;Z

  Y)

練習問題10.3（基礎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）

問題: {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）

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

解答（要点）:

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

練習問題10.6（発展6）

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

解答（概要）:

弱型（weakly typical）：

• A^{(n)}_ε = {x^n :

  -(1/n)log p(x^n) - H(X)

  ≤ ε}

強型（strongly typical）：

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

AEP（漸近等分割性）：

• i.i.d. のとき、-(1/n)log p(X^n) → H(X)（確率1）

証明スケッチ：

• -log p(X^n)=∑_{i=1}^n -log p(X_i)。右辺は独立同分布で期待値が H(X)。
• 大数の法則により (1/n)∑ -log p(X_i) → H(X)。

練習問題10.7（発展7）

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

解答:

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

• R_X ≥ H(X

  Y)

• R_Y ≥ H(Y

  X)

• R_X + R_Y ≥ H(X,Y)

練習問題10.8（発展8）

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

解答（概要）:

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

練習問題10.9（探究9）

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

解答（調査ガイド）:

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

練習問題10.10（探究10）

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

解答（調査ガイド）:

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

練習問題10.11（探究11）

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

解答（調査ガイド）:

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

練習問題10.12（探究12）

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

解答（調査ガイド）:

論点：

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

応用例：

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

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

練習問題11.1（基礎1）

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

解答:

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

練習問題11.2（基礎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）

問題: 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）

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

解答:

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

練習問題11.5（発展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）

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

解答（概要）:

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

知識抽出器の基本形：

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

練習問題11.7（発展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）

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

解答:

双線形ペアリング e: G1×G2→GT の代表性質：

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

応用（例：Boneh-Franklin IBE）：

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

練習問題11.9（探究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）

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

解答（調査ガイド）:

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

練習問題11.11（探究11）

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

解答（調査ガイド）:

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

練習問題11.12（探究12）

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

解答（調査ガイド）:

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

第12章: 並行計算の理論

練習問題12.1（基礎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）

問題: 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 を選択して終了する。
(b) 同値。制限 \{a} により a は外部へ出せず（相手がいないため内部同期もしない）、残る観測可能な行動は b のみで b.0 と同じ振る舞いになる。

練習問題12.3（基礎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）

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

解答（スケッチ）:

各プロセス i は番号 ticket[i] を取り、(ticket[i], i) の辞書順最小がクリティカルセクションに入る。
同時に i,j が CS に入ったと仮定すると、互いに「相手が自分より先ではない」ことを待っているため、 (ticket[i],i) < (ticket[j],j) かつ (ticket[j],j) < (ticket[i],i) の矛盾が生じる。
従って同時侵入は不可能で相互排除が成り立つ。

練習問題12.5（発展5）

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

解答:

Lamport 時計：

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

性質：

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

ベクトル時計：

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

練習問題12.6（発展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）

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

解答（概要）:

Michael-Scott キュー：

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

ABA問題：

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

対策例：

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

練習問題12.8（発展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）

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

解答（調査ガイド）:

比較軸：

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

概略：

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

練習問題12.10（探究10）

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

解答（調査ガイド）:

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

練習問題12.11（探究11）

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

解答（調査ガイド）:

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

実装例：

• Erlang/Elixir、Akka（JVM）等。

練習問題12.12（探究12）

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

解答（調査ガイド）:

例：

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

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

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