計算理論基礎（簡體書）

作者:(美)辛格 譯者:曹愛文、葉鵬、李少帥

《計算理論基礎(世界著名計算機教材精選)》由辛格編著，本書討論計算機科學中的純粹、引人注目并且普遍存在的基本內容，介紹構成基本計算范例的基本概念、模型、技巧、結果，闡述當今計算機科學家用于建模、討論和預測算法與計算的思想概念與數學。本書中所選話題都是相當長時間內表現出異常持久性，并在當前應用中經常出現的，本書可以作為計算機科學、計算機工程和數學等專業的本科核心課程教材，適用于計算理論、自動化理論、形式語言和計算模型等方面的課程。

第1章 數學基礎
1．1 引言
1．2 集合
1．3 關系與圖
1．4 函數與計數
1．5 證明技巧
1．6 本章總結與習題
本章習題
第2章 正則語言
2．1 引言
2．2 語言基礎
本節習題
2．3 正則表達式
本節習題
2．4 正則語法
本節習題
2．5 確定性有限自動機(DFA)
本節習題
2．6 非確定性有限自動機(NFA)
本節習題
2．7 本章總結與附加思考題
附加思考題
第3章 等價
3．1 引言
3．2 NFA到DFA
本節習題
3．3 有限自動機與正則語法
本節習題
3．4 正則表達式到NFA
本節習題
3．5 NFA到正則表達式
本節習題
3．6 本章總結與附加思考題
附加思考題
第4章 正則語言的結構
4．1 引言
4．2 閉包性質
本節習題
4．3 非正則語言
本節習題
4．4 米歇爾一尼羅德定理
本節習題
4．5 狀態最小化
本節習題
4．6 本章總結與附加思考題
附加思考題
第5章 上下文無關語言
5．1 引言
5．2 上下文無關語法
本節習題
5．3 分析樹
本節習題
5．4 歧義
本節習題
5．5 消除／刪除不良生成式
本節習題
5．6 范式
本節習題
5．7 本章總結與附加思考題
附加思考題
第6章 上下文無關語言的結構
6．1 引言
6．2 疊加自動機
本節習題
6．3 上下文無關語法與疊加自動機
本節習題
6．4 泵作用引理
本節習題
6．5 上下文無關語言的閉包性質
本節習題
6．6 確定型疊加自動機
本節習題
6．7 本章總結與附加思考題
附加思考題
第7章 可計算枚舉語言
7．1 引言
7．2 非限制性語法
本節習題
7．3 圖靈機
本節習題
7．4 接受與拒絕
本節習題
7．5 使用舊自動機
本節習題
7．6 多帶圖靈機
本節習題
7．7 非確定性圖靈機和語法
本節習題
7．8 本章總結與附加思考題
附加思考題
第8章 非可計算枚舉語言
8．1 引言
8．2 作為計算器的圖靈機
本節習題
8．3 作為語言判定的圖靈機
本節習題
8．4 存在多少圖靈機
本節習題
8．5 接受問題
本節習題
8．6 喬姆斯基層次結構
本節習題
8．7 總結和附加問題
本節習題
第9章 算法可解性
9．1 引言
9．2 問題歸約
本節習題
9．3 賴斯定理
本節習題
9．4 關于有限自動機
本節習題
9．5 關于疊加自動機
本節習題
9．6 關于波斯特對應問題
本節習題
9．7 關于邏輯理論
本節習題
9．8 其他有趣的問題
本節習題
9．9 總結和附加問題
本節習題
第10章 計算復雜性
10．1 引言
10．2 函數增長率
本節習題
10．3 復雜性類別
本節習題
10．4 空間復雜性
本節習題
10．5 時間復雜性
本節習題
10．6 NP類
本節習題
10．7 NP完整性
本節習題
10．8 某些NP完整問題
本節習題
10．9 解決NP完整問題
本節習題
10．10 本章總結與附加思考題
附加思考題
部分習題答案與提示
參考文獻