Ⅰ計算の理論 |
1 すべては計算から始まる |
1.1 計算における壁 2 |
計算の原理上の限界 4 |
計算の実際上の限界 6 |
計算モデルからの壁 7 |
1.2 計算モデルの妥当性 7 |
計算モデルの安定性 8 |
計算モデルの展開 9 |
1.3 本書を効率よく使うために 11 |
2 計算の理論のための概念や用語 |
2.1 集 合 13 |
2.2 系列と言語 15 |
2.3 関数と問題 16 |
2.4 関数とグラフ 18 |
2.5 論理演算と論理式 24 |
2.6 命題と証明 26 |
2.7 アルゴリズムの記述 31 |
問 題 34 |
Ⅱオートマトンと言語 |
3 有限オートマトン |
3.1 有限オートマトンによるモデル化 36 |
問題のモデル化 36 |
有限オートマトンの定義 39 |
3.2 非決定性有限オートマトン 46 |
非決定性有限オートマトンへの一般化 46 |
決定性宥限オートマトンと非決定性有限オートマトンの等価性 53 |
3.3 正規表現 62 |
正規表現の導入 62 |
正規表現と有限オートマトンの等価性 67 |
3.4 正規言語の性質 78 |
有限オートマトンの言語受理能力の限界 78 |
正規言語のクラスの閉包性 81 |
問 題 84 |
4 文脈自由言語 |
4.1 文脈自由文法 87 |
4.2 生成と受理 94 |
4.3 チョムスキーの標準形 98 |
4.4 文脈自由文法の言語生成能力の限界 102 |
4.5 文脈自由言語の所属問題 107 |
問 題 112 |
5 プッシュダウンオートマトン |
5.1 プッシュダウンオートマトン 114 |
5.2 プッシュダウンオートマトンと文脈自由文法の等価性 126 |
プッシュダウンオートマトンによる文脈自由文法の模倣 127 |
文脈自由文法によるプッシュダウンオートマトンの模倣 131 |
問 題 139 |
Ⅲ計算可能性 |
6 チューリング機械 |
6.1 チューリング機械 142 |
チューリング機械の例 147 |
6.2 チューリング機械の定義の拡張 157 |
片無限テープチューリング機械による |
両無限テープチューリング機械の模倣 157 |
1テープチューリング機械による多テープチューリング機械の模倣 160 |
6.3 非決定性チューリング機械 163 |
6.4 チャーチ・チューリングの提唱 167 |
問 題 169 |
7 チューリング機械の計算の万能性とその限界 |
7.1 万能チューリング機械 170 |
7.2 停止問題の決定不能性 176 |
7.3 帰着 180 |
7.4 ポストの対応問題の決定不能性 185 |
問 題 192 |
Ⅳ計算の複雑さ |
8 チューリング機械に基づいた計算量限定の計算 |
8.1 時間計算量 194 |
正しい括弧の系列を判定するのに要する計算時間 194 |
関数のオーダー表示 198 |
チューリング機械の時間計算量と問題の時間計算量 199 |
8.2 多項式時間で計算できる問題とできないと予想される問題 201 |
到達可能性問題 202 |
オイラー閉路問題 204 |
ハミルトン閉路問題 206 |
8.3 PとNP 207 |
問 題 212 |
9 論理回路に基づいた計算量限定の計算 |
9.1 論理関数と論理回路 213 |
9.2 離散関数と離散回路 219 |
9.3 決定性チューリング機械を模倣する論理回路 222 |
9.4 非決定性チューリング機械を模倣する論理回路 229 |
9.5 充足可能性問題 232 |
9.6 回路の充足可能性問題の式充足可能性問題への帰着 235 |
問 題 241 |
10 NP完全 |
IO.7 NP完全 242 |
10.2 いろいろなNP完全問題 243 |
充足可能性問題 244 |
ハミルトン閉路問題 245 |
部分和問題 251 |
問 題 254 |
解 答 256 |
文 献 271 |
おわりに 274 |
索 引 276 |