計算理論是計算機科學的理論基礎。
本書介紹了計算理論最核心、最基本的內容，包括形式語言與自動機、可計算性和計算複雜性三大部分。全書共分7章，分別為：集合、關係和語言；有窮自動機；上下文無關語言；Turing機；不可判定性；計算複雜性；NP完全性。本書突出了算法，從而使計算機專業的學生更易於本書適合作為計算機專業及數學專業本科生或研究生的教材，也可供從事計算機科學的教學與研究人員參考。
基本介紹
- 書名：計算理論基礎
- ISBN：9787302132882
- 定價：29元
- 裝幀：平裝
基本信息,書籍目錄,
基本信息
ISBN：9787302132882
定價：29元
印次：1-2
裝幀：平裝
印刷日期：2006-11-28
書籍目錄
1.1 引言1
1.2 集合1
1.3 關係與圖3
1.4 函式與計數7
1.5 證明技巧14
1.6 本章總結與習題22
本章習題22
第2章 正則語言26
2.1 引言26
2.2 語言基礎26
本節習題29
2.3 正則表達式31
本節習題32
2.4 正則語法34
本節習題37
2.5 確定性有限自動機（DFA) 38
本節習題46
2.6 非確定性有限自動機（NFA) 47
本節習題52
2.7 本章總結與附加思考題54
附加思考題54
第3章 等價58
3.1 引言58
3.2 NFA到DFA58
本節習題63
3.3 有限自動機與正則語法64
本節習題65
3.4 正則表達式到NFA66
本節習題68
3.5 NFA到正則表達式69
本節習題73
3.6 本章總結與附加思考題75
附加思考題76
第4章 正則語言的結構78
4.1 引言78
4.2 閉包性質78
本節習題81
4.3 非正則語言82
本節習題86
4.4 米歇爾-尼羅德定理88
本節習題92
4.5 狀態最小化92
本節習題98
4.6 本章總結與附加思考題99
附加思考題100
第5章 上下文無關語言105
5.1 引言105
5.2 上下文無關語法105
本節習題108
5.3 分析樹110
本節習題114
5.4 歧義114
本節習題117
5.5 消除/刪除不良生成式118
本節習題121
5.6 範式122
本節習題128
5.7 本章總結與附加思考題129
附加思考題129
第6章 上下文無關語言的結構132
6.1 引言132
6.2 疊加自動機132
本節習題138
6.3 上下文無關語法與疊加自動機140
本節習題144
6.4 泵作用引理145
本節習題150
6.5 上下文無關語言的閉包性質151
本節習題153
6.6 確定型疊加自動機154
本節習題158
6.7 本章總結與附加思考題159
附加思考題159
第7章 可計算枚舉語言167
7.1 引言167
7.2 非限制性語法167
本節習題169
7.3 圖靈機170
本節習題174
7.4 接受與拒絕174
本節習題179
7.5 使用舊自動機180
本節習題187
7.6 多帶圖靈機188
本節習題191
7.7 非確定性圖靈機和語法192
本節習題197
7.8 本章總結與附加思考題198
附加思考題198
第8章 非可計算枚舉語言201
8.1 引言201
8.2 作為計算器的圖靈機201
本節習題204
8.3 作為語言判定的圖靈機205
本節習題209
8.4 存在多少圖靈機210
本節習題213
8.5 接受問題213
本節習題217
8.6 喬姆斯基層次結構217
本節習題219
8.7 總結和附加問題222
本節習題222
第9章 算法可解性229
9.1 引言229
9.2 問題歸約230
本節習題232
9.3 賴斯定理234
本節習題236
9.4 關於有限自動機238
本節習題239
9.5 關於疊加自動機240
本節習題244
9.6 關於波斯特對應問題245
本節習題249
9.7 關於邏輯理論250
本節習題255
9.8 其他有趣的問題255
本節習題257
9.9 總結和附加問題258
本節習題259
第10章 計算複雜性267
10.1 引言267
10.2 函式增長率268
本節習題271
10.3 複雜性類別272
本節習題275
10.4 空間複雜性276
本節習題278
10.5 時間複雜性279
本節習題283
10.6 NP類284
本節習題286
10.7 NP完整性287
本節習題291
10.8 某些NP完整問題291
本節習題298
10.9 解決NP完整問題300
本節習題303
10.10 本章總結與附加思考題303
附加思考題304
部分習題答案與提示313
參考文獻334
