人民幣定價：28 元
定 價：NT$ 168 元
優惠價：87 折 146 元
絕版無法訂購
相關商品
商品簡介
名人/編輯推薦
目次
商品簡介
名人/編輯推薦
呂克偉編著的《計算復雜性理論基礎》首先介紹計算復雜性概述、一些計算問題和邏輯，然后詳細介紹計算模型、P vs NP問題、歸約和NP完備性理論等；接著針對信息安全和算法設計等專業特點，詳細介紹隨機化算法、(非)一致電路；最后簡單介紹幾個較深入的課題：交互語言類、計數復雜類、概率可驗證語言類等。我們試圖通過對計算復雜性理論的基礎知識通俗直觀地介紹，幫助讀者掌握該理論的思想方法，為進一步開展計算機科學的相關領域的學習和研究奠定基礎。因此，本書不僅適合作為計算機科學各專業高年級本科生和低年級研究生(特別是信息安全專業)基礎課教材，也可供有關研究人員參考。
目次
第0章引言
習題
第1章一些計算問題
習題
第2章邏輯概述
2.1布爾邏輯
2.2一階邏輯
2.3公理和證明
2.4存在二階邏輯
第3章計算模型
3.1字符串、編碼
3.2算法時間的度量與模型
3.3圖靈機基礎
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.4NP一關系
6.5Oracle圖靈機
6.6自歸約
習題
第7章NP—完備問題、coNP與函數計算
7.1NP—完備問題
7.1.1可滿足問題的一些變形
7.1.2圖論中的NP—完備問題
7.1.3集合與數
7.2偽多項式算法和強NP—完備問題
7.3P與NP
7.4函數問題
7.5coNP
習題
第8章隨機化計算
8.1隨機化算法
8.1.1概率素性檢驗
8.1.2符號行列式
8.1.3隨機游動
8.2概率計算
8.3RP，coRP，ZPP和PP語言類
8.4魯棒性
習題
第9章電路復雜度和非一致多項式時間類
9.1電路復雜度
9.2單調電路（：MonotoneCircuits）
9.3非一致多項式時間類（P／Poly）
第10章幾類語言類介紹
10.1多項式譜系（I>olynomialHierarchy）
10.1.1多項式譜系的定義（PH）
10.1.2交錯圖靈機與多項式譜系（PH）
10.2交互證明系統
10.2.1證明
10.2.2交互證明系統IP
10.2.3公共擲幣系統和輪數
10.3概率可驗證證明系統
10.3.1PCP系統
10.3.2PCP系統與交互證明系統
10.3.3PCP語言
10.3.4復雜度度量
10.3.5PCP系統的相關結論
10.4計數類
術語中英文對照表
索引
參考文獻
習題
第1章一些計算問題
習題
第2章邏輯概述
2.1布爾邏輯
2.2一階邏輯
2.3公理和證明
2.4存在二階邏輯
第3章計算模型
3.1字符串、編碼
3.2算法時間的度量與模型
3.3圖靈機基礎
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.4NP一關系
6.5Oracle圖靈機
6.6自歸約
習題
第7章NP—完備問題、coNP與函數計算
7.1NP—完備問題
7.1.1可滿足問題的一些變形
7.1.2圖論中的NP—完備問題
7.1.3集合與數
7.2偽多項式算法和強NP—完備問題
7.3P與NP
7.4函數問題
7.5coNP
習題
第8章隨機化計算
8.1隨機化算法
8.1.1概率素性檢驗
8.1.2符號行列式
8.1.3隨機游動
8.2概率計算
8.3RP，coRP，ZPP和PP語言類
8.4魯棒性
習題
第9章電路復雜度和非一致多項式時間類
9.1電路復雜度
9.2單調電路（：MonotoneCircuits）
9.3非一致多項式時間類（P／Poly）
第10章幾類語言類介紹
10.1多項式譜系（I>olynomialHierarchy）
10.1.1多項式譜系的定義（PH）
10.1.2交錯圖靈機與多項式譜系（PH）
10.2交互證明系統
10.2.1證明
10.2.2交互證明系統IP
10.2.3公共擲幣系統和輪數
10.3概率可驗證證明系統
10.3.1PCP系統
10.3.2PCP系統與交互證明系統
10.3.3PCP語言
10.3.4復雜度度量
10.3.5PCP系統的相關結論
10.4計數類
術語中英文對照表
索引
參考文獻
您曾經瀏覽過的商品
購物須知
大陸出版品因裝訂品質及貨運條件與台灣出版品落差甚大，除封面破損、內頁脫落等較嚴重的狀態，其餘商品將正常出貨。
特別提醒：部分書籍附贈之內容(如音頻mp3或影片dvd等)已無實體光碟提供，需以QR CODE 連結至當地網站註冊“並通過驗證程序”，方可下載使用。
無現貨庫存之簡體書，將向海外調貨：
海外有庫存之書籍，等候約45個工作天;
海外無庫存之書籍，平均作業時間約60個工作天，然不保證確定可調到貨，尚請見諒。
為了保護您的權益，「三民網路書店」提供會員七日商品鑑賞期(收到商品為起始日)。
若要辦理退貨，請在商品鑑賞期內寄回，且商品必須是全新狀態與完整包裝(商品、附件、發票、隨貨贈品等)否則恕不接受退貨。
優惠價：87
146
絕版無法訂購