付録I: 概念マップ
この付録は、理論分野そのものを分類する図ではなく、本書のどこから読み、どこへ戻るかを決めるための地図です。第1章の「理論計算機科学の全体像」が分野間の関係を示すのに対し、ここでは章の前提、再読経路、通し例の変化を索引化します。
3つの利用場面
- 初読前: 「目的別ショートカット」から入口を選び、必要な前提だけを先に確認します。
- 読書中: 各章の「必須前提」と「強く推奨する前提」を使い、詰まった概念へ戻ります。
- 読了後: 「横断概念の再読経路」や通し例からテーマを選び、複数章を辞書のように再参照します。
「必須前提」は本書内で用語・記法・証明を追うための最小経路、「強く推奨する前提」は対象章だけでも読み始められるものの、先に読むと理解が安定する経路です。「応用・横断的関連」は順序を強制せず、別の章から同じ考え方を見直す寄り道を表します。ここでの「必須」は数学上の依存関係一般ではなく、本書の説明順に対する判定です。
目的別ショートカット
- 最初から体系的に読みたい: 第1章 → 第2章 → 第3章 → Part II〜IV
- 第11章の暗号を読みたい: 第1章の確率・証明 → 第5章の計算量的困難さ → 第11章; 情報量の直観が必要なら第10章へ寄ります
- モデル検査を理解したい: 第1章の論理 → 第3章の形式的表現 → 第9章; 並行系の検証は第12章へ進みます
- 還元と下界を学びたい: 第2章 → 第4章 → 第5章; 計算量的に実行困難であることを安全性の根拠として使う例は第11章で確認します
- アルゴリズムとデータ構造を優先したい: 第1章 → 第6章 → 第7章 / 第8章
- ネットワークと分散処理を読みたい: 第1章 → 第6章 → 第8章 → 第12章; 並行系の仕様検証まで扱う場合は第9章を第12章の前に挟みます
12章の概念マップ
小さい画面や画像を利用できない環境では、図を拡大する代わりに主要辺のテキスト版、続いて章ごとの前提へ進んでください。
概念図: 必須・強く推奨・横断の3種で見る章依存
図では、実線を必須前提、破線を強く推奨する前提、点線を応用・横断的関連として示します。色だけには依存せず、各レーンに辺の種類と章番号を併記しています。図は主要辺の俯瞰であり、次の2つのテキスト版が正本です。
主要辺のテキスト版
- 必須前提（実線）: 1→2・3・6・7・8・9・10・11・12、2→4・5
- 強く推奨する前提（破線）: 3→4、4→5、5→6・11、6→7・8・10・12、7→8、3→9、10→11、9→12
- 応用・横断的関連（点線）: 4↔9、7↔12、8↔10・12、9↔11、10↔12、11↔12
テキスト版: 章ごとの前提と戻り先
Part I: 数学的基礎
- 第1章 数学的基礎
- 第2章 計算理論の基礎
- 必須前提: 第1章の集合・関数・証明技法。
- 強く推奨する前提: なし。計算モデルの構成要素が曖昧なら第1章の写像と論理へ戻ります。
- 横断的関連: 第3章の制約付き計算モデル、第4章の決定可能性、第5章の資源制約へ分岐します。
- 第3章 形式言語とオートマトン理論
- 必須前提: 第1章の集合・関係・帰納的な証明。
- 強く推奨する前提: 第2章。モデル間の表現力を比較するときに併読します。
- 横断的関連: 第4章の言語と判定、第9章の形式仕様へ接続します。
Part II: 計算理論
- 第4章 計算可能性理論
- 必須前提: 第2章のチューリング機械・認識可能性。
- 強く推奨する前提: 第3章。言語の受理と閉包性を再確認し、背理法と対角化の読み方は第1章へ戻ります。
- 横断的関連: 還元は第5章のNP完全性へ接続します。一般の自動判定には限界があるという視点は、第9章で有限状態や特定論理に範囲を定めた検証を読む際の境界になります。
- 第5章 計算複雑性理論
- 必須前提: 第2章の計算モデルと入力長、第1章の漸近記法。
- 強く推奨する前提: 第4章。還元の向きを再確認し、具体的な計算量評価は第6章へ往復します。
- 横断的関連: 第11章の計算量的安全性と攻撃者モデルを支える前提です。
- 第6章 アルゴリズムの数学的解析
- 必須前提: 第1章の関数・漸近解析・確率。
- 強く推奨する前提: 第5章。問題の難しさと個別アルゴリズムの速さを分けるために併読します。
- 横断的関連: 第7・8章の性能保証、第10章の符号化手順、第12章の並列アルゴリズムへ接続します。
Part III: 高度なトピック
- 第7章 データ構造の理論
- 必須前提: 第1章の関係・関数・漸近記法。
- 強く推奨する前提: 第6章。計算量と償却解析の見方を先に確認します。
- 横断的関連: Union-Findは第8章、共有データ構造は第12章で再利用します。
- 第8章 グラフ理論とネットワーク
- 必須前提: 第1章のグラフ。
- 強く推奨する前提: 第6章のアルゴリズム解析と第7章の優先度付きキュー・Union-Find。
- 横断的関連: 通信路は第10章、分散ネットワークは第12章へ接続します。
- 第9章 論理学と形式的手法
- 必須前提: 第1章の命題・述語論理と証明技法。
- 強く推奨する前提: 第3章の形式的な構文と第4章の自動化の限界。
- 横断的関連: 暗号プロトコルの性質は第11章、並行系の正当性・モデル検査は第12章へ接続します。
Part IV: 応用理論
- 第10章 情報理論
- 必須前提: 第1章の確率・対数・期待値。
- 強く推奨する前提: 第6章。漸近評価と構成手順を併読します。
- 横断的関連: ネットワーク容量は第8章、安全な通信は第11章、分散通信は第12章へ接続します。
- 第11章 暗号理論の数学的基礎
- 必須前提: 第1章の確率・合同算術・証明。
- 強く推奨する前提: 第5章の計算量的困難さと第10章のエントロピー。
- 横断的関連: プロトコル検証は第9章、分散環境の攻撃面は第12章と接続します。
- 第12章 並行計算の理論
- 必須前提: 第1章の関係・グラフ・不変量・証明技法。
- 強く推奨する前提: 第6章のアルゴリズム解析と第9章の仕様・モデル検査。
- 横断的関連: 共有データ構造は第7章、ネットワークは第8章、通信と安全性は第10・11章から再参照します。
横断概念の再読経路
- 証明・反例: 第1章の証明技法 → 第4章の対角化・還元 → 第5章の困難性 → 第9章の証明体系
- 計算モデルと言語: 第2章の一般モデル → 第3章の制約付きモデル → 第4章の決定可能性 → 第5章の資源制約
- 還元と下界: 第4章の多対一還元 → 第5章のNP完全性 → 第11章の計算量的安全性
- 漸近解析・確率・償却: 第1章の基礎 → 第6章の解析 → 第7章の償却 → 第10章の情報量 → 第11章の確率的安全性
- グラフと最適化: 第1章のグラフ → 第6章の設計法 → 第7章の補助構造 → 第8章の最短路・最大流 → 第12章の分散ネットワーク
- 論理・仕様・検証: 第1章の論理 → 第3章の形式的記述 → 第9章の仕様・モデル検査 → 第12章の並行系検証
- 情報・安全性・並行性: 第10章で測る → 第11章で守る → 第12章で複数主体を協調させる
通し例を章単位で追う
「安全なメッセージ配送基盤」は、新しい理論を導入する別ケースではありません。同じ対象が章ごとにどの表現へ変わるかを思い出すための索引です。章本文または所属Part openerにある既存の説明を章単位へ展開しており、新しいケース設定は追加していません。
- 第1章: メッセージ集合、配送関係、安全性命題、失敗例を数学的に書く。
- 第2章: 入力から配送判断を返す処理を計算モデルとして捉える。
- 第3章: メッセージ形式とコマンド列を言語・文法・受理器へ変換する。
- 第4章: 仕様検査のうち、一般には自動判定できない境界を切り分ける。
- 第5章: 配送制約・レプリカ配置・優先順位づけを計算量で分類する。
- 第6章: 配送・割当て・探索手順を選び、時間・空間・近似保証を評価する。
- 第7章: キュー、索引、優先度、重複排除状態をデータ構造と不変量へ落とす。
- 第8章: ノードと回線をグラフにし、経路・容量・割当てを最適化する。
- 第9章: 認証、重複防止、最終到達などの要件を論理式と検証手続きへ変換する。
- 第10章: 通知やログを情報源として捉え、圧縮率・誤り耐性・通信路容量を評価する。
- 第11章: 機密性・真正性・改ざん検知・鍵管理を攻撃者モデルと安全性ゲームで定義する。
- 第12章: 競合・順序・複製・合意を並行モデルと正当性条件へ変換する。
Part単位の背景説明へ戻る場合は、Part I、Part II、Part III、Part IVを参照してください。