本書由計算理論領(lǐng)域的知名權(quán)威MichaelSipser所撰寫。他以獨特的視角，系統(tǒng)地介紹了計算理論的三個主要內(nèi)容：自動機(jī)與語言、可計算性理論和計算復(fù)雜性理論。作者以清新的筆觸、生動的語言給出了寬泛的數(shù)學(xué)原理，而沒有拘泥于某些低層次的細(xì)節(jié)。在證明之前，均有“證明思路”，幫助讀者理解數(shù)學(xué)形式下蘊(yùn)涵的概念。本書可作為計算機(jī)專業(yè)高年級本科生和研究生的教材，也可作為教師和研究人員的參考書。
Introduction to the Theory of Computation,3e
出版者的話
譯者序
第3版前言
第2版前言
第1版前言
第0章緒論
0 1自動機(jī)、可計算性與復(fù)雜性
0 1 1計算復(fù)雜性理論
0 1 2可計算性理論
0 1 3自動機(jī)理論
0 2數(shù)學(xué)概念和術(shù)語
0 2 1集合
0 2 2序列和多元組
0 2 3函數(shù)和關(guān)系
0 2 4圖
0 2 5字符串和語言
0 2 6布爾邏輯
0 2 7數(shù)學(xué)名詞匯總
0 3定義、定理和證明
0 4證明的類型
0 4 1構(gòu)造性證明
0 4 2反證法
0 4 3歸納法
練習(xí)
問題
習(xí)題選解
第一部分自動機(jī)與語言
第1章正則語言
1 1有窮自動機(jī)
1 1 1有窮自動機(jī)的形式化定義
1 1 2有窮自動機(jī)舉例
1 1 3計算的形式化定義
1 1 4設(shè)計有窮自動機(jī)
1 1 5正則運算
1 2非確定性
1 2 1非確定型有窮自動機(jī)的形式化定義
1 2 2NFA與DFA的等價性
1 2 3在正則運算下的封閉性
1 3正則表達(dá)式
1 3 1正則表達(dá)式的形式化定義
1 3 2與有窮自動機(jī)的等價性
1 4非正則語言
練習(xí)
問題
習(xí)題選解
第2章上下文無關(guān)文法
2 1上下文無關(guān)文法概述
2 1 1上下文無關(guān)文法的形式化定義
2 1 2上下文無關(guān)文法舉例
2 1 3設(shè)計上下文無關(guān)文法
2 1 4歧義性
2 1 5喬姆斯基范式
2 2下推自動機(jī)
2 2 1下推自動機(jī)的形式化定義
2 2 2下推自動機(jī)舉例
2 2 3與上下文無關(guān)文法的等價性
2 3非上下文無關(guān)語言
2 4確定型上下文無關(guān)語言
2 4 1DCFL的性質(zhì)
2 4 2確定型上下文無關(guān)文法
2 4 3DPDA和DCFG的關(guān)系
2 4 4語法分析和LR(k)文法
練習(xí)
問題
習(xí)題選解
第二部分可計算性理論
第3章丘奇圖靈論題
3 1圖靈機(jī)
3 1 1圖靈機(jī)的形式化定義
3 1 2圖靈機(jī)的例子
3 2圖靈機(jī)的變形
3 2 1多帶圖靈機(jī)
3 2 2非確定型圖靈機(jī)
3 2 3枚舉器
3 2 4與其他模型的等價性
3 3算法的定義
3 3 1希爾伯特問題
3 3 2描述圖靈機(jī)的術(shù)語
練習(xí)
問題
習(xí)題選解
第4章可判定性
4 1可判定語言
4 1 1與正則語言相關(guān)的可判定性問題
4 1 2與上下文無關(guān)語言相關(guān)的可判定性問題
4 2不可判定性
4 2 1對角化方法
4 2 2不可判定語言
4 2 3一個圖靈不可識別語言
練習(xí)
問題
習(xí)題選解
第5章可歸約性
5 1語言理論中的不可判定問題
5 2一個簡單的不可判定問題
5 3映射可歸約性
5 3 1可計算函數(shù)
5 3 2映射可歸約性的形式化定義
練習(xí)
問題
習(xí)題選解
第6章可計算性理論的高級專題
6 1遞歸定理
6 1 1自引用
6 1 2遞歸定理的術(shù)語
6 1 3應(yīng)用
6 2邏輯理論的可判定性
6 2 1一個可判定的理論
6 2 2一個不可判定的理論
6 3圖靈可歸約性
6 4信息的定義
6 4 1極小長度的描述
6 4 2定義的優(yōu)化
6 4 3不可壓縮的串和隨機(jī)性
練習(xí)
問題
習(xí)題選解
第三部分復(fù)雜性理論
第7章時間復(fù)雜性
7 1度量復(fù)雜性
7 1 1大O和小o記法
7 1 2分析算法
7 1 3模型間的復(fù)雜性關(guān)系
7 2P類
7 2 1多項式時間
7 2 2P中的問題舉例
7 3NP類
7 3 1NP中的問題舉例
7 3 2P與NP問題
7 4NP完全性
7 4 1多項式時間可歸約性
7 4 2NP完全性的定義
7 4 3庫克列文定理
7 5幾個NP完全問題
7 5 1頂點覆蓋問題
7 5 2哈密頓路徑問題
7 5 3子集和問題
練習(xí)
問題
習(xí)題選解
第8章空間復(fù)雜性
8 1薩維奇定理
8 2PSPACE類
8 3PSPACE完全性
8 3 1TQBF問題
8 3 2博弈的必勝策略
8 3 3廣義地理學(xué)
8 4L類和NL類
8 5NL完全性
8 6NL等于coNL
練習(xí)
問題
習(xí)題選解
第9章難解性
9 1層次定理
9 2相對化
9 3電路復(fù)雜性
練習(xí)
問題
習(xí)題選解
第10章復(fù)雜性理論高級專題
10 1近似算法
10 2概率算法
10 2 1BPP類
10 2 2素數(shù)性
10 2 3只讀一次的分支程序
10 3交錯式
10 3 1交錯式時間與交錯式空間
10 3 2多項式時間層次
10 4交互式證明系統(tǒng)
10 4 1圖的非同構(gòu)
10 4 2模型的定義
10 4 3IP=PSPACE
10 5并行計算
10 5 1一致布爾電路
10 5 2NC類
10 5 3P完全性
10 6密碼學(xué)
10 6 1密鑰
10 6 2公鑰密碼系統(tǒng)
10 6 3單向函數(shù)
10 6 4天窗函數(shù)
練習(xí)
問題
習(xí)題選解
參考文獻(xiàn)
索引
書單推薦
