付録H: 図版ガイドと図一覧

この付録は、本書の図版を見返す入口として使うための読者向けガイドです。 本文の途中で見た図を後から探し直したいとき、章をまたいで似た図を比較したいとき、図の役割を確認したいときに参照してください。

この付録の使い方

• 最初に読む場所ではありません。本文を読んでいて図に助けられた箇所を、後から戻るための一覧です。
• 本文の節リンク と SVG 直接リンク を併記しています。前者は文脈確認用、後者は図だけを拡大して見たいときに使ってください。
• 章内の位置 は「節」で示しています。厳密な図番号ではなく、読者が再訪しやすい再参照導線を優先しています。

図ラベルの読み方

• 直観図: 定義や証明を置き換えるものではなく、何が本質かを先に掴むための図です。
• 例示図: アルゴリズムの逐次実行、状態変化、構成の具体例を追うための図です。
• 比較図: 複数の手法・クラス・見方の差分を見比べるための図です。
• 構成図 / 模式図: 装置の構成や処理フローを順に追うための図です。
• 図版: 本文に明示ラベルがない図です。節名と alt テキストで文脈を補っています。

目的別ショートリスト

図で詰まったときは、まず次の目的別ショートリストから近いものを開いてください。

直観図を見たいとき

• Thompson 構成法：段階図 — 第3章 形式言語とオートマトン理論 / 節: 「3.3.2 正規表現からNFAへの変換プロセス」 / SVG
• PDA のスタック操作（括弧整合） — 第3章 形式言語とオートマトン理論 / 節: 「3.6 プッシュダウンオートマトン」 / SVG
• PDAの受理方式 — 第3章 形式言語とオートマトン理論 / 節: 「3.6.2 PDAの受理方式」 / SVG
• Big-O 成長率の比較 — 第5章 計算複雑性理論 / 節: 「5.1.2 漸近記法」 / SVG

例示図を見たいとき

• グラフ理論の基本例 — 第1章 数学的基礎 / 節: 「1.5.1 グラフの定義」 / SVG
• Dijkstraアルゴリズムの実行例 — 第8章 グラフ理論とネットワーク / 節: 「8.2.1 単一始点最短路」 / SVG
• Dijkstra 法の逐次確定の例 — 第8章 グラフ理論とネットワーク / 節: 「Dijkstraのアルゴリズム」 / SVG
• 最大フロー最小カットの例 — 第8章 グラフ理論とネットワーク / 節: 「8.4.1 最大フロー問題」 / SVG

比較図を見たいとき

• 計算可能性の概念と階層 — 第2章 計算理論の基礎 / 節: 「2.2 計算可能性」 / SVG
• 決定可能性の階層構造 — 第2章 計算理論の基礎 / 節: 「2.3 決定可能性」 / SVG
• 有限オートマトンの種類と特徴 — 第3章 形式言語とオートマトン理論 / 節: 「3.2 有限オートマトン」 / SVG
• 言語クラスの階層構造 — 第4章 計算可能性理論 / 節: 「4.3.1 言語クラスの包含関係」 / SVG

手順/構成図を見たいとき

• チューリング機械の構成要素 — 第2章 計算理論の基礎 / 節: 「2.1.2 チューリング機械の形式的定義」 / SVG
• チューリング機械の構成 — 第2章 計算理論の基礎 / 節: 「2.1.3 チューリング機械の構成と計算」 / SVG
• 万能チューリング機械の構成と意義 — 第2章 計算理論の基礎 / 節: 「2.5 万能チューリング機械」 / SVG
• 多対一還元の仕組み — 第4章 計算可能性理論 / 節: 「4.2.1 多対一還元」 / SVG

図版サマリー

• 総図版数: 72
• Part I: 数学的基礎: 24 図
• Part II: 計算理論: 16 図
• Part III: 高度なトピック: 15 図
• Part IV: 応用理論: 17 図

図一覧

Part I: 数学的基礎

第1章 数学的基礎（4 図）

• 図版: 理論計算機科学の体系と相互関連 — 節: 「理論計算機科学の全体像」 / SVG
• 図版: 集合演算の視覚化 — 節: 「1.1.2 集合演算」 / SVG
• 図版: 有理数の可算性の証明 — 節: 「1.1.3 集合の濃度 (可算と非可算)」 / SVG
• 図版: グラフ理論の基本例 — 節: 「1.5.1 グラフの定義」 / SVG

第2章 計算理論の基礎（8 図）

• 図版: チューリング機械の構成要素 — 節: 「2.1.2 チューリング機械の形式的定義」 / SVG
• 図版: チューリング機械の構成 — 節: 「2.1.3 チューリング機械の構成と計算」 / SVG
• 図版: 計算可能性の概念と階層 — 節: 「2.2 計算可能性」 / SVG
• 図版: 等価な計算モデル（1930年代） — 節: 「2.2.3 Church-Turingの提唱」 / SVG
• 図版: 決定可能性の階層構造 — 節: 「2.3 決定可能性」 / SVG
• 図版: チューリング機械の変種と等価性 — 節: 「2.4 チューリング機械の変種」 / SVG
• 図版: 万能チューリング機械の構成と意義 — 節: 「2.5 万能チューリング機械」 / SVG
• 図版: 対角化論法と決定不能性 — 節: 「2.6 計算可能性の基本定理」 / SVG

第3章 形式言語とオートマトン理論（12 図）

• 図版: 形式言語の基本概念 — 節: 「3.1 形式言語」 / SVG
• 図版: 有限オートマトンの種類と特徴 — 節: 「3.2 有限オートマトン」 / SVG
• 図版: 偶数個の0を認識するDFA — 節: 「3.2.1 決定性有限オートマトン（DFA）」 / SVG
• 図版: 正規言語と正規表現 — 節: 「3.3 正規言語」 / SVG
• 直観図: Thompson 構成法：段階図 — 節: 「3.3.2 正規表現からNFAへの変換プロセス」 / SVG / 本文ラベル: 「Thompson 構成の各規則（リテラル・連結・和・クリーネ閉包）」
• 図版: ポンピング補題（Pumping Lemma）と限界 — 節: 「3.4 正規言語の限界」 / SVG
• 図版: Myhill–Nerode: 接頭辞で区別できる右コンテキスト — 節: 「最小DFAとの関係（実務的な見方）」 / SVG
• 図版: 文脈自由言語と文法 — 節: 「3.5 文脈自由言語」 / SVG
• 図版: プッシュダウンオートマトンの構造と機能 — 節: 「3.6 プッシュダウンオートマトン」 / SVG
• 直観図: PDA のスタック操作（括弧整合） — 節: 「3.6 プッシュダウンオートマトン」 / SVG / 本文ラベル: 「括弧整合を受理する PDA のスタック操作例」
• 直観図: PDAの受理方式 — 節: 「3.6.2 PDAの受理方式」 / SVG / 本文ラベル: 「最終状態受理 vs 空スタック受理」
• 図版: 文脈自由言語の性質と限界 — 節: 「3.7 文脈自由言語の性質」 / SVG

Part II: 計算理論

第4章 計算可能性理論（5 図）

• 図版: 停止問題の対角化論法 — 節: 「4.1.1 停止問題」 / SVG
• 図版: 多対一還元の仕組み — 節: 「4.2.1 多対一還元」 / SVG
• 図版: 言語クラスの階層構造 — 節: 「4.3.1 言語クラスの包含関係」 / SVG
• 図版: Rice の定理の還元スキーマ（A_{TM} から R_P への還元） — 節: 「4.4.2 Riceの定理の主張と証明」 / SVG
• 図版: 部分再帰関数の構成 — 節: 「4.5.1 部分再帰関数」 / SVG

第5章 計算複雑性理論（7 図）

• 直観図: Big-O 成長率の比較 — 節: 「5.1.2 漸近記法」 / SVG / 本文ラベル: 「代表的な計算量の増加の比較（\(O(1)\), \(O(\log n)\), \(O(n)\), \(O(n\log n)\), \(O(n^2)\)）」
• 図版: 計算複雑性の階層構造 — 節: 「5.1.3 時間複雑性クラス」 / SVG
• 図版: P vs NP 問題の構造 — 節: 「5.3.1 問題の定式化」 / SVG
• 直観図: Cook–Levin の直観図（テープ×時間とCNF） — 節: 「5.3.3 Cook–Levin の定理」 / SVG / 本文ラベル: 「テープ×時間の格子から CNF への局所制約」
• 図版: NP完全性と還元の連鎖 — 節: 「5.3.4 NP完全問題の連鎖と還元の「気持ち」」 / SVG
• 図版: 計算複雑性クラスの包含関係 — 節: 「5.4.3 空間と時間の関係」 / SVG
• 直観図: 3-SAT → 頂点被覆 ガジェット例 — 節: 「実装課題」 / SVG / 本文ラベル: 「変数/節ガジェットの最小例（3-SAT → 頂点被覆）」

第6章 アルゴリズムの数学的解析（4 図）

• 図版: 主要な時間複雑度クラス — 節: 「6.1.1 最悪時間解析」 / SVG
• 図版: マスター定理の適用 — 節: 「6.2.2 マスター定理」 / SVG
• 図版: 動的計画法の適用条件 — 節: 「6.3.1 最適部分構造」 / SVG
• 図版: アルゴリズム設計パラダイムの比較 — 節: 「6.4.1 貪欲選択性」 / SVG

Part III: 高度なトピック

第7章 データ構造の理論（4 図）

• 図版: 基本データ構造の比較 — 節: 「7.2.1 配列とリスト」 / SVG
• 図版: AVL木の回転操作 — 節: 「7.3.1 AVL木」 / SVG
• 図版: Union-Findの最適化技法 — 節: 「7.4.2 Union-Find構造」 / SVG
• 図版: スキップリストの構造 — 節: 「7.6.1 スキップリスト」 / SVG

第8章 グラフ理論とネットワーク（6 図）

• 直観図: BFS と DFS の比較 — 節: 「8.1.3 グラフの走査」 / SVG / 本文ラベル: 「同一グラフに対する BFS と DFS の探索順・探索木の比較」
• 図版: Dijkstraアルゴリズムの実行例 — 節: 「8.2.1 単一始点最短路」 / SVG
• 例示図: Dijkstra 法の逐次確定の例 — 節: 「Dijkstraのアルゴリズム」 / SVG / 本文ラベル: 「Dijkstra の逐次確定（確定集合と緩和の模式図）」
• 図版: Kruskal法とUnion-Findの流れ — 節: 「8.3.2 Kruskalのアルゴリズム」 / SVG
• 図版: 最大フロー最小カットの例 — 節: 「8.4.1 最大フロー問題」 / SVG
• 図版: 二部グラフのマッチング — 節: 「8.5.1 二部グラフのマッチング」 / SVG

第9章 論理学と形式的手法（5 図）

• 図版: 命題論理の決定手続きの比較 — 節: 「9.1.4 命題論理の決定手続き」 / SVG
• 直観図: DPLL と CDCL の対比 — 節: 「9.1.4 命題論理の決定手続き」 / SVG / 本文ラベル: 「DPLL と CDCL の対比（学習・非年代戻り・VSIDS）」
• 図版: 時相論理とモデル検査 — 節: 「9.3.3 モデル検査」 / SVG
• 図版: Hoare論理の推論規則体系 — 節: 「9.4.2 推論規則」 / SVG
• 図版: 定理証明支援系の分類と特徴 — 節: 「9.6.1 対話型定理証明」 / SVG

Part IV: 応用理論

第10章 情報理論（6 図）

• 図版: 情報量とエントロピーの概念 — 節: 「10.1.2 Shannon エントロピー」 / SVG
• 直観図: 二値エントロピー関数 h(p) の曲線 — 節: 「10.1.2 Shannon エントロピー」 / SVG / 本文ラベル: 「二値エントロピー h(p) の曲線（底は \(\log_2\)）」
• 図版: Huffman符号の構成例 — 節: 「Huffman 符号」 / SVG
• 図版: 通信路モデルと容量 — 節: 「10.3.1 通信路モデル」 / SVG
• 直観図: AWGN 容量曲線 — 節: 「10.5.4 帯域制限通信路」 / SVG / 本文ラベル: 「AWGN 容量 \(C = \frac{1}{2} \log_2(1+\mathrm{SNR})\) の曲線」
• 図版: 情報理論の応用分野 — 節: 「10.6.1 データ圧縮への応用」 / SVG

第11章 暗号理論の数学的基礎（5 図）

• 図版: 暗号システムの基本構造 — 節: 「11.1.1 暗号システムの定義」 / SVG
• 直観図: ECB でパターンが露呈する例 — 節: 「11.2.3 暗号利用モード」 / SVG / 本文ラベル: 「模様が暗号文に残る（ECBの例）」
• 直観図: AEAD の処理フロー — 節: 「11.2.4 認証付き暗号」 / SVG / 本文ラベル: 「AEAD の処理フロー（鍵/ノンス/AD/平文から暗号文+タグへの変換、検証）」
• 図版: RSA暗号の仕組み — 節: 「11.3.1 RSA 暗号」 / SVG
• 図版: ゼロ知識証明の概念と応用 — 節: 「11.6.2 ゼロ知識性」 / SVG

第12章 並行計算の理論（6 図）

• 図版: 並行計算の基本概念 — 節: 「12.1.1 並行性の基本概念」 / SVG
• 直観図: HB 関係のタイムライン — 節: 「12.1.2 共有メモリモデル」 / SVG / 本文ラベル: 「happens-before（HB）関係のタイムライン」
• 図版: Petriネットによる並行システムモデリング — 節: 「12.3.1 基本定義」 / SVG
• 直観図: デッドロックのCoffmanの4条件 — 節: 「12.4.3 モデル検査アルゴリズム」 / SVG / 本文ラベル: 「Coffman の4条件と資源割当グラフ（デッドロック例）」
• 図版: 並行データ構造の設計手法 — 節: 「12.6.2 ロックフリーアルゴリズム」 / SVG
• 直観図: ABA問題の概念図 — 節: 「12.6.2 ロックフリーアルゴリズム」 / SVG / 本文ラベル: 「ABA問題の概念図と緩和策の示唆」

補足

• 図だけを拡大して見たいときは SVG リンク、前後の説明ごと見直したいときは本文リンクを使ってください。
• 図だけで理解が固まらないときは、対応する節の定義・定理・例を本文側で併読してください。