《計算複雜性》【定價】 ￥59.00
【作者】帕帕李米特里烏
【叢 書 名】 大學計算機教育國外著名教材系列
【出 版 社】 清華大學出版社
【書 號】 7302089558
【出版日期】 2004 年9月
【開 本】 16開
【頁 碼】 523
【版 次】1-1
【所屬分類】 計算機 > 計算機科學理論與基礎知識 > 基礎知識 > 綜合
教材 > 征訂教材 > 高等理工
計算機 > 計算機科學理論與基礎知識 > 計算理論 > 綜合
教材 > 計算機教材 > 本科/研究生 > 計算機專業 > 計算機基礎課程 > 算法與數學基礎
內容簡介
計算機複雜理論的研究是計算機科學最重要的研究領域之一，而Chistos.H.Papadimitriou是該領域最著名的專家之一。本書是一本全面闡述計算機複雜性理論及其近年來進展的教科書，主要包含算法圖靈機、可計算性等有關計算複雜理論的基本概念；布爾邏輯、一階邏輯、邏輯中的不可判定性等複雜性理論的基礎知識；P與NP、NP完全等各複雜性類的概念及其之間的關係等複雜性理論的核心內容；隨機算法、近似算法、並行算法及其複雜性理論；以及NP之外如多項式空間等複雜性類的介紹。
本書內容豐富，體系嚴謹，證明簡潔，敘述深入淺出，並配有大量的練習和文獻引用。本書不但適合和作為研究生或本科生高年級學生的教材，也適合從事算法和計算機複雜性研究的人員參考。
目錄介紹
目 錄：
I. ALGORITHMS.
1. Problems and Algorithms.
2. Turing Machines.
3. Undecidability.
II. LOGIC.
1. Boolean Logic.
2. First Order Logic.
3. Undecidability in Logic.
III. P AND NP.
1. Relations between Complexity Classes.
2. Reductions and Completeness.
3. NP-Complete Problems.
4. CONP and Function Problems.
5. Randomized Computation.
6. Cryptography.
7. Approximability.
8. On P vs. NP.
IV. INSIDE P.
1. Parallel Computation.
2. Logarithmic Space.
V. BEYOND NP.
1. The Polynomial Hierarchy.
2. Computation That Counts.
3. Polynomial Space.
4. A Glimpse Beyond.
