計(jì)算理論導(dǎo)引

目錄
譯者序
前言
第1章   導(dǎo)引
1.1   自動(dòng)機(jī). 可計(jì)算性與復(fù)雜性
1.1.1   計(jì)算復(fù)雜性理論
1.1.2   可計(jì)算性理論
1.1.3    自動(dòng)機(jī)理論
1.2   數(shù)學(xué)概念和術(shù)語(yǔ)
1.2.1   集合
1.2.2   序列和多元組
1.2.3   函數(shù)和關(guān)系
1.2.4   圖
1.2.5   字符串和語(yǔ)言
1.2.6   布爾邏輯
1.2.7    數(shù)學(xué)名詞匯總 
1.3    定義. 定理和證明
1.4    證明的類(lèi)型
1.4.1    構(gòu)造性證明
1.4.2   反證法
1.4.3   歸納法
練習(xí)
問(wèn)題
第一部分    自動(dòng)機(jī)與語(yǔ)言
第2 章   正則語(yǔ)言
2.1   有窮自動(dòng)機(jī)
2.1.1    有窮自動(dòng)機(jī)的形式定義
2.1.2    有窮自動(dòng)機(jī)舉例
2.1.3    計(jì)算的形式定義
2.1.4   設(shè)計(jì)有窮自動(dòng)機(jī)
2.1.5   正則運(yùn)算
2.2   非確定性
2.2.1   非確定型有窮自動(dòng)機(jī)的形式定義
2.2.2    NFA與DFA的等價(jià)性
2.2.3    在正則運(yùn)算下的封閉性 
2.3    正則表達(dá)式
2.3.1    正則表達(dá)式的形式定義
2.3.2    與有窮自動(dòng)機(jī)的等價(jià)性
2.4    非正則語(yǔ)言
練習(xí)
問(wèn)題
第3章   上下文無(wú)關(guān)語(yǔ)言
3.1    上下文無(wú)關(guān)文法
3.1.1    上下文無(wú)關(guān)文法的形式定義
3.1.2    上下文無(wú)關(guān)文法舉例
3.1.3    設(shè)計(jì)上下文無(wú)關(guān)文法
3.1.4     歧義性
3.1.5     喬姆斯基范式
3.2    下推自動(dòng)機(jī)
3.2.1    下推自動(dòng)機(jī)的形式定義
3.2.2    下推自動(dòng)機(jī)舉例
3.2.3     與上下文無(wú)關(guān)文法的等價(jià)性
3.3     非上下文無(wú)關(guān)語(yǔ)言
練習(xí)
問(wèn)題
第二部分   可計(jì)算性理論
第4章    丘奇—圖靈論題
4.1   圖靈機(jī)
4.1.1    圖靈機(jī)的形式定義
4.1.2    圖靈機(jī)的例子
4.2    圖靈機(jī)的變形
4.2.1    多帶圖靈機(jī)
4.2.2     非確定型圖靈機(jī)
4.2.3     枚舉器
4.2.4    與其他模型的等價(jià)性
4.3     算法的定義
4.3.1    希爾伯特問(wèn)題
4.3.2    描述圖靈機(jī)的術(shù)語(yǔ)
練習(xí)
問(wèn)題
第5章   可判定性
5.1    可判定語(yǔ)言
5.1.1     與正則語(yǔ)言相關(guān)的可判定性問(wèn)題
5.1.2    與上下文無(wú)關(guān)語(yǔ)言相關(guān)的可判定問(wèn)題
5.2    停機(jī)問(wèn)題
5.2.1    對(duì)角化方法
5.2.2    停機(jī)問(wèn)題是不可判定的
5.2.3    一個(gè)圖靈不可識(shí)別語(yǔ)言
練習(xí)
問(wèn)題
第6章    可歸約性
6.1    語(yǔ)言理論中的不可判定問(wèn)題
6.2     一個(gè)簡(jiǎn)單的不可判定問(wèn)題
6.3     映射可歸約性
6.3.1   可計(jì)算函數(shù)
6.3.2    映射可歸約性的形式定義
練習(xí)
問(wèn)題
第7 章    可計(jì)算性理論的高級(jí)專(zhuān)題
7.1    遞歸定理 
7.1.1    自引用
7.1.2    應(yīng)用遞歸定理的術(shù)語(yǔ)
7.1.3   應(yīng)用
7.2    邏輯理論的可判定性
7.2.1    一個(gè)可判定的理論
7.2.2    一個(gè)不可判定的理論
7.3     圖靈可歸約性
7.4     信息的定義
7.4.1    極小長(zhǎng)度的描述
7.4.2    定義的優(yōu)化 
7.4.3    不可壓縮的串和隨機(jī)性
練習(xí)
問(wèn)題
第三部分   復(fù)雜性理論 
第8章   時(shí)間復(fù)雜性
8.1    度量復(fù)雜性
8.1.1    大O和小o記法
8.1.2    分析算法
8.1.3     模型間的復(fù)雜性關(guān)系
8.2   P 類(lèi)
8.2.1   多項(xiàng)式時(shí)間
8.2.2   P 中的問(wèn)題舉例
8.3    NP類(lèi) 
8.3.1   NP中的問(wèn)題舉例
8.3.2   P與NP問(wèn)題
8.4    NP完全性
8.4.1     多項(xiàng)式時(shí)間可歸約性
8.4.2     NP完全性的定義
8.4.3    庫(kù)克—列文定理
8.5    幾個(gè)NP完全問(wèn)題
8.5.1    頂點(diǎn)覆蓋問(wèn)題
8.5.2    哈密頓路徑問(wèn)題
8.5.3    子集和問(wèn)題
練習(xí)
問(wèn)題
第9章    空間復(fù)雜性
9.1    薩維奇定理
9.2    PSPACE類(lèi)
9.3   PSPACE完全性
9.3.1     問(wèn)題TQBF
9.3.2    博奕的必勝策略
9.3.3     廣義地理學(xué)
9.4     L類(lèi)和NL學(xué)
9.5    NL 完全性
9.6    NL等于coNL
練習(xí)
問(wèn)題
第10章    難解性
10.1   層次定理
10.2    相對(duì)化
10.3    電路復(fù)雜性 
練習(xí)
問(wèn)題
第 11章    復(fù)雜性理論中的高級(jí)專(zhuān)題
11.1    近似算法
11.2    概率算法
11.2.1    BPP類(lèi)
11.2.2    素?cái)?shù)性
11.2.3    只讀一次的分支程序
11.3    交錯(cuò)式
11.3.1    交錯(cuò)式時(shí)間與交錯(cuò)式空間
11.3.2    多項(xiàng)式時(shí)間層次
11.4     交互式證明系統(tǒng)
11.4.1    圖的非同構(gòu)
11.4.2    模型的定義
11.4.3    IP=PSPACE
11.5   并行計(jì)算
11.5.1    一致布爾電路
11.5.2    NC類(lèi)
11.5.3    P完全性
11.6     密碼學(xué)
11.6.1     密鑰
11.6.2    公鑰密碼系統(tǒng)
11.6.3    單向函數(shù)
11.6.4     天窗函數(shù) 
練習(xí)
問(wèn)題
參考文獻(xiàn)
索引