本体教科書 readiness checklist
目的
本体教科書の各章へ入る前に、該当する前提が揃っているかを確認します。ここで「いいえ」が多い場合は、該当する補助教材の章へ戻ってください。
この章別checklistは、共通の進行判定ポリシーにおける最終ゲートです。前提診断や統合テストの総合得点が基準以上でも、対象章の進行条件または「不可」となる必須項目を満たさない場合は進行できません。
第1章 数学的基礎へ進む前
| 確認項目 | 必要章 |
|---|---|
| 集合、部分集合、冪集合を説明できる | 第1章 |
| 命題論理と述語論理の記号を読める | 第1章 |
| 量化記号の否定を変形できる | 第1章 |
| 関数・関係・同値関係・順序を説明できる | 第2章 |
| 直接証明・対偶証明・帰納法を書ける | 第3章 |
進行条件: すべて「はい」。
計算可能性・形式言語へ進む前
| 確認項目 | 必要章 |
|---|---|
| 文字列と文字列集合を区別できる | 第9章 |
Σ, Σ*, ε, ∅ を区別できる |
第9章 |
| 再帰的定義に対して構造帰納法を使える | 第3章、第9章 |
| DFA/NFA の5要素と受理条件を説明できる | 第9章 |
| 判定問題を言語として表せる | 第9章 |
進行条件: 5項目中4項目以上。ε と ∅ を混同している場合は不可。
複雑性理論へ進む前
| 確認項目 | 必要章 |
|---|---|
O, Ω, Θ の定義を説明できる |
第4章 |
| 多項式時間と指数時間の違いを説明できる | 第4章 |
| 判定問題と言語の対応を説明できる | 第9章 |
| グラフ・SAT的な状態空間を数えられる | 第6章、第7章 |
| 簡単な帰着の構造を読める | 第3章、第9章 |
進行条件: 5項目中4項目以上。漸近記法が弱い場合は不可。
アルゴリズム解析へ進む前
| 確認項目 | 必要章 |
|---|---|
| 擬似コードを逐次実行できる | 第5章 |
| ループの反復回数を数えられる | 第4章、第5章 |
| 再帰関数の停止性を説明できる | 第5章 |
| グラフ探索の計算量を説明できる | 第6章 |
| データ構造の操作計算量を説明できる | 第8章 |
進行条件: すべて「はい」。
データ構造理論へ進む前
| 確認項目 | 必要章 |
|---|---|
| ADT と実装を区別できる | 第8章 |
| 配列、リスト、スタック、キューを説明できる | 第5章、第8章 |
| ハッシュ表の平均・最悪計算量を説明できる | 第8章 |
| ヒープの操作計算量を説明できる | 第8章 |
| 木構造とグラフの基本を説明できる | 第6章 |
進行条件: 5項目中4項目以上。
グラフ理論・ネットワークへ進む前
| 確認項目 | 必要章 |
|---|---|
| グラフを集合で定義できる | 第6章 |
| パス、閉路、連結性、到達可能性を説明できる | 第6章 |
| 木の基本性質を説明できる | 第6章 |
| BFS/DFS を実行できる | 第6章 |
| 組合せ的にパスや状態数を見積もれる | 第7章 |
進行条件: すべて「はい」。
論理・形式手法へ進む前
| 確認項目 | 必要章 |
|---|---|
| 命題論理・述語論理の式を読める | 第1章 |
| 量化と含意のスコープを扱える | 第1章 |
| 関係・順序・到達可能性を説明できる | 第2章、第6章 |
| 証明技法を使い分けられる | 第3章 |
| 状態遷移と不変条件を説明できる | 第13章 |
進行条件: 5項目中4項目以上。量化記号が弱い場合は不可。
情報理論へ進む前
| 確認項目 | 必要章 |
|---|---|
| 条件付き確率と独立性を説明できる | 第10章 |
| 期待値と指示変数を使える | 第10章 |
| 総和記号に抵抗がない | 第4章、第10章 |
| Hamming距離を計算できる | 第12章 |
F_2 上のベクトル・行列を計算できる |
第12章 |
| 組合せ数で符号語数を見積もれる | 第7章 |
進行条件: 6項目中5項目以上。確率が弱い場合は不可。
暗号へ進む前
| 確認項目 | 必要章 |
|---|---|
| 合同算術の定義を説明できる | 第11章 |
| gcd と Euclid互除法を使える | 第11章 |
| 逆元の存在条件を説明できる | 第11章 |
| 群・巡回群・体の記法を読める | 第11章 |
| 鍵空間や探索空間を数えられる | 第7章 |
| 計算量の支配項を説明できる | 第4章 |
| 確率的な成功確率を読める | 第10章 |
進行条件: 7項目中6項目以上。合同算術・逆元が弱い場合は不可。
並行計算へ進む前
| 確認項目 | 必要章 |
|---|---|
| 関係と半順序を説明できる | 第2章 |
| 状態遷移システムを定義できる | 第13章 |
| 到達可能性をグラフとして見られる | 第6章、第13章 |
| 不変条件を証明の道具として使える | 第3章、第13章 |
| 非決定性と確率を区別できる | 第13章 |
| safety と liveness を反例で区別できる | 第13章 |
| 合意問題の条件を説明できる | 第13章 |
進行条件: 7項目中6項目以上。safety/liveness の区別が曖昧な場合は不可。
進行判定の記録テンプレート
日付:
本体章:
該当前提章:
チェック項目数:
YES数:
NO項目:
補強する章:
補強後の再判定日:
進行可否:
進行可否を記録すると、途中で詰まったときに原因を戻って分析できます。