計算復雜性理論基礎(chǔ)

定　價：￥28.00

作　者：	呂克偉著
出版社：	國防工業(yè)出版社
叢編項：
標　簽：	計算機/網(wǎng)絡(luò) 計算機理論

購買這本書可以去

ISBN：	9787118085990	出版時間：	2013-06-01	包裝：	平裝
開本：	大32開	頁數(shù)：	206	字數(shù)：

內(nèi)容簡介

　　計算復雜性理論是用數(shù)學方法研究計算機解決各種算法問題難易程度的理論。《計算復雜性理論基礎(chǔ)》對這一理論的基礎(chǔ)知識做了全面介紹，力爭幫助讀者掌握該理論的思想方法，為進一步開展計算機科學的相關(guān)領(lǐng)域的學習和研究奠定了基礎(chǔ)。《計算復雜性理論基礎(chǔ)》首先介紹計算復雜性理論的概述、一些計算問題和邏輯，然后詳細介紹計算模型、PvsNP問題、歸約和NP完備性理論等；接著針對信息安全專業(yè)特點，詳細介紹隨機化算法、（非）一致電路；最后簡單介紹幾個較深入的課題：交互語言類、計數(shù)復雜類、概率可驗證語言類等。

作者簡介

暫缺《計算復雜性理論基礎(chǔ)》作者簡介

圖書目錄

第0章引言
習題
第1章一些計算問題
習題
第2章邏輯概述
2.1 布爾邏輯
2.2 一階邏輯
2.3 公理和證明
2.4 存在二階邏輯
第3章計算模型
3.1 字符串、編碼
3.2 算法時間的度量與模型
3.3 圖靈機基礎(chǔ)
3.4 多帶圖靈機、時間與空間
3.5 非確定圖靈機
3.6 通用圖靈機
3.7 遞歸語言與遞歸可枚舉語言
習題
第4章不可判定性
4.1 對角化方法與停機問題
4.2 遞歸可枚舉語言的形式表達
習題
第5章計算復雜類
5.1 復雜類
5.2 分離定理
5.3 可達性方法
習題
第6章歸約和完備性
6.1 歸約
6.2 完備性
6.3 邏輯刻畫
6.4 NP一關(guān)系
6.5 Oracle圖靈機
6.6 自歸約
習題
第7章 NP-完備問題、coNP與函數(shù)計算
7.1 NP-完備問題
7.1.1 可滿足問題的一些變形
7.1.2 圖論中的NP-完備問題
7.1.3 集合與數(shù)
7.2 偽多項式算法和強NP-完備問題
7.3 P與NP
7.4 函數(shù)問題
7.5 coNP
習題
第8章隨機化計算
8.1 隨機化算法
8.1.1 概率素性檢驗
8.1.2 符號行列式
8.1.3 隨機游動
8.2 概率計算
8.3 RP，coRP，ZPP和PP語言類
8.4 魯棒性
習題
第9章電路復雜度和非一致多項式時間類
9.1 電路復雜度
9.2 單調(diào)電路（Monotone Circuits）
9.3 非一致多項式時間類（P／Poly）
第10章幾類語言類介紹
10.1 多項式譜系（Dolynomial Hierarchy）
10.1.1 多項式譜系的定義（PH）
10.1.2 交錯圖靈機與多項式譜系（PH）
10.2 交互證明系統(tǒng)
10.2.1 證明
10.2.2 交互證明系統(tǒng)IP
10.2.3 公共擲幣系統(tǒng)和輪數(shù)
10.3 概率可驗證證明系統(tǒng)
10.3.1 PCP系統(tǒng)
10.3.2 PCP系統(tǒng)與交互證明系統(tǒng)
10.3.3 PCP語言
10.3.4 復雜度度量
10.3.5 PCP系統(tǒng)的相關(guān)結(jié)論
10.4 計數(shù)類
術(shù)語中英文對照表
索引
參考文獻