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

理論計算機科学の各章における学習目標と自己評価用チェックリストです。各項目を理解し、問題を解けるようになったらチェックしてください。

第1章: 数学的基礎

1.1 集合論 📚

基本概念

集合の概念と記法を理解している
要素の所属関係（∈, ∉）を正しく使える
部分集合（⊆, ⊊）の概念を理解している
空集合（∅）の性質を説明できる

集合演算

和集合（∪）の定義と性質を理解している
積集合（∩）の定義と性質を理解している
差集合（\）と対称差（⊕）を計算できる
ド・モルガンの法則を証明できる
べき集合の概念を理解している

実践問題

3つ以上の集合の複合演算を実行できる
ベン図を描いて集合関係を視覚化できる
集合の基数（要素数）を計算できる

1.2 関係と関数 🔄

関係

二項関係の定義を理解している
反射的・対称的・推移的関係を判定できる
同値関係と同値類を理解している
順序関係（半順序・全順序）を理解している

関数

関数の定義（定義域・値域・像）を理解している
単射・全射・全単射を判定できる
逆関数の存在条件を説明できる
合成関数を計算できる

実践問題

関数の単射性・全射性を証明できる
同値関係から商集合を構成できる
順序関係からハッセ図を描ける

1.3 論理学 🤔

命題論理

論理演算子（∧, ∨, ¬, →, ↔）を理解している
真理表を作成できる
論理的同値性を判定できる
CNF（連言標準形）とDNF（選言標準形）に変換できる

述語論理

量詞（∀, ∃）の意味を理解している
量詞の否定を正しく作れる
束縛変数と自由変数を区別できる
述語論理式を解釈できる

実践問題

日常言語を論理式に翻訳できる
論理式の充足可能性を判定できる
推論規則を使って証明できる

1.4 証明技法 ✅

基本的証明技法

直接証明の構造を理解している
対偶証明を適切に使える
背理法の手順を理解している
場合分けによる証明ができる

数学的帰納法

数学的帰納法の原理を理解している
基底ケースと帰納ステップを正しく設定できる
強帰納法（完全帰納法）を使える
構造帰納法を理解している

実践問題

不等式を数学的帰納法で証明できる
等式を数学的帰納法で証明できる
存在証明と非存在証明ができる

第1章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第2章: 計算理論の基礎

2.1 チューリング機械 🤖

基本概念

チューリング機械の構成要素を説明できる
状態遷移図を描ける
配置（configuration）の概念を理解している
計算の実行過程を追跡できる

チューリング機械の設計

簡単な言語を認識するTMを設計できる
基本的な計算（加算、乗算）を行うTMを設計できる
マルチテープTMの利点を理解している
非決定性TMの概念を理解している

実践問題

具体的なTMの動作をシミュレートできる
TMの等価性を示すことができる
TMの変種の計算能力を比較できる

2.2 計算可能性 💭

基本概念

計算可能関数の定義を理解している
Church-Turing仮説の意味を説明できる
チューリング完全性の概念を理解している
計算可能性の不変性テーゼを理解している

計算モデルの等価性

ラムダ計算とTMの等価性を理解している
再帰関数とTMの等価性を理解している
プログラミング言語の計算能力を判定できる

実践問題

与えられた関数が計算可能か判定できる
異なる計算モデル間での変換ができる
計算可能性の限界を説明できる

第2章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第3章: 形式言語とオートマトン理論

3.1 有限オートマトン 🔄

DFA（決定性有限オートマトン）

DFAの定義と構成要素を理解している
状態遷移図と状態遷移表を作成できる
DFAが受理する言語を決定できる
与えられた言語を受理するDFAを設計できる

NFA（非決定性有限オートマトン）

NFAの定義と動作原理を理解している
ε遷移の概念を理解している
NFAからDFAへの変換（部分集合構成法）ができる
NFAの実行をシミュレートできる

正規言語

正規言語の閉包性質を理解している
正規言語でない言語を識別できる
ポンピング補題を使って証明できる

実践問題

複雑な正規言語のDFA/NFAを設計できる
正規表現とオートマトンを相互変換できる
正規言語の決定問題を解ける

3.2 文脈自由言語 📝

文脈自由文法

CFGの定義と記法を理解している
導出と導出木の概念を理解している
文法の曖昧性を判定できる
与えられた言語のCFGを設計できる

プッシュダウンオートマトン

PDAの定義と動作原理を理解している
スタックの使用方法を理解している
CFGとPDAの等価性を理解している
PDAの実行をシミュレートできる

文脈自由言語の性質

CFL閉包性質を理解している
CFLのポンピング補題を使える
CFLと正規言語の関係を理解している

実践問題

プログラミング言語構文のCFGを書ける
文法の曖昧性を除去できる
CFLでない言語を証明できる

3.3 チョムスキー階層 📊

言語の分類

型0, 1, 2, 3文法の特徴を理解している
各クラスの計算モデルとの対応を知っている
言語階層の包含関係を理解している
各クラスの決定問題の複雑性を知っている

実践問題

与えられた言語がどのクラスに属するか判定できる
異なるクラス間の分離を示す例を挙げられる

第3章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第4章: 計算可能性

4.1 決定可能性 ✅

基本概念

決定可能言語の定義を理解している
半決定可能言語（認識可能言語）との違いを理解している
列挙可能性と計算可能性の関係を理解している

決定可能な問題

正規言語の決定問題が決定可能であることを理解している
CFLの一部決定問題が決定可能であることを理解している
算術の決定可能な部分を知っている

4.2 決定不可能性 ❌

停止問題

停止問題の定義を理解している
停止問題が決定不可能であることを証明できる
対角化論法の仕組みを理解している

還元による証明

多対一還元の概念を理解している
チューリング還元の概念を理解している
還元を使って決定不可能性を証明できる

その他の決定不可能問題

受理性問題が決定不可能であることを理解している
空性問題が決定不可能であることを理解している
Riceの定理を理解し適用できる

実践問題

新しい決定不可能問題を還元で証明できる
決定可能性と半決定可能性を判定できる
Riceの定理の適用条件を確認できる

4.3 計算可能性の応用 🔧

プログラム検証

静的解析の限界を理解している
プログラム等価性問題の決定不可能性を理解している
自動定理証明の限界を理解している

第4章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第5章: 計算複雑性理論

5.1 時間複雑性 ⏱️

基本概念

時間複雑性関数の定義を理解している
最悪時間複雑性と平均時間複雑性の違いを理解している
多項式時間の概念を理解している

複雑性クラス

クラスPの定義を理解している
クラスEXPTIMEの定義を理解している
時間階層定理を理解している

5.2 非決定性と NP クラス 🤝

NP クラス

非決定性チューリング機械の概念を理解している
NPクラスの定義（検証器による定義）を理解している
P ⊆ NP の関係を理解している

NP完全性

NP困難とNP完全の定義を理解している
多項式時間還元の概念を理解している
SATがNP完全であることを理解している（Cookの定理）

代表的なNP完全問題

3-SAT問題を理解している
クリーク問題を理解している
独立集合問題を理解している
頂点被覆問題を理解している
ハミルトン経路問題を理解している
巡回セールスマン問題（TSP）を理解している

実践問題

新しい問題のNP完全性を証明できる
NP完全問題間の還元を構成できる
P vs NP問題の意義を説明できる

5.3 空間複雑性 💾

空間複雑性クラス

PSPACEクラスの定義を理解している
NP ⊆ PSPACE の関係を理解している
Savitchの定理を理解している

PSPACE完全問題

量化ブール式（QBF）問題を理解している
ゲーム理論と複雑性の関係を理解している

5.4 その他の複雑性クラス 🔍

多項式階層

Σᵖₖ, Πᵖₖ, Δᵖₖクラスの定義を理解している
多項式階層の崩壊の概念を理解している

確率的複雑性

RPクラスとBPPクラスの基本概念を理解している

第5章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第6章: アルゴリズムの数学的解析

6.1 漸近記法 📈

Big-O記法

O, Ω, Θ記法の定義を理解している
o, ω記法の定義を理解している
漸近的比較の基本性質を理解している

実践的使用

アルゴリズムの時間複雑性を正しく表現できる
複数のアルゴリズムの効率性を比較できる
漸近記法を使った証明ができる

6.2 分割統治法 ✂️

基本概念

分割統治法の設計パラダイムを理解している
Master定理の内容と適用条件を理解している
再帰関係式の解法を理解している

代表的アルゴリズム

マージソートの動作と解析を理解している
クイックソートの動作と解析を理解している
二分探索の動作と解析を理解している
行列乗算（Strassenアルゴリズム）を理解している

実践問題

新しい分割統治アルゴリズムを設計できる
Master定理を使って複雑性を解析できる
再帰関係式を解くことができる

6.3 動的計画法 🎯

基本概念

最適部分構造の概念を理解している
重複部分問題の概念を理解している
メモ化の技法を理解している

代表的問題

最長共通部分列（LCS）問題を解ける
ナップサック問題を解ける
最短経路問題（Floyd-Warshall）を解ける
連鎖行列乗算問題を解ける

実践問題

新しい問題を動的計画法で解ける
時間・空間複雑性を最適化できる
解の復元ができる

6.4 貪欲法 🎰

基本概念

貪欲選択性質を理解している
最適部分構造との関係を理解している
貪欲法が最適解を保証する条件を理解している

代表的アルゴリズム

最短路問題（Dijkstraアルゴリズム）を理解している
最小全域木（Kruskal, Primアルゴリズム）を理解している
活動選択問題を理解している

実践問題

貪欲法の正当性を証明できる
反例を使って貪欲法の限界を示せる

第6章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第7章: データ構造の理論

7.1 基本データ構造 📊

線形データ構造

配列の時間・空間複雑性を理解している
連結リストの操作と複雑性を理解している
スタックとキューの操作を理解している

木構造

二分木の性質と操作を理解している
二分探索木の操作と複雑性を理解している
平衡二分探索木の必要性を理解している

7.2 高度なデータ構造 🏗️

平衡木

AVL木の回転操作を理解している
赤黒木の性質を理解している
B-tree, B+treeの構造を理解している

ハッシュテーブル

ハッシュ関数の性質を理解している
衝突解決法（チェイン法、オープンアドレス法）を理解している
負荷率と性能の関係を理解している

ヒープ

ヒープの性質と操作を理解している
ヒープソートの動作を理解している
優先度付きキューの実装を理解している

Union-Find構造

Union-Find の基本操作を理解している
経路圧縮とrank結合を理解している
逆アッカーマン関数による解析を理解している

実践問題

適切なデータ構造を選択できる
データ構造の変種を設計できる
償却解析ができる

第7章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第8章: グラフ理論とネットワーク

8.1 グラフの基本概念 🌐

基本定義

グラフの定義と種類を理解している
次数、経路、サイクルの概念を理解している
連結性と強連結性を理解している
平面グラフと非平面グラフの概念を理解している

グラフの表現

隣接行列と隣接リストの特徴を理解している
表現方法の時間・空間効率を比較できる

8.2 グラフ探索 🔍

探索アルゴリズム

深さ優先探索（DFS）の動作と解析を理解している
幅優先探索（BFS）の動作と解析を理解している
トポロジカルソートを理解している

強連結成分

Kosarajuアルゴリズムを理解している
Tarjanアルゴリズムを理解している

8.3 最短経路問題 🛣️

単一始点最短経路

Dijkstraアルゴリズムの動作と解析を理解している
Bellman-Fordアルゴリズムを理解している
負の重みを持つ辺の扱いを理解している

全点対最短経路

Floyd-Warshallアルゴリズムを理解している
Johnsonアルゴリズムを理解している

8.4 最小全域木 🌳

最小全域木アルゴリズム

Kruskalアルゴリズムの動作と正当性を理解している
Primアルゴリズムの動作と正当性を理解している
カット性質とサイクル性質を理解している

8.5 ネットワークフロー 💧

最大流問題

最大流最小カットの定理を理解している
Ford-Fulkersonアルゴリズムを理解している
Edmonds-Karpアルゴリズムを理解している

二部マッチング

二部グラフの最大マッチング問題を理解している
Königの定理を理解している

8.6 特殊なグラフ問題 🧩

NP完全問題

ハミルトン経路・サイクル問題を理解している
グラフ彩色問題を理解している
クリーク問題と独立集合問題を理解している

実践問題

実問題をグラフ問題にモデル化できる
適切なアルゴリズムを選択できる
グラフアルゴリズムの計算量を解析できる

第8章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第9章: 論理学・形式的手法

9.1 命題論理・述語論理の応用 🤖

SAT問題

SAT問題の定義と重要性を理解している
3-SATのNP完全性を理解している
SATソルバーの基本原理を理解している

論理プログラミング

Hornクローズと論理プログラミングの関係を理解している
単一化（unification）の概念を理解している

9.2 時相論理 ⏰

線形時相論理（LTL）

LTLの基本演算子を理解している
LTL式の意味を理解している
安全性と活性性の性質を理解している

計算木論理（CTL）

CTLの基本演算子を理解している
CTLとLTLの表現力の違いを理解している

9.3 モデル検査 🔍

基本概念

モデル検査の基本アイデアを理解している
Kripke構造の概念を理解している
状態空間爆発問題を理解している

モデル検査アルゴリズム

CTLモデル検査アルゴリズムの基本を理解している
反例生成の概念を理解している

9.4 プログラム検証 ✅

Hoare論理

事前条件・事後条件の概念を理解している
Hoare三段論法を理解している
最弱事前条件の計算方法を理解している

不変条件

ループ不変条件の概念を理解している
不変条件を使った証明方法を理解している

実践問題

簡単なプログラムの正当性を証明できる
形式仕様を書ける
検証条件を生成できる

第9章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第10章: 情報理論

10.1 情報量とエントロピー 📊

基本概念

情報量の定義と意味を理解している
エントロピーの定義と性質を理解している
結合エントロピーと条件付きエントロピーを理解している
相互情報量の概念を理解している

エントロピーの性質

エントロピーの最大値と最小値を理解している
連鎖律を理解している
データ処理不等式を理解している

10.2 情報源符号化 📝

符号化の基本概念

符号の定義と性質を理解している
平均符号長の概念を理解している
クラフトの不等式を理解している

最適符号化

情報源符号化定理を理解している
ハフマン符号化の動作と最適性を理解している
算術符号化の基本概念を理解している

10.3 通信路符号化 📡

通信路の概念

離散無記憶通信路の定義を理解している
通信路容量の概念を理解している
二元対称通信路（BSC）を理解している

誤り訂正符号

線形符号の基本概念を理解している
ハミング距離と誤り訂正能力の関係を理解している
ハミング符号の構成を理解している

通信路符号化定理

Shannonの通信路符号化定理を理解している
信頼性関数の概念を理解している

10.4 情報理論の応用 🔧

データ圧縮

可逆圧縮と非可逆圧縮の違いを理解している
LZ77、LZ78アルゴリズムの基本を理解している

暗号理論への応用

完全秘匿性の概念を理解している
情報理論的安全性を理解している

第10章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第11章: 暗号理論の数学的基礎

11.1 古典暗号 🔐

基本概念

暗号系の基本構成要素を理解している
完全秘匿性（perfect secrecy）の定義を理解している
一回限りパッド（one-time pad）を理解している

古典的暗号方式

シーザー暗号の動作と脆弱性を理解している
ヴィジュネル暗号の動作と解析を理解している
頻度分析による暗号解読を理解している

11.2 現代暗号の基礎 🛡️

対称鍵暗号

ブロック暗号の基本概念を理解している
DESとAESの基本構造を理解している
暗号利用モード（ECB, CBC, CTRなど）を理解している

公開鍵暗号

公開鍵暗号の基本アイデアを理解している
RSA暗号の動作原理を理解している
楕円曲線暗号の基本概念を理解している

11.3 暗号学的プリミティブ 🧱

ハッシュ関数

暗号学的ハッシュ関数の性質を理解している
一方向性、衝突耐性、第二原像耐性を理解している
SHA-256の基本構造を理解している

デジタル署名

デジタル署名の概念と要求事項を理解している
RSA署名の動作を理解している
ハッシュ関数と署名の組み合わせを理解している

11.4 暗号学的証明 📜

安全性定義

計算量的安全性の概念を理解している
IND-CPA、IND-CCAなどの安全性定義を理解している
ゲームベース証明の基本を理解している

困難性仮定

素因数分解問題の困難性を理解している
離散対数問題の困難性を理解している
これらの仮定に基づく暗号方式を理解している

11.5 高度な暗号技術 🚀

ゼロ知識証明

ゼロ知識証明の基本概念を理解している
完全性、健全性、ゼロ知識性を理解している

同型暗号

同型暗号の基本アイデアを理解している
加法同型暗号と乗法同型暗号を理解している

第11章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

第12章: 並行計算の理論

12.1 並行計算モデル ⚡

基本概念

並行性と並列性の違いを理解している
プロセスとスレッドの概念を理解している
共有メモリモデルと分散メモリモデルを理解している

同期メカニズム

ミューテックス（mutex）の概念を理解している
セマフォの動作と使用法を理解している
モニターの概念を理解している

12.2 並行プログラムの正当性 ✅

安全性と活性性

安全性（safety）の概念を理解している
活性性（liveness）の概念を理解している
デッドロックとライブロックの違いを理解している

相互排除

相互排除問題の定義を理解している
Peterson アルゴリズムを理解している
Dekkerアルゴリズムを理解している

12.3 分散アルゴリズム 🌐

基本概念

分散システムの特徴を理解している
メッセージパッシングモデルを理解している
分散アルゴリズムの複雑性尺度を理解している

分散合意

分散合意問題の定義を理解している
FLPの不可能性結果を理解している
部分同期モデルでの解決可能性を理解している

ビザンチン障害への耐性

ビザンチン将軍問題を理解している
ビザンチン合意の下界を理解している
実用的ビザンチン障害耐性（PBFT）の基本を理解している

12.4 並行データ構造 📊

無ロックデータ構造

無ロック（lock-free）の概念を理解している
待機不要（wait-free）の概念を理解している
Compare-and-Swap（CAS）操作を理解している

線形化可能性

線形化可能性（linearizability）の定義を理解している
順序一貫性との違いを理解している

12.5 並行システムの検証 🔍

モデル検査

並行システムの状態空間を理解している
Promela/SPINによるモデル検査を理解している
部分順序削減の概念を理解している

プロセス代数

CCS（Calculus of Communicating Systems）の基本を理解している
π計算の基本概念を理解している

第12章の理解度: □ 90%以上　□ 70-89%　□ 50-69%　□ 50%未満

全体的な理解度評価 📋

理論の統合的理解

異なる章の内容の関連性を理解している
理論計算機科学全体の体系を把握している
実世界の問題と理論の関係を説明できる

問題解決能力

新しい問題に理論を適用できる
複数の理論を組み合わせて問題を解決できる
理論的限界と実用的解決法のバランスを取れる

研究・応用への準備

最新の研究論文を読む基礎ができている
理論計算機科学の研究分野を理解している
実装と理論の橋渡しができる

学習継続のための行動計画 📅

短期目標（1-3ヶ月）

理解度が70%未満の章を重点的に復習
実装練習を通じて理論の理解を深める
応用例を調べて理論の有用性を確認

中期目標（3-6ヶ月）

より高度な教科書や論文に挑戦
関連する数学分野（代数、解析など）を学習
実際のプロジェクトで理論を活用

長期目標（6ヶ月以上）

研究や専門的実務での応用
理論計算機科学の最新動向をフォロー
新しい理論の学習と既習内容の発展

この学習進捗チェックリストを定期的に見直し、自分の理解度を客観的に評価することで、効果的な学習を継続してください。理論計算機科学は奥深い分野ですが、着実に積み重ねることで必ず習得できます。