理論計算機科学 学習進捗チェックリスト

使い方

このチェックリストは、理論計算機科学の学習進捗を自己評価するためのツールです。各項目について以下の基準で評価してください：

• ☐ 未学習
• ☑ 基礎理解（概念を説明できる）
• ☑☑ 応用可能（問題を解ける）
• ☑☑☑ 深い理解（他人に教えられる）

第1章 理論計算機科学への招待

基本概念

• アルゴリズムの定義を説明できる
• 計算量の概念を理解している
• 問題とインスタンスの区別ができる

漸近記法

• Big-O記法の定義を理解している
• Ω記法とΘ記法の違いを説明できる
• 具体的な関数の漸近的振る舞いを解析できる

アルゴリズム解析

• 時間計算量を計算できる
• 空間計算量を計算できる
• 最悪・平均・最良ケースを区別できる

Master定理

• Master定理の3つのケースを理解している
• 分割統治法の漸化式を解ける
• 定理の適用条件を判断できる

実践スキル

• 簡単なアルゴリズムの計算量を解析できる
• 効率的なアルゴリズムを選択できる
• 計算量のトレードオフを理解している

第2章 計算理論の基礎

チューリング機械

• チューリング機械の形式的定義を理解している
• 状態遷移図を描ける
• 簡単な言語を認識するTMを設計できる

計算と構成

• 構成（configuration）の概念を理解している
• 計算過程をトレースできる
• 受理・拒否・無限ループを区別できる

Church-Turingの提唱

• 提唱の内容を説明できる
• 他の計算モデルとの等価性を理解している
• 計算可能性の本質を把握している

TMの変種

• 多テープTMの動作を理解している
• 非決定性TMの概念を説明できる
• 変種間の等価性を理解している

万能チューリング機械

• 万能TMの意義を説明できる
• TMの符号化方法を理解している
• プログラム内蔵方式との関連を理解している

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

形式言語の基礎

• アルファベット、文字列、言語の定義を理解している
• 言語の演算（和、積、閉包）ができる
• 正規表現を書ける

有限オートマトン

• DFAの形式的定義を理解している
• NFAとDFAの違いを説明できる
• 具体的な言語のDFA/NFAを構成できる

正規言語

• 正規表現とDFAの等価性を理解している
• Pumping補題を使える
• 言語が正規でないことを証明できる

文脈自由言語

• CFGの定義と導出を理解している
• 導出木と曖昧性を説明できる
• CFGのPumping補題を使える

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

• PDAの動作原理を理解している
• CFGとPDAの等価性を知っている
• 簡単なPDAを設計できる

言語の階層

• Chomskyの階層を説明できる
• 各言語クラスの包含関係を理解している
• 言語クラスの判定ができる

第4章 計算可能性

決定可能性

• 決定可能と認識可能の違いを理解している
• 基本的な決定可能問題を知っている
• 決定アルゴリズムを設計できる

決定不能問題

• 停止問題を理解している
• 対角化論法を説明できる
• 他の決定不能問題を知っている

還元

• 多対一還元の概念を理解している
• 還元による決定不能性の証明ができる
• 還元の連鎖を理解している

Riceの定理

• 定理の内容を説明できる
• 定理の適用範囲を理解している
• 具体例に適用できる

計算可能関数

• 部分計算可能と計算可能の違いを理解している
• 再帰定理を知っている
• s-m-n定理を理解している

第5章 計算複雑性理論

時間複雑性

• 時間複雑性クラスを理解している
• P、EXPTIME等の定義を知っている
• 時間階層定理を理解している

P vs NP

• PとNPの定義を説明できる
• 検証による特徴付けを理解している
• P vs NP問題の意義を説明できる

NP完全性

• NP完全の定義を理解している
• Cook-Levinの定理を知っている
• 基本的なNP完全問題を知っている

多項式時間還元

• 還元の方法を理解している
• NP完全性の証明ができる
• 還元の設計ができる

空間複雑性

• 空間複雑性クラスを理解している
• Savitchの定理を知っている
• PSPACE完全問題を理解している

その他の複雑性

• 多項式階層を理解している
• 確率的複雑性クラスを知っている
• 対話型証明系の基礎を理解している

第6章 アルゴリズム

設計パラダイム

• 分割統治法を理解し実装できる
• 動的計画法を理解し実装できる
• グリーディ法を理解し実装できる

ソートアルゴリズム

• 基本的なソート（バブル、選択、挿入）を実装できる
• 効率的なソート（マージ、クイック、ヒープ）を実装できる
• 各アルゴリズムの特徴を説明できる

探索アルゴリズム

• 線形探索と二分探索を実装できる
• ハッシュ法を理解している
• 探索木での探索を理解している

動的計画法の応用

• 編集距離を計算できる
• ナップサック問題を解ける
• 最長共通部分列を求められる

グラフアルゴリズム

• 基本的な走査（DFS、BFS）を実装できる
• 最短路アルゴリズムを理解している
• 最小全域木を求められる

近似アルゴリズム

• 近似アルゴリズムの必要性を理解している
• 近似率の概念を説明できる
• 基本的な近似アルゴリズムを知っている

第7章 データ構造

基本データ構造

• 配列とリストの特徴を理解している
• スタックとキューを実装できる
• 各操作の計算量を分析できる

木構造

• 二分木の基本操作を実装できる
• 二分探索木を理解し実装できる
• 平衡木（AVL、赤黒木）の概念を理解している

ヒープ

• ヒープの性質を理解している
• ヒープソートを実装できる
• 優先度付きキューとして使える

ハッシュ法

• ハッシュ関数の設計を理解している
• 衝突解決法を説明できる
• ハッシュテーブルを実装できる

高度なデータ構造

• B木の概念を理解している
• Union-Findを実装できる
• トライ木を理解している

永続的データ構造

• 永続性の概念を理解している
• 関数型データ構造の基礎を知っている
• 応用例を説明できる

第8章 グラフ理論

グラフの基礎

• グラフの表現方法を理解している
• 基本的な用語を説明できる
• グラフの性質を判定できる

グラフ走査

• DFSを実装できる
• BFSを実装できる
• 走査の応用を理解している

最短路問題

• Dijkstra法を実装できる
• Bellman-Ford法を理解している
• Floyd-Warshall法を知っている

最小全域木

• Kruskal法を実装できる
• Prim法を実装できる
• Union-Findとの関連を理解している

ネットワークフロー

• 最大流問題を理解している
• Ford-Fulkerson法を知っている
• 最小カット定理を理解している

NP困難なグラフ問題

• ハミルトン路問題を理解している
• グラフ彩色問題を知っている
• 近似解法を理解している

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

命題論理

• 論理式の構文を理解している
• 真理値表を作成できる
• 論理的同値を判定できる

述語論理

• 量化子を正しく使える
• 自由変数と束縛変数を区別できる
• 論理式の意味を理解している

証明系

• 自然演繹を理解している
• 証明の健全性と完全性を説明できる
• 簡単な証明を構成できる

プログラム検証

• Hoare論理を理解している
• 事前・事後条件を書ける
• 不変条件を見つけられる

モデル検査

• 時相論理の基礎を理解している
• 状態遷移系をモデル化できる
• 基本的な性質を記述できる

形式的仕様記述

• 仕様記述の重要性を理解している
• 基本的な記法を知っている
• 簡単な仕様を書ける

第10章 情報理論

情報量とエントロピー

• 情報量の定義を理解している
• エントロピーを計算できる
• 条件付きエントロピーを理解している

情報源符号化

• 符号化の基本原理を理解している
• Huffman符号を構成できる
• 符号の効率を評価できる

通信路符号化

• 通信路モデルを理解している
• 通信路容量を計算できる
• Shannon の定理を理解している

誤り訂正符号

• 誤り検出と訂正の違いを理解している
• 簡単な符号を設計できる
• ハミング距離を計算できる

データ圧縮

• 可逆圧縮と非可逆圧縮を区別できる
• 基本的な圧縮手法を理解している
• 圧縮の限界を理解している

応用

• 暗号との関連を理解している
• 機械学習への応用を知っている
• 実用システムでの利用を理解している

第11章 暗号理論

暗号の基礎

• 暗号の基本要素を理解している
• 対称鍵と公開鍵の違いを説明できる
• 安全性の概念を理解している

古典暗号

• シーザー暗号を理解している
• 頻度分析による解読を知っている
• 古典暗号の限界を理解している

現代暗号

• DES/AESの概要を理解している
• ブロック暗号とストリーム暗号を区別できる
• 暗号モードを理解している

公開鍵暗号

• RSA暗号の原理を理解している
• 鍵配送問題を説明できる
• 電子署名を理解している

暗号プロトコル

• 認証プロトコルを理解している
• 鍵交換プロトコルを知っている
• ゼロ知識証明の概念を理解している

暗号の安全性

• 計算量的安全性を理解している
• 情報論的安全性を知っている
• 攻撃モデルを理解している

第12章 並行計算

並行性の基礎

• プロセスとスレッドを区別できる
• 並行性と並列性の違いを理解している
• 同期の必要性を説明できる

相互排除

• 臨界領域を理解している
• ミューテックスを使える
• デッドロックを理解している

同期プリミティブ

• セマフォを理解している
• モニタを説明できる
• 条件変数を使える

並行アルゴリズム

• 生産者消費者問題を解ける
• 読者書き手問題を理解している
• 哲学者の食事問題を知っている

分散システム

• 分散システムの特徴を理解している
• 合意問題を知っている
• CAP定理を理解している

並行データ構造

• ロックフリーの概念を理解している
• CASを知っている
• 並行性の正当性を理解している

総合評価

理論的理解

• 各分野の基本概念を説明できる
• 分野間の関連を理解している
• 理論の限界を認識している

実践的スキル

• 基本的なアルゴリズムを実装できる
• 問題に適した手法を選択できる
• 効率性を評価できる

応用能力

• 新しい問題に理論を適用できる
• 実世界の問題をモデル化できる
• 理論と実践を結びつけられる

発展的学習

• 最新の研究動向に興味がある
• 関連分野との接続を理解している
• 独自の問題設定ができる

学習アドバイス

効果的な学習方法

1. 理論と実践のバランス：概念を学んだら必ず実装してみる
2. 問題演習の重要性：各章の練習問題を解く
3. 相互関連の理解：章をまたいだ関連性を意識する
4. 応用例の探索：実世界での使用例を調べる

つまずきやすいポイント

1. 抽象概念の理解：具体例を多く見る
2. 証明の構成：典型的なパターンを学ぶ
3. 計算量解析：多くの例題を解く
4. 実装の詳細：擬似コードから始める

発展的学習への道

1. 原著論文を読む：重要な結果の原論文に挑戦
2. 実装プロジェクト：学んだ理論を使ったシステム開発
3. 競技プログラミング：アルゴリズムスキルの向上
4. 研究への参加：最新の問題に取り組む

このチェックリストを定期的に見直し、自分の理解度を確認しながら学習を進めてください。すべての項目を完璧にマスターする必要はありませんが、各分野の基本概念は確実に理解することを目指しましょう。