書記の読書記録#1106『計算理論とオートマトン言語理論[第2版]: コンピュータの原理を明かす』

丸岡 章『計算理論とオートマトン言語理論[第2版]: コンピュータの原理を明かす』のレビュー

計算理論とオートマトン言語理論[第2版]: コンピュータの原理を明かす (Information&Computing 122)

レビュー

Michael Sipser『計算理論の基礎』を手軽にした感じの計算理論の教科書で，一通り要点をおさえるのにちょうど良い分量。

もくじ

I　計算の理論
１　すべては計算から始まる
1.1　計算における壁
1.2　計算モデルの妥当性
1.3　本書を効率よく使うために

２　計算の理論のための概念や用語
2.1　集合
2.2　系列と言語
2.3　関数と問題
2.4　関数とグラフ
2.5　論理演算と論理式
2.6　命題と証明
2.7　アルゴリズムの記述
　　問題

II　オートマトンと言語
３　有限オートマトン
3.1　有限オートマトンによるモデル化
3.2　非決定性有限オートマトン
3.3　正規表現
3.4　正規言語の性質
　　問題

４　文脈自由言語
4.1　文脈自由文法
4.2　生成と受理
4.3　チョムスキーの標準形
4.4　文脈自由文法の言語生成能力の限界
4.5　文脈自由言語の所属問題
　　問題

５　プッシュダウンオートマトン
5.1　プッシュダウンオートマトン
5.2　プッシュダウンオートマトンと文脈自由文法の等価性
　　問題

III　計算可能性
６　チューリング機械
6.1　チューリング機械
6.2　チューリング機械の定義の拡張
6.3　非決定性チューリング機械
6.4　チャーチ・チューリングの提唱
　　問題

７　チューリング機械の計算の万能性とその限界
7.1　万能チューリング機械
7.2　停止問題の決定不能性
7.3　帰着
7.4　ポストの対応問題の決定不能性
　　問題

IV　計算の複雑さ
８　チューリング機械に基づいた計算量限定の計算
8.1　時間計算量
8.2　多項式時間で計算できる問題とできないと予想される問題
8.3　ΡとΝΡ
　　問題

９　論理回路に基づいた計算量限定の計算
9.1　論理関数と論理回路
9.2　離散関数と離散回路
9.3　決定性チューリング機械を模倣する論理回路
9.4　非決定性チューリング機械を模倣する論理回路
9.5　充足可能性問題
9.6　回路の充足可能性問題の式充足可能性問題への帰着
　　問題

10　ΝΡ完全
10.1　ΝΡ完全
10.2　いろいろなΝΡ完全問題
　　問題

解答
文献
おわりに
索引

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note