Introduction to the Theory of Computation,3e
出版者的話
譯者序
第3版前言
第2版前言
第1版前言
第0章緒論
0 1自動(dòng)機(jī)、可計(jì)算性與復(fù)雜性
0 1 1計(jì)算復(fù)雜性理論
0 1 2可計(jì)算性理論
0 1 3自動(dòng)機(jī)理論
0 2數(shù)學(xué)概念和術(shù)語(yǔ)
0 2 1集合
0 2 2序列和多元組
0 2 3函數(shù)和關(guān)系
0 2 4圖
0 2 5字符串和語(yǔ)言
0 2 6布爾邏輯
0 2 7數(shù)學(xué)名詞匯總
0 3定義、定理和證明
0 4證明的類(lèi)型
0 4 1構(gòu)造性證明
0 4 2反證法
0 4 3歸納法
練習(xí)
問(wèn)題
習(xí)題選解
第一部分自動(dòng)機(jī)與語(yǔ)言
第1章正則語(yǔ)言
1 1有窮自動(dòng)機(jī)
1 1 1有窮自動(dòng)機(jī)的形式化定義
1 1 2有窮自動(dòng)機(jī)舉例
1 1 3計(jì)算的形式化定義
1 1 4設(shè)計(jì)有窮自動(dòng)機(jī)
1 1 5正則運(yùn)算
1 2非確定性
1 2 1非確定型有窮自動(dòng)機(jī)的形式化定義
1 2 2NFA與DFA的等價(jià)性
1 2 3在正則運(yùn)算下的封閉性
1 3正則表達(dá)式
1 3 1正則表達(dá)式的形式化定義
1 3 2與有窮自動(dòng)機(jī)的等價(jià)性
1 4非正則語(yǔ)言
練習(xí)
問(wèn)題
習(xí)題選解
第2章上下文無(wú)關(guān)文法
2 1上下文無(wú)關(guān)文法概述
2 1 1上下文無(wú)關(guān)文法的形式化定義
2 1 2上下文無(wú)關(guān)文法舉例
2 1 3設(shè)計(jì)上下文無(wú)關(guān)文法
2 1 4歧義性
2 1 5喬姆斯基范式
2 2下推自動(dòng)機(jī)
2 2 1下推自動(dòng)機(jī)的形式化定義
2 2 2下推自動(dòng)機(jī)舉例
2 2 3與上下文無(wú)關(guān)文法的等價(jià)性
2 3非上下文無(wú)關(guān)語(yǔ)言
2 4確定型上下文無(wú)關(guān)語(yǔ)言
2 4 1DCFL的性質(zhì)
2 4 2確定型上下文無(wú)關(guān)文法
2 4 3DPDA和DCFG的關(guān)系
2 4 4語(yǔ)法分析和LR(k)文法
練習(xí)
問(wèn)題
習(xí)題選解
第二部分可計(jì)算性理論
第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與其他模型的等價(jià)性
3 3算法的定義
3 3 1希爾伯特問(wèn)題
3 3 2描述圖靈機(jī)的術(shù)語(yǔ)
練習(xí)
問(wèn)題
習(xí)題選解
第4章可判定性
4 1可判定語(yǔ)言
4 1 1與正則語(yǔ)言相關(guān)的可判定性問(wèn)題
4 1 2與上下文無(wú)關(guān)語(yǔ)言相關(guān)的可判定性問(wèn)題
4 2不可判定性
4 2 1對(duì)角化方法
4 2 2不可判定語(yǔ)言
4 2 3一個(gè)圖靈不可識(shí)別語(yǔ)言
練習(xí)
問(wèn)題
習(xí)題選解
第5章可歸約性
5 1語(yǔ)言理論中的不可判定問(wèn)題
5 2一個(gè)簡(jiǎn)單的不可判定問(wèn)題
5 3映射可歸約性
5 3 1可計(jì)算函數(shù)
5 3 2映射可歸約性的形式化定義
練習(xí)
問(wèn)題
習(xí)題選解
第6章可計(jì)算性理論的高級(jí)專(zhuān)題
6 1遞歸定理
6 1 1自引用
6 1 2遞歸定理的術(shù)語(yǔ)
6 1 3應(yīng)用
6 2邏輯理論的可判定性
6 2 1一個(gè)可判定的理論
6 2 2一個(gè)不可判定的理論
6 3圖靈可歸約性
6 4信息的定義
6 4 1極小長(zhǎng)度的描述
6 4 2定義的優(yōu)化
6 4 3不可壓縮的串和隨機(jī)性
練習(xí)
問(wèn)題
習(xí)題選解
第三部分復(fù)雜性理論
第7章時(shí)間復(fù)雜性
7 1度量復(fù)雜性
7 1 1大O和小o記法
7 1 2分析算法
7 1 3模型間的復(fù)雜性關(guān)系
7 2P類(lèi)
7 2 1多項(xiàng)式時(shí)間
7 2 2P中的問(wèn)題舉例
7 3NP類(lèi)
7 3 1NP中的問(wèn)題舉例
7 3 2P與NP問(wèn)題
7 4NP完全性
7 4 1多項(xiàng)式時(shí)間可歸約性
7 4 2NP完全性的定義
7 4 3庫(kù)克列文定理
7 5幾個(gè)NP完全問(wèn)題
7 5 1頂點(diǎn)覆蓋問(wèn)題
7 5 2哈密頓路徑問(wèn)題
7 5 3子集和問(wèn)題
練習(xí)
問(wèn)題
習(xí)題選解
第8章空間復(fù)雜性
8 1薩維奇定理
8 2PSPACE類(lèi)
8 3PSPACE完全性
8 3 1TQBF問(wèn)題
8 3 2博弈的必勝策略
8 3 3廣義地理學(xué)
8 4L類(lèi)和NL類(lèi)
8 5NL完全性
8 6NL等于coNL
練習(xí)
問(wèn)題
習(xí)題選解
第9章難解性
9 1層次定理
9 2相對(duì)化
9 3電路復(fù)雜性
練習(xí)
問(wèn)題
習(xí)題選解
第10章復(fù)雜性理論高級(jí)專(zhuān)題
10 1近似算法
10 2概率算法
10 2 1BPP類(lèi)
10 2 2素?cái)?shù)性
10 2 3只讀一次的分支程序
10 3交錯(cuò)式
10 3 1交錯(cuò)式時(shí)間與交錯(cuò)式空間
10 3 2多項(xiàng)式時(shí)間層次
10 4交互式證明系統(tǒng)
10 4 1圖的非同構(gòu)
10 4 2模型的定義
10 4 3IP=PSPACE
10 5并行計(jì)算
10 5 1一致布爾電路
10 5 2NC類(lèi)
10 5 3P完全性
10 6密碼學(xué)
10 6 1密鑰
10 6 2公鑰密碼系統(tǒng)
10 6 3單向函數(shù)
10 6 4天窗函數(shù)
練習(xí)
問(wèn)題
習(xí)題選解
參考文獻(xiàn)
索引