理論計算機科学を読むための数学・証明・アルゴリズム基礎

到達判定表

使い方

この表は、各パートを完了したかを判定するための基準です。章を読んだだけでは完了としません。説明できる、証明できる、計算できる、実装または擬似コード化できるのいずれかで確認してください。

Core 到達判定

項目 到達条件 確認方法
集合 ⊆, ∪, ∩, \, P(A) を説明できる 3つの集合計算問題を解く
論理 含意、対偶、量化の否定を扱える 命題の否定を3問書く
関数 単射・全射・全単射を定義できる 具体例で判定する
関係 同値関係・半順序を検証できる 反射律等を確認する証明を書く
証明 直接証明・対偶証明・帰納法を使える 各1問を手書きで証明する
漸近記法 O, Ω, Θ を定義から説明できる 3つの関数比較を行う
擬似コード ループ・再帰の挙動を追える 再帰関数の停止性を説明する

Core 合格条件

次をすべて満たせば Core 完了です。

  • 前提診断 Q1-Q32 で 26/32 以上。
  • 証明領域 Q13-Q20 で 6/8 以上。
  • Core 演習 70問のうち 56問以上正答。
  • 証明問題について、ルーブリック平均 3.0点以上。
  • 「例をいくつか確認した」だけの回答で証明を代替していない。

Standard 到達判定

項目 到達条件 確認方法
グラフ グラフ・木・DAG・到達可能性を定義できる 小さいグラフで BFS/DFS を実行する
グラフ計算量 BFS/DFS が O(|V|+|E|) である理由を説明できる 隣接リスト前提で数える
組合せ 2^n, C(n,k), n! を使い分ける 状態数を3問見積もる
包除 重複を引く理由を説明できる 倍数カウント問題を解く
データ構造 ADT と実装を区別できる スタック・キュー・ヒープ・ハッシュ表を比較する
基本アルゴリズム 二分探索、ソート、Union-Find、DPの入口を説明できる 擬似コードまたは計算量を述べる
形式言語 Σ, Σ*, ε, 言語、DFA/NFA を読める DFAの5要素を書く

Standard 合格条件

次をすべて満たせば Standard 完了です。

  • 前提診断 Q33-Q60 で 22/28 以上。
  • Standard 演習 60問のうち 45問以上正答。
  • グラフ、組合せ、形式言語の3領域でそれぞれ70%以上。
  • ε と ∅、NFA と確率的オートマトン、ADT と実装を混同していない。

Extended 到達判定

項目 到達条件 確認方法
確率 条件付き確率、独立性、期待値を扱える Pr[A|B] と指示変数の問題を解く
数論 gcd、合同算術、逆元を計算できる Euclid互除法と逆元を計算する
代数 群・巡回群・体の記法を読める 小さい mod 群で例を挙げる
線形代数 行列積、ランク、F_2 を扱える F_2 行列を計算する
符号理論入口 Hamming距離、生成行列、検査行列を説明できる 小さい線形符号で計算する
並行性 状態遷移、非決定性、safety/livenessを説明できる 反例traceを作る
合意問題 一致性・妥当性・終了性を説明できる 故障モデルと条件を対応させる

Extended 合格条件

次をすべて満たせば Extended 完了です。

  • 前提診断 Q61-Q80 で 16/20 以上。
  • Extended 演習 80問のうち 56問以上正答。
  • 情報理論へ進むなら、確率と線形代数の章末確認で80%以上。
  • 暗号へ進むなら、数論・代数の章末確認で80%以上。
  • 並行計算へ進むなら、並行性と形式モデルの章末確認で80%以上。

統合到達判定

統合到達確認テストは50問です。

本体教科書への正式な進行判定は、共通の進行判定ポリシーを正本とします。

得点 判定 次の行動
43〜50 合計点ゲート達成 証明問題と対象章別 readiness のゲートを確認する
36〜42 合計点ゲート未達 弱点領域を1周してから再受験する
28〜35 部分的進行 Core/Standard の弱点を補強する
0〜27 進行非推奨 Coreから再学習する

証明問題 Q7〜Q10・Q23・Q49 が2/6以下の場合は、総合点に関係なく Core 第3章へ戻ってください。合計43/50以上でも、証明3/6と対象章別 readiness の両方を満たすまで進行不可です。

Edit this page on GitHub