計算復雜性

定　價：￥119.00

作　者：	（美）克里斯特斯 H .帕帕季米特里烏
出版社：	機械工業(yè)出版社
叢編項：
標　簽：	計算機/網(wǎng)絡計算機理論

購買這本書可以去

ISBN：	9787111517351	出版時間：	2015-12-01	包裝：	平裝
開本：	16開	頁數(shù)：	329	字數(shù)：

內容簡介

　　計算機復雜理論的研究是計算機科學*重要的研究領域之一，而Chistos.H.Papadimitriou是該領域*著名的專家之一。本書是一本全面闡述計算機復雜性理論及其近年來進展的教科書，主要包含算法圖靈機、可計算性等有關計算復雜理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等復雜性理論的基礎知識；P與NP、NP完全等各復雜性類的概念及其之間的關系等復雜性理論的核心內容；隨機算法、近似算法、并行算法及其復雜性理論；以及NP之外如多項式空間等復雜性類的介紹。

作者簡介

暫缺《計算復雜性》作者簡介

圖書目錄

目錄
Computational Complexity
出版者的話
譯者序
前言
第一部分算法
第1章問題與算法
11圖的可達性問題
12最大流問題
13旅行商問題
14注解、參考文獻和問題
第2章圖靈機
21圖靈機概述
22視為算法的圖靈機
23多帶圖靈機
24線性加速
25空間界
26隨機存取機
27非確定性機
28注解、參考文獻和問題
第3章不可判定性
31通用圖靈機
32停機問題
33更多不可判定性問題
34注解、參考文獻和問題
第二部分邏輯學
第4章布爾邏輯
41布爾表達式
42可滿足性與永真性
43布爾函數(shù)與電路
44注解、參考文獻和問題
第5章一階邏輯
51一階邏輯的語法
52模型
53永真的表達式
54公理和證明
55完備性定理
56完備性定理的推論
57二階邏輯
58注解、參考文獻和問題
第6章邏輯中的不可判定性
61數(shù)論公理
62作為一個數(shù)論概念的計算
63不可判定性與不完備性
64注解、參考文獻和問題
第三部分P和NP
第7章復雜性類之間的關系
71復雜性類
72譜系定理
73可達性方法
74注解、參考文獻和問題
第8章歸約和完備性
81歸約
82完全性
83邏輯特征
84注解、參考文獻和問題
第9章NP完全問題
91NP中的問題
92可滿足性問題的不同版本
93圖論問題
94集合和數(shù)字
95注解、參考文獻和問題
第10章coNP和函數(shù)問題
101NP和coNP
102素性
103函數(shù)問題
104注解、參考文獻和問題
第11章隨機計算
111隨機算法
112隨機復雜性類
113隨機源
114電路復雜性
115注解、參考文獻和問題
第12章密碼學
121單向函數(shù)
122協(xié)議
123注解、參考文獻和問題
第13章可近似性
131近似算法
132近似和復雜性
133不可近似性
134注解、參考文獻和問題
第14章關于P和NP
141NP的地圖
142同構和稠密性
143諭示
144單調電路
145注解、參考文獻和問題
第四部分P內部的計算復雜性類
第15章并行計算
151并行算法
152計算的并行模型
153NC類
154RNC算法
155注解、參考文獻和問題
第16章對數(shù)空間
161L=?NL問題
162交錯
163無向圖的可達性
164注解、參考文獻和問題
第五部分NP之外的計算復雜性類
第17章多項式譜系
171優(yōu)化問題
172多項式譜系
173注解、參考文獻和問題
第18章有關計數(shù)的計算
181積和式
182P類
183注解、參考文獻和問題
第19章多項式空間
191交錯和博弈
192對抗自然的博弈和交互協(xié)議
193更多的PSPACE完全問題
194注解、參考文獻和問題
第20章未來的展望
201指數(shù)時間復雜性類
202注解、參考文獻和問題
索引