コンピュータサイエンスの理論と数学的基礎

目次

第1章 数学的基礎

1.1 集合論

• 1.1.1 基本概念
• 1.1.2 集合演算
• 1.1.3 集合の濃度

1.2 論理学

• 1.2.1 命題論理
• 1.2.2 述語論理

1.3 証明技法

• 1.3.1 直接証明
• 1.3.2 対偶による証明
• 1.3.3 背理法
• 1.3.4 数学的帰納法

1.4 関係と関数

• 1.4.1 関係
• 1.4.2 関数

1.5 グラフ理論の基礎

• 1.5.1 グラフの定義
• 1.5.2 グラフの基本概念
• 1.5.3 特殊なグラフ

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

第2章 計算理論の基礎

2.1 計算モデル

• 2.1.1 チューリング機械の直観的理解
• 2.1.2 チューリング機械の形式的定義
• 2.1.3 チューリング機械の構成と計算
• 2.1.4 チューリング機械の例

2.2 計算可能性

• 2.2.1 チューリング計算可能関数
• 2.2.2 部分関数と計算可能性
• 2.2.3 Church-Turingの提唱

2.3 決定可能性

• 2.3.1 言語と決定問題
• 2.3.2 決定可能言語
• 2.3.3 認識可能言語

2.4 チューリング機械の変種

• 2.4.1 多テープチューリング機械
• 2.4.2 非決定性チューリング機械
• 2.4.3 線形拘束オートマトン
• 2.4.4 確率的チューリング機械

2.5 万能チューリング機械

• 2.5.1 チューリング機械の符号化
• 2.5.2 万能チューリング機械の構成
• 2.5.3 万能性の意義

2.6 計算可能性の基本定理

• 2.6.1 対角化言語
• 2.6.2 認識可能だが決定可能でない言語

2.7 計算の階層

• 2.7.1 言語クラスの包含関係
• 2.7.2 計算可能関数の性質

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

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

3.1 形式言語

• 3.1.1 基本定義
• 3.1.2 文字列の演算
• 3.1.3 言語の演算

3.2 有限オートマトン

• 3.2.1 決定性有限オートマトン（DFA）
• 3.2.2 非決定性有限オートマトン（NFA）
• 3.2.3 ε-NFA
• 3.2.4 DFAとNFAの等価性

3.3 正規言語

• 3.3.1 正規表現
• 3.3.2 正規言語の特徴付け
• 3.3.3 正規言語の閉包性
• 3.3.4 正規言語の判定問題

3.4 正規言語の限界

• 3.4.1 Pumping補題
• 3.4.2 非正規言語の例
• 3.4.3 Myhill-Nerodの定理

3.5 文脈自由言語

• 3.5.1 文脈自由文法
• 3.5.2 導出木と曖昧性
• 3.5.3 文脈自由言語の標準形
• 3.5.4 CFGのPumping補題

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

• 3.6.1 PDAの定義
• 3.6.2 PDAの受理方式
• 3.6.3 CFGとPDAの等価性

3.7 文脈自由言語の性質

• 3.7.1 閉包性
• 3.7.2 決定問題
• 3.7.3 決定性文脈自由言語

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

第4章 計算可能性理論

4.1 決定不能問題

• 4.1.1 停止問題
• 4.1.2 対角化言語
• 4.1.3 受理問題

4.2 還元可能性

• 4.2.1 多対一還元
• 4.2.2 還元による決定不能性の証明
• 4.2.3 チューリング還元

4.3 再帰的可算言語の階層

• 4.3.1 言語クラスの包含関係
• 4.3.2 言語の算術階層
• 4.3.3 Postの定理

4.4 Riceの定理

• 4.4.1 チューリング機械の性質
• 4.4.2 Riceの定理の主張と証明
• 4.4.3 Riceの定理の応用

4.5 計算可能関数

• 4.5.1 部分再帰関数
• 4.5.2 計算可能性の同値性
• 4.5.3 不動点定理

4.6 相対計算可能性

• 4.6.1 オラクルチューリング機械
• 4.6.2 相対化
• 4.6.3 チューリング次数

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

第5章 計算複雑性理論

5.1 時間複雑性

• 5.1.1 計算時間の定義
• 5.1.2 漸近記法
• 5.1.3 時間複雑性クラス
• 5.1.4 多テープ機械と時間複雑性

5.2 非決定性と NP

• 5.2.1 非決定性時間複雑性
• 5.2.2 検証による NP の特徴付け
• 5.2.3 NP の例
• 5.2.4 coNP

5.3 P vs NP 問題

• 5.3.1 問題の定式化
• 5.3.2 NP 完全性
• 5.3.3 Cook-Levin の定理
• 5.3.4 NP完全問題の連鎖

5.4 空間複雑性

• 5.4.1 空間複雑性の定義
• 5.4.2 空間の基本的性質
• 5.4.3 空間と時間の関係
• 5.4.4 PSPACE完全性

5.5 多項式階層

• 5.5.1 階層の定義
• 5.5.2 階層の性質
• 5.5.3 完全問題

5.6 確率的計算クラス

• 5.6.1 BPP（有界誤り確率多項式時間）
• 5.6.2 その他の確率的クラス
• 5.6.3 確率的計算の脱乱択化

5.7 回路複雑性

• 5.7.1 ブール回路
• 5.7.2 回路複雑性クラス
• 5.7.3 下界

5.8 対話型証明系

• 5.8.1 対話型証明の定義
• 5.8.2 IP の能力
• 5.8.3 ゼロ知識証明

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

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

6.1 漸近的解析

• 6.1.1 最悪時間解析
• 6.1.2 平均時間解析
• 6.1.3 償却解析
• 6.1.4 確率的解析

6.2 分割統治法

• 6.2.1 分割統治の一般形
• 6.2.2 マスター定理
• 6.2.3 分割統治の例
• 6.2.4 分割統治の最適性

6.3 動的計画法

• 6.3.1 最適部分構造
• 6.3.2 部分問題の重複
• 6.3.3 動的計画法の設計手順
• 6.3.4 最適性の原理

6.4 貪欲アルゴリズム

• 6.4.1 貪欲選択性
• 6.4.2 マトロイド理論
• 6.4.3 貪欲アルゴリズムの例
• 6.4.4 貪欲法の限界

6.5 高度な解析技法

• 6.5.1 生成関数を用いた解析
• 6.5.2 確率的解析の高度な手法
• 6.5.3 線形計画法による解析

6.6 並列アルゴリズムの解析

• 6.6.1 並列計算モデル
• 6.6.2 Brentの定理
• 6.6.3 並列アルゴリズムの例

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

第7章 データ構造の理論

7.1 抽象データ型

• 7.1.1 代数的仕様
• 7.1.2 操作の複雑性
• 7.1.3 下界の証明

7.2 基本的なデータ構造

• 7.2.1 配列とリスト
• 7.2.2 二分探索木
• 7.2.3 ヒープ
• 7.2.4 ハッシュ表

7.3 平衡木

• 7.3.1 AVL木
• 7.3.2 赤黒木
• 7.3.3 B木
• 7.3.4 スプレー木

7.4 高度なデータ構造

• 7.4.1 フィボナッチヒープ
• 7.4.2 Union-Find構造
• 7.4.3 永続的データ構造
• 7.4.4 効率的な文字列データ構造

7.5 キャッシュ効率的データ構造

• 7.5.1 キャッシュモデル
• 7.5.2 B木の I/O 解析
• 7.5.3 キャッシュ無視アルゴリズム

7.6 確率的データ構造

• 7.6.1 スキップリスト
• 7.6.2 ブルームフィルタ
• 7.6.3 Count-Min スケッチ

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

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

8.1 グラフの基本理論

• 8.1.1 グラフの表現と基本概念
• 8.1.2 基本的なグラフの性質
• 8.1.3 グラフの走査
• 8.1.4 連結性

8.2 最短路問題

• 8.2.1 単一始点最短路
• 8.2.2 全点対最短路
• 8.2.3 特殊なグラフでの最短路

8.3 最小全域木

• 8.3.1 最小全域木の性質
• 8.3.2 Kruskalのアルゴリズム
• 8.3.3 Primのアルゴリズム

8.4 ネットワークフロー

• 8.4.1 最大フロー問題
• 8.4.2 Ford-Fulkerson法
• 8.4.3 効率的な実装
• 8.4.4 応用

8.5 マッチング理論

• 8.5.1 二部グラフのマッチング
• 8.5.2 最大マッチングアルゴリズム
• 8.5.3 完全マッチング
• 8.5.4 安定マッチング

8.6 グラフの彩色

• 8.6.1 頂点彩色
• 8.6.2 辺彩色
• 8.6.3 平面グラフの彩色
• 8.6.4 彩色アルゴリズム

8.7 特殊なグラフクラス

• 8.7.1 平面グラフ
• 8.7.2 木構造
• 8.7.3 弦グラフ

8.8 ランダムグラフ

• 8.8.1 Erdős-Rényiモデル
• 8.8.2 小世界ネットワーク
• 8.8.3 スケールフリーネットワーク

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

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

9.1 命題論理

• 9.1.1 構文と意味論
• 9.1.2 論理的帰結と同値
• 9.1.3 標準形
• 9.1.4 命題論理の決定手続き
• 9.1.5 健全性と完全性
• 9.1.6 コンパクト性定理

9.2 一階述語論理

• 9.2.1 構文
• 9.2.2 意味論
• 9.2.3 前束標準形
• 9.2.4 Skolem化
• 9.2.5 完全性定理
• 9.2.6 決定不能性

9.3 時相論理

• 9.3.1 線形時相論理（LTL）
• 9.3.2 計算木論理（CTL）
• 9.3.3 モデル検査
• 9.3.4 公平性

9.4 プログラム検証

• 9.4.1 Hoare論理
• 9.4.2 推論規則
• 9.4.3 最弱事前条件
• 9.4.4 プログラムの全正当性
• 9.4.5 分離論理

9.5 形式的仕様記述

• 9.5.1 代数的仕様
• 9.5.2 Z記法
• 9.5.3 時相論理による仕様

9.6 定理証明支援系

• 9.6.1 対話型定理証明
• 9.6.2 自動定理証明
• 9.6.3 証明の形式化

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

第10章 情報理論

10.1 情報量とエントロピー

• 10.1.1 情報量の定義
• 10.1.2 Shannon エントロピー
• 10.1.3 結合エントロピーと条件付きエントロピー
• 10.1.4 相互情報量
• 10.1.5 相対エントロピー
• 10.1.6 エントロピーの性質

10.2 情報源符号化

• 10.2.1 符号の定義と性質
• 10.2.2 Kraft の不等式
• 10.2.3 Shannon の符号化定理
• 10.2.4 最適符号
• 10.2.5 算術符号
• 10.2.6 ユニバーサル符号

10.3 通信路符号化

• 10.3.1 通信路モデル
• 10.3.2 通信路容量
• 10.3.3 Shannon の通信路符号化定理
• 10.3.4 誤り指数

10.4 誤り訂正符号

• 10.4.1 線形符号
• 10.4.2 符号の限界
• 10.4.3 具体的な符号
• 10.4.4 復号アルゴリズム
• 10.4.5 連接符号とターボ符号

10.5 連続情報理論

• 10.5.1 微分エントロピー
• 10.5.2 ガウス分布の特性
• 10.5.3 ガウス通信路
• 10.5.4 帯域制限通信路

10.6 情報理論の応用

• 10.6.1 データ圧縮への応用
• 10.6.2 暗号理論との関係
• 10.6.3 機械学習における情報理論
• 10.6.4 生物情報学での応用

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

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

11.1 暗号理論の基礎概念

• 11.1.1 暗号システムの定義
• 11.1.2 安全性の定義
• 11.1.3 一方向関数
• 11.1.4 疑似乱数生成器

11.2 対称鍵暗号

• 11.2.1 ストリーム暗号
• 11.2.2 ブロック暗号
• 11.2.3 暗号利用モード
• 11.2.4 認証付き暗号

11.3 公開鍵暗号

• 11.3.1 RSA 暗号
• 11.3.2 離散対数問題
• 11.3.3 ElGamal 暗号
• 11.3.4 楕円曲線暗号

11.4 デジタル署名

• 11.4.1 署名スキームの定義
• 11.4.2 安全性定義
• 11.4.3 RSA 署名
• 11.4.4 DSA と ECDSA
• 11.4.5 Schnorr 署名

11.5 ハッシュ関数

• 11.5.1 暗号学的ハッシュ関数の性質
• 11.5.2 Merkle-Damgård 構成
• 11.5.3 具体的なハッシュ関数
• 11.5.4 ハッシュ関数の応用

11.6 ゼロ知識証明

• 11.6.1 対話型証明系
• 11.6.2 ゼロ知識性
• 11.6.3 具体例：グラフ同型
• 11.6.4 Σプロトコル
• 11.6.5 非対話型ゼロ知識（NIZK）
• 11.6.6 zk-SNARK

11.7 高度な暗号プリミティブ

• 11.7.1 準同型暗号
• 11.7.2 秘密分散
• 11.7.3 マルチパーティ計算

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

第12章 並行計算の理論

12.1 並行計算モデル

• 12.1.1 並行性の基本概念
• 12.1.2 共有メモリモデル
• 12.1.3 メッセージパッシングモデル

12.2 プロセス代数

• 12.2.1 CCS（Calculus of Communicating Systems）
• 12.2.2 操作的意味論
• 12.2.3 双模倣等価性
• 12.2.4 その他のプロセス代数

12.3 Petri ネット

• 12.3.1 基本定義
• 12.3.2 実行意味論
• 12.3.3 性質解析
• 12.3.4 解析手法

12.4 時相論理による並行システムの検証

• 12.4.1 並行システムの性質
• 12.4.2 CTL による検証
• 12.4.3 モデル検査アルゴリズム

12.5 分散アルゴリズム

• 12.5.1 分散システムのモデル
• 12.5.2 基本的な分散アルゴリズム
• 12.5.3 合意問題
• 12.5.4 分散スナップショット

12.6 並行データ構造

• 12.6.1 ロックベースの手法
• 12.6.2 ロックフリーアルゴリズム
• 12.6.3 線形化可能性

12.7 プロセス計算の高度な話題

• 12.7.1 π計算
• 12.7.2 Ambient 計算
• 12.7.3 確率的プロセス代数

12.8 実時間システム

• 12.8.1 時間オートマトン
• 12.8.2 時間付き時相論理

章末問題

• 基礎問題
• 発展問題
• 探究課題
• 実装課題

付録A 数学記法一覧

集合論記法

• ∈: 要素
• ⊆: 部分集合
• ∪: 和集合
• ∩: 積集合
• ∅: 空集合
• ℕ: 自然数
• ℤ: 整数
• ℚ: 有理数
• ℝ: 実数

論理記号

• ¬: 否定
• ∧: 論理積
• ∨: 論理和
• →: 含意（論理式内）
• ⇒: 含意（メタレベル）
• ↔: 同値（論理式内）
• ⟺: 同値（メタレベル）
• ∀: 全称量化
• ∃: 存在量化

漸近記法

• O(): 上界
• Ω(): 下界
• Θ(): タイト境界
• o(): 真に小さい
• ω(): 真に大きい

付録B 重要定理一覧

1. Cantor対角線論法: 実数は非可算
2. Church-Turingの提唱: 計算可能性の定義
3. 停止問題の決定不能性
4. Cook-Levinの定理: SATのNP完全性
5. マスター定理: 分割統治の解析
6. 最大フロー最小カット定理
7. Gődelの不完全性定理
8. Shannon符号化定理
9. 4色定理
10. FLP不可能性定理: 非同期分散合意

参考文献

基礎理論

• Sipser, M. “Introduction to the Theory of Computation”
• Hopcroft, J., Motwani, R., Ullman, J. “Introduction to Automata Theory, Languages, and Computation”
• Arora, S., Barak, B. “Computational Complexity: A Modern Approach”

アルゴリズム

• Cormen, T. et al. “Introduction to Algorithms”
• Kleinberg, J., Tardos, E. “Algorithm Design”

論理学と形式手法

• Huth, M., Ryan, M. “Logic in Computer Science”
• Baier, C., Katoen, J. “Principles of Model Checking”

情報理論と暗号

• Cover, T., Thomas, J. “Elements of Information Theory”
• Katz, J., Lindell, Y. “Introduction to Modern Cryptography”

並行計算

• Lynch, N. “Distributed Algorithms”
• Milner, R. “Communicating and Mobile Systems: The π-Calculus”