《世界著名計算機教材精選:計算理論基礎》討論了計算機科學中的純粹、引人注目並且普遍存在的基本內容，介紹構成基本計算範例的基本概念、模型、技巧、結果，闡述當今計算機科學家用於建模、討論和預測算法與計算的思想概念與數學知識。全書共分10章，內容包括數學基礎、正則語言、上下文無關語言、可計算枚舉語言、非可計算枚舉語言、算法可解性、計算複雜性等內容。每章都給出了大量習題，並且在附錄提供了部分習題的答案與提示。
基本介紹
- 書名：世界著名計算機教材精選:計算理論基礎
- 作者：辛格 (Arindama Singh)
- 類型：計算機與網際網路
- 出版日期：2013年1月1日
- 語種：簡體中文
- ISBN：9787302305422
- 外文名：Elements of Computation Theory
- 譯者：曹愛文
- 出版社：清華大學出版社
- 頁數：339頁
- 開本：16
基本介紹,內容簡介,作者簡介,圖書目錄,
基本介紹
內容簡介
《計算理論基礎(世界著名計算機教材精選)》由辛格編著，本書討論計算機科學中的純粹、引人注目並且普遍存在的基本內容，介紹構成基本計算範例的基本概念、模型、技巧、結果，闡述當今計算機科學家用於建模、討論和預測算法與計算的思想概念與數學。本書中所選話題都是相當長時間內表現出異常持久性，並在當前套用中經常出現的，本書可以作為計算機科學、計算機工程和數學等專業的本科核心課程教材，適用於計算理論、自動化理論、形式語言和計算模型等方面的課程。
作者簡介
作者：（美國）辛格（Arindama Singh） 譯者：曹愛文 葉鵬 李少帥
圖書目錄
第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.2NFA到DFA
本節習題
3.3有限自動機與正則語法
本節習題
3.4正則表達式到NFA
本節習題
3.5NFA到正則表達式
本節習題
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.6NP類
本節習題
10.7NP完整性
本節習題
10.8某些NP完整問題
本節習題
10.9解決NP完整問題
本節習題
10.10本章總結與附加思考題
附加思考題
部分習題答案與提示
參考文獻
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.2NFA到DFA
本節習題
3.3有限自動機與正則語法
本節習題
3.4正則表達式到NFA
本節習題
3.5NFA到正則表達式
本節習題
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.6NP類
本節習題
10.7NP完整性
本節習題
10.8某些NP完整問題
本節習題
10.9解決NP完整問題
本節習題
10.10本章總結與附加思考題
附加思考題
部分習題答案與提示
參考文獻
