可計算性與計算復雜性導引（第3版）簡(jiǎn)介，目錄書(shū)摘
2019-11-26 15:07
來(lái)源：京東
作者：京東
可計算性與計算復雜性導引（第3版）
暫無(wú)報價(jià)
80+評論
98%好評
編輯推薦:
內容簡(jiǎn)介: 《可計算性與計算復雜性導引（第3版）》是學(xué)習計算理論的教材和參考書(shū)，內容包括三部分：可計算性、形式語(yǔ)言與自動(dòng)機、計算復雜性．主要介紹幾種計算模型及它們的等價(jià)性，函數、謂詞和語(yǔ)言的可計算性等基本概念，形式語(yǔ)言及其對應的自動(dòng)機模型，時(shí)間和空間復雜性，np完全性等．
《可計算性與計算復雜性導引（第3版）》可作為計算機專(zhuān)業(yè)本科生和研究生的教材，也可作為從事計算機科學(xué)技術(shù)的研究和開(kāi)發(fā)人員的參考書(shū)，還可作為對計算理論感興趣的讀者的入門(mén)讀物．
《可計算性與計算復雜性導引（第3版）》可作為計算機專(zhuān)業(yè)本科生和研究生的教材，也可作為從事計算機科學(xué)技術(shù)的研究和開(kāi)發(fā)人員的參考書(shū)，還可作為對計算理論感興趣的讀者的入門(mén)讀物．
作者簡(jiǎn)介:
目錄:第一章 程序設計語(yǔ)言 和可計算函數
1.1 預備知識
1.2 church-turing論題
1.3 程序設計語(yǔ)言
1.4 可計算函數
1.5 宏指令
習題
第二章 原始遞歸函數
2.1 原始遞歸函數
2.2 原始遞歸謂詞
2.3 迭代運算、有界量詞和極小化
2.4 配對函數和godel數
2.5 原始遞歸運算
2.6 ackermann函數
2.7 字函數的可計算性
習題
第三章 通用程序
3.1 程序的代碼
3.2 停機問(wèn)題
3.3 通用程序
3.4 遞歸可枚舉集
習題
第四章 turing機
4.1 turing機的基本模型
4.2 turing機的各種形式
4.3 turing機與可計算性
4.4 turing機接受的語(yǔ)言
4.5 非確定型turing機
習題
第五章 過(guò)程與文法
5.1 半thue過(guò)程
5.2 用半thue過(guò)程模擬turing機
5.3 文法
5.4 再論遞歸可枚舉集
5.5 部分遞歸函數
5.6 再論church-turing論題
習題
第六章 不可判定的問(wèn)題
6.1 判定問(wèn)題
6.2 turing機的停機問(wèn)題
6.3 字問(wèn)題和post對應問(wèn)題
6.4 有關(guān)文法的不可判定問(wèn)題
6.5 一階邏輯中的判定問(wèn)題
習題
第七章 正則語(yǔ)言
7.1 chomsky譜系
7.2 有窮自動(dòng)機
7.3 有窮自動(dòng)機與正則文法的等價(jià)性
7.4 正則表達式
7.5 非正則語(yǔ)言
習題
第八章 上下文無(wú)關(guān)語(yǔ)言
8.1 上下文無(wú)關(guān)文法
8.2 chomsky范式
8.3 bar-hillel泵引理
8.4 下推自動(dòng)機
8.5 上下文無(wú)關(guān)文法與下推自動(dòng)機的等價(jià)性
8.6 確定型下推自動(dòng)機
8.7 上下文有關(guān)文法
習題
第九章 時(shí)間復雜性與空間復雜性
9.1 turing機的運行時(shí)間和工作空間
9.2 計算復雜性類(lèi)
9.3 復雜性類(lèi)的真包含關(guān)系
習題
第十章 np完全性
10.1 p與np
10.2 多項式時(shí)間變換和np完全性
10.3 cook定理
10.4 若干np完全問(wèn)題
10.5 conp
習題
第十一章 np類(lèi)的外面
11.1 pspace完全問(wèn)題
11.2 一個(gè)難解問(wèn)題
習題
第十二章 p類(lèi)的里面
12.1 若干例子
12.2 對數空間變換
12.3 nl類(lèi)
12.4 p完全問(wèn)題
習題
第十三章 隨機算法與隨機復雜性類(lèi)
13.1 隨機算法
13.2 隨機復雜性類(lèi)
習題
習題解答
附錄
附錄a 記號
附錄b 中英文名詞索引
參考文獻
1.1 預備知識
1.2 church-turing論題
1.3 程序設計語(yǔ)言
1.4 可計算函數
1.5 宏指令
習題
第二章 原始遞歸函數
2.1 原始遞歸函數
2.2 原始遞歸謂詞
2.3 迭代運算、有界量詞和極小化
2.4 配對函數和godel數
2.5 原始遞歸運算
2.6 ackermann函數
2.7 字函數的可計算性
習題
第三章 通用程序
3.1 程序的代碼
3.2 停機問(wèn)題
3.3 通用程序
3.4 遞歸可枚舉集
習題
第四章 turing機
4.1 turing機的基本模型
4.2 turing機的各種形式
4.3 turing機與可計算性
4.4 turing機接受的語(yǔ)言
4.5 非確定型turing機
習題
第五章 過(guò)程與文法
5.1 半thue過(guò)程
5.2 用半thue過(guò)程模擬turing機
5.3 文法
5.4 再論遞歸可枚舉集
5.5 部分遞歸函數
5.6 再論church-turing論題
習題
第六章 不可判定的問(wèn)題
6.1 判定問(wèn)題
6.2 turing機的停機問(wèn)題
6.3 字問(wèn)題和post對應問(wèn)題
6.4 有關(guān)文法的不可判定問(wèn)題
6.5 一階邏輯中的判定問(wèn)題
習題
第七章 正則語(yǔ)言
7.1 chomsky譜系
7.2 有窮自動(dòng)機
7.3 有窮自動(dòng)機與正則文法的等價(jià)性
7.4 正則表達式
7.5 非正則語(yǔ)言
習題
第八章 上下文無(wú)關(guān)語(yǔ)言
8.1 上下文無(wú)關(guān)文法
8.2 chomsky范式
8.3 bar-hillel泵引理
8.4 下推自動(dòng)機
8.5 上下文無(wú)關(guān)文法與下推自動(dòng)機的等價(jià)性
8.6 確定型下推自動(dòng)機
8.7 上下文有關(guān)文法
習題
第九章 時(shí)間復雜性與空間復雜性
9.1 turing機的運行時(shí)間和工作空間
9.2 計算復雜性類(lèi)
9.3 復雜性類(lèi)的真包含關(guān)系
習題
第十章 np完全性
10.1 p與np
10.2 多項式時(shí)間變換和np完全性
10.3 cook定理
10.4 若干np完全問(wèn)題
10.5 conp
習題
第十一章 np類(lèi)的外面
11.1 pspace完全問(wèn)題
11.2 一個(gè)難解問(wèn)題
習題
第十二章 p類(lèi)的里面
12.1 若干例子
12.2 對數空間變換
12.3 nl類(lèi)
12.4 p完全問(wèn)題
習題
第十三章 隨機算法與隨機復雜性類(lèi)
13.1 隨機算法
13.2 隨機復雜性類(lèi)
習題
習題解答
附錄
附錄a 記號
附錄b 中英文名詞索引
參考文獻
京公網(wǎng)安備 11000002000088號
