付録C 本体教科書との対応表
目的
この対応表は、本教材の各章が『理論計算機科学教科書』のどの章の前提を補うかを示します。
対応表
| 本教材 | 補う前提 | 本体教科書で主に使う箇所 |
|---|---|---|
| 第1章 集合と論理 | 集合、部分集合、集合演算、命題、含意、量化記号 | 第1章、全章の定義・証明 |
| 第2章 関数と関係 | 関数、単射、全射、同値関係、半順序、到達可能性 | 第1章、第3章、第4章、第9章、第12章 |
| 第3章 証明技法 | 直接証明、対偶証明、背理法、場合分け、反例、帰納法、強い帰納法、構造帰納法、ループ不変条件 | 全章、とくに第3〜7章、第12章 |
| 第4章 漸近記法 | O、Ω、Θ、増加率、ループ計算量、対数時間、再帰式の入口 | 第5章、第6章、第7章、第8章、第11章 |
| 第5章 擬似コードと再帰 | 基本構文、配列、関数、再帰、停止性、探索、二分探索、不変条件 | 第2章、第4章、第6章、第7章 |
| 第6章 グラフと木 | グラフ、パス、閉路、木、DAG、BFS、DFS、到達可能性 | 第3章、第8章、第12章 |
| 第7章 組合せと数え上げ | 和の法則、積の法則、順列、組合せ、鳩ノ巣原理、包除原理、状態数、候補数 | 第5章、第6章、第8章、第10章、第11章 |
| 第8章 データ構造と基本アルゴリズム | 配列、リスト、スタック、キュー、ハッシュ表、ヒープ、Union-Find、グラフ表現、BFS/DFS、二分探索、DPの入口 | 第6章、第7章、第8章 |
| 第9章 形式言語の入口 | アルファベット、文字列、空文字列、言語、正規表現、文法、導出、DFA/NFA、判定問題の言語化 | 第3章、第4章、第5章 |
| 第10章 確率の基礎 | 標本空間、事象、条件付き確率、独立性、確率変数、期待値、指示変数、二項分布、確率的不等式 | 第10章、第11章、第12章 |
| 第11章 数論・代数の基礎 | 割り切り、gcd、Euclidの互除法、合同算術、逆元、群、巡回群、体、離散対数問題 | 第11章 |
| 第12章 線形代数の最小限 | ベクトル、行列、行列積、線形結合、線形独立、ランク、F_2、生成行列、検査行列、Hamming距離 |
第10章、第12章 |
| 第13章 並行性と形式モデルの入口 | 状態、遷移、非決定性、trace、safety、liveness、invariant、happens-before、合意問題、故障モデル | 第12章 |
本体 Part 別の推奨補強
Part I: 数学的基礎・計算理論の入口・形式言語
必要:
- 第1章 集合と論理
- 第2章 関数と関係
- 第3章 証明技法
- 第5章 擬似コードと再帰
- 第9章 形式言語の入口
特に構造帰納法は、文字列、文法、正規表現、構文木を扱う前に確認する。
Part II: 計算可能性・複雑性・アルゴリズム
必要:
- 第3章 証明技法
- 第4章 漸近記法
- 第5章 擬似コードと再帰
- 第7章 組合せと数え上げ
- 第8章 データ構造と基本アルゴリズム
- 第9章 形式言語の入口
計算量クラスを読む前に、O, Ω, Θ の違い、入力サイズ、候補数、判定問題を言語として表す考え方を確認する。
Part III: データ構造・グラフ・論理
必要:
- 第2章 関数と関係
- 第3章 証明技法
- 第4章 漸近記法
- 第5章 擬似コードと再帰
- 第6章 グラフと木
- 第7章 組合せと数え上げ
- 第8章 データ構造と基本アルゴリズム
グラフ到達可能性、探索、DAG、半順序、データ構造の計算量、候補数の見積もりが重要。
Part IV: 情報理論・暗号・並行計算
必要:
- 第7章 組合せと数え上げ
- 第10章 確率の基礎
- 第11章 数論・代数の基礎
- 第12章 線形代数の最小限
- 第13章 並行性と形式モデルの入口
情報理論では確率と F_2 上の線形代数、暗号では合同算術と群、並行計算では状態遷移と safety/liveness が主要な前提になる。
v0.8 時点の対応状況
| 領域 | 状態 |
|---|---|
| 確率 | 第10章として追加済み |
| 数論・代数 | 第11章として追加済み |
| 線形代数 | 第12章として追加済み |
| 並行性と形式モデル | 第13章として追加済み |
| 採点ルーブリック | 評価・到達判定に追加済み |
| 図表・Python実装ノート | 図表・Python実装ノートに追加済み |
| 用語索引・記号索引 | v0.7 で追加済み |
| 章間リンク・逆引き | v0.7 で追加済み |
評価導線
本体教科書へ進む前の判定には、次を使う。
| 目的 | ファイル |
|---|---|
| 前提診断の採点 | assessment/scoring-rubric.md |
| 到達判定 | assessment/attainment-criteria.md |
| 章単位の確認 | assessment/chapter-exit-checks.md |
| 弱点補強 | assessment/recovery-routes.md |
| 本体章別の進行可否 | assessment/main-textbook-readiness.md |
| 最終確認 | exercises/integrated-readiness-test.md |