付録C: 練習問題解答

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

第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は文脈自由言語ではない。□

第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を満たす言語と満たさない言語が両方存在）。

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

第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。□

練習問題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完全である。□

第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²) □

これらの解答例は、理論的な理解を深めるとともに、実際の問題解決能力を向上させることを目的としています。各解答には証明の構造、アルゴリズムの設計、複雑性解析が含まれており、理論と実践の両面から学習できるようになっています。