付録

本書の学習をサポートする補助資料を提供します。

付録一覧

付録A: 数学記法ガイド

本書で使用する数学記法の統一ガイドです。理論計算機科学で一般的に使用される記法に準拠しています。

• 集合論記号
• 論理記号
• 関数記法
• 漸近記法（Big-O記法）
• グラフ理論記法
• 形式言語記法
• 複雑性理論記法
• 証明記法

付録B: アルゴリズム実装例

本書で学習する理論的アルゴリズムのPython実装例と複雑性解析を示します。

• 第1章: 数学的基礎のアルゴリズム
• 第3章: オートマトンシミュレーター
• 第5章: NP完全問題の実装
• 第6章: 分割統治、動的計画法、貪欲法
• 第8章: グラフアルゴリズム

付録C: 練習問題解答

本書第1〜12章の各章末に掲載された練習問題の解答と解説を示します。

• 第1章: 数学的基礎の問題解答
• 第2章: 計算理論の基礎の問題解答
• 第3章: 形式言語とオートマトン理論の問題解答
• 第4章: 計算可能性の問題解答
• 第5章: 計算複雑性理論の問題解答
• 第6章: アルゴリズム解析の問題解答
• 第7章: データ構造の理論の問題解答
• 第8章: グラフ理論とネットワークの問題解答
• 第9章: 論理学と形式的手法の問題解答
• 第10章: 情報理論の問題解答
• 第11章: 暗号理論の数学的基礎の問題解答
• 第12章: 並行計算の理論の問題解答

付録D: 用語集・索引

理論計算機科学で使用される専門用語の日英対訳と詳細な説明です。

• アルファベット順用語集
• 記号索引
• 概念別索引

付録E: 実世界への応用例

理論計算機科学の各章で学習する理論が、実際の技術やシステムでどのように活用されているかを示します。

• 暗号システム、データベース、機械学習
• コンパイラ、ネットワーク、セキュリティ
• 分散システム、ブロックチェーン

付録F: 学習進捗チェックリスト

理論計算機科学の各章における学習目標と自己評価用チェックリストです。

• 章別学習目標
• 理解度チェックポイント
• 学習継続のための行動計画

付録G: AI/ML と理論計算機科学の接続

機械学習（ML）を理論計算機科学（TCS）の観点で整理し、仮定を明示して議論するための概説です。

• PAC学習とVC次元（サンプル複雑性の直観）
• 学習/最適化の計算量（「学べる」と「効率よく学べる」の差）
• 情報理論（交差エントロピー/KL/相互情報量）との接続

これらの付録を活用して、理論計算機科学の学習を効果的に進めてください。理論の理解だけでなく、実践的な応用力も身につけることで、より深い学習成果を得ることができます。