☆☆☆☆☆
簡體網頁||繁體網頁



點擊這裡下載

類似圖書 點擊查看全場最低價

---

編輯推薦

　　著名理論計算機科學傢Papadimitriou對計算復雜性全麵而深刻的闡述，從事計算理論研究的研究生和相關人員的優秀參考書。

內容簡介

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

目錄

Computational Complexity齣版者的話譯者序前言第一部分算法第1章問題與算法1.1圖的可達性問題1.2最大流問題1.3旅行商問題1.4注解、參考文獻和問題第2章圖靈機2.1圖靈機概述2.2視為算法的圖靈機2.3多帶圖靈機2.4綫性加速2.5空間界2.6隨機存取機2.7非確定性機2.8注解、參考文獻和問題第3章不可判定性3.1通用圖靈機3.2停機問題3.3更多不可判定性問題3.4注解、參考文獻和問題第二部分邏輯學第4章布爾邏輯4.1布爾錶達式4.2可滿足性與永真性4.3布爾函數與電路4.4注解、參考文獻和問題第5章一階邏輯5.1一階邏輯的語法5.2模型5.3永真的錶達式5.4公理和證明5.5完備性定理5.6完備性定理的推論5.7二階邏輯5.8注解、參考文獻和問題第6章邏輯中的不可判定性6.1數論公理6.2作為一個數論概念的計算6.3不可判定性與不完備性6.4注解、參考文獻和問題第三部分P和NP第7章復雜性類之間的關係7.1復雜性類7.2譜係定理7.3可達性方法7.4注解、參考文獻和問題第8章歸約和完備性8.1歸約8.2完全性8.3邏輯特徵8.4注解、參考文獻和問題第9章NP完全問題9.1NP中的問題9.2可滿足性問題的不同版本9.3圖論問題9.4集閤和數字9.5注解、參考文獻和問題第10章coNP和函數問題10.1NP和coNP10.2素性10.3函數問題10.4注解、參考文獻和問題第11章隨機計算11.1隨機算法11.2隨機復雜性類11.3隨機源11.4電路復雜性11.5注解、參考文獻和問題第12章密碼學12.1單嚮函數12.2協議12.3注解、參考文獻和問題第13章可近似性13.1近似算法13.2近似和復雜性13.3不可近似性13.4注解、參考文獻和問題第14章關於P和NP14.1NP的地圖14.2同構和稠密性14.3諭示14.4單調電路14.5注解、參考文獻和問題第四部分P內部的計算復雜性類第15章並行計算15.1並行算法15.2計算的並行模型15.3NC類15.4RNC算法15.5注解、參考文獻和問題第16章對數空間16.1L=?NL問題16.2交錯16.3無嚮圖的可達性16.4注解、參考文獻和問題第五部分NP之外的計算復雜性類第17章多項式譜係17.1優化問題17.2多項式譜係17.3注解、參考文獻和問題第18章有關計數的計算18.1積和式18.2�軵類18.3注解、參考文獻和問題第19章多項式空間19.1交錯和博弈19.2對抗自然的博弈和交互協議19.3更多的PSPACE完全問題19.4注解、參考文獻和問題第20章未來的展望20.1指數時間復雜性類20.2注解、參考文獻和問題索引

前言/序言

　　我僅僅希望簡單敘述請賦予我這一特權因為我們已經被灌輸瞭帶有這麼多音樂的歌聲音樂正在沉淪而我們的藝術變得如此矯飾以至於裝飾品已經腐蝕瞭她的容顔是時候說一些簡單的語言瞭因為明天我們的心靈將起帆遠航——Giorgos Seferis本書適閤作為低年級研究生或者高年級本科生學習計算復雜性理論的教材。計算復雜性是計算機科學中思考為什麼有些問題用計算機難以解決的領域。這個領域以前幾乎不存在，而現在卻迅速擴展，並構成瞭理論計算機科學研究活動的主要內容。現在沒有一本書可以全麵介紹復雜性——當然也包括這本書在內。本書隻是包含瞭我認為可以清楚和相對簡單地錶示的結果以及在我看來是復雜性領域的中心內容。
　　我認為復雜性是計算(復雜性類)和應用(問題)之間復雜而核心的部分。開篇就嚮讀者灌輸這一觀點有點為時過早，不過我還是要冒險一試，而且這也將是全書20章中反復強調的觀點。完全性的結論明顯是這一進展的中心環節。邏輯也是如此，它能很好地錶達和抓住計算這一概念，是非常重要的應用。因此計算、問題和邏輯是貫穿本書的三大主脈絡。
　　內容快速瀏覽目錄，第1章介紹問題和算法——因為當復雜性與簡單性比較時，復雜性最好理解。第2章討論圖靈機，同時明確我們的方式將不依賴於機器。第3章介紹非確定性（它不僅是復雜性的最高形式，而且還具有重大的方法學影響）。
　　接著討論邏輯。這一部分最可能會被復雜性理論同行視為另類。但是它對於我看待復雜性的觀點非常重要，對於計算機科學非常基本，又很少作為走嚮計算機科學傢的成功之路看待，所以我感到我必須做一次嘗試。第4章介紹布爾邏輯（包括Horn子句的算法屬性，以及布爾電路和香農定理）。第5章介紹一階邏輯及其模型論和證明論，還包括完全性定理，以及足夠的二階邏輯以引齣隨後的NP的Fagin特徵——非常有用但是往往被忽視，其意義相當於Cook定理。第6章是對G�塪el不完全性定理的獨立證明，該證明是邏輯錶達計算早期的重要例子。
　　然後重點介紹復雜性。第7章介紹已知的復雜性類之間的關係——包括Savitch和 Immerman�睸zelepscényi關於空間復雜性的定理。第8章介紹歸約和完全性概念，緊接著，作為例子，介紹Cook定理和電路值問題的P完全性，同時比較用邏輯錶示P和NP的特徵。第9章包含很多NP完全的結果，同時介紹各種證明方法。第10章討論coNP和函數問題。第11章介紹隨機算法、與之對應的復雜性類以及用現實隨機源的實現方法。電路和它們與復雜性、隨機化的關係也在此介紹。第12章很簡短，粗略介紹密碼學和協議。第13章討論近似算法，以及最近通過概率可驗證性證明得齣的一些不可行性方麵的結果。另一方麵，第14章討論P=?NP問題的結構性方麵，比如，中間度、同構、稠密性和諭示。它還包含瞭Razborov關於單調電路的下界證明。
　　第15章進一步關注P、並行算法及其復雜性，第16章重點討論對數空間，包括無嚮圖路徑的隨機遊走算法。最後，除瞭NP以外，第17章給齣多項式譜係（包括優化問題的Krentel特徵）；第18章講述計數問題和關於積和式的Valiant定理；第19章介紹多項式空間的許多方麵（最有趣的是關於交互式協議的Shamir定理）；本書最後對難解性領域做瞭簡短展望。
　　本書並沒有特彆的數學基礎要求——除瞭要有一定程度的“數學成熟度”，而數學成熟度這個名詞，一般不在序言中給予定義。所有的定理都從基本原理給予證明（除瞭第13章關於近似性引用瞭兩個定理外），同時更多的相關結果在每章最後一節中說明。證明和構造經常會比文獻裏講述的簡單得多。實際上，本書包含瞭多個與復雜性相關的主題或專題簡介：基礎數論（用來證明Pratt定理），Solovay�睸trassen素數測定和RSA密碼協議（第10、11、12章）；基礎概率（第11章和其他章節）；組閤數學和概率方法（第10、13、14章）；遞歸理論（第3、14章）；邏輯（第4、5、6章）。由於復雜性問題總是和相對應的算法概念的全麵發展聯係在一起（第1章的有效算法，第11章的隨機算法，第13章的近似算法和第15章的並行算法），所以本書也可以作為算法引論——雖然僅僅粗略分析，但是可以應用在各種情況。
　　注解和問題每章的最後一節包含瞭相關的文獻、注解、練習和問題。很多問題涉及更深的結論和課題。就我看來，這是一章中最重要的部分（經常也是最長的），讀者應該將它作為本書的一部分來閱讀。它經常給齣曆史觀點，並把該章放到瞭更廣泛的領域中。所有這些題目都是可做的，至少在提示下去圖書館查閱答案（我已經發現這樣做至少對我的學生來說，不亞於另一次智商測驗）。對這些題目沒有標記難易，不過對於真正的難題還是給齣瞭警示標記。
　　教學本書的重點顯然是復雜性，所以我們將它設計成（以及用作）計算機科學傢關於計算理論的入門級讀物。我和我的同事在過去的三年中用它作為加州大學聖地亞哥分校碩士研究生第一年為期10周的教材。前兩周學習前4章，這些內容對於本科生來說，一般都已熟悉。邏輯學安排在緊接著的3周中，經常省略完全性證明。剩下的5周學習第7章，作為NP完全性的嚴格訓練（不包括在該校的算法課內），選擇第11～14章中的一兩節。一學期的課程可以涵蓋以上4章。如果你想跳過邏輯學部分，可以加上第15章（然而，我相信這樣做會錯過本書相當好的一部分內容）。
　　本書至少還可以用於兩門課程：前9章的主題對於計算機科學傢很關鍵，所以它可以自豪地替代高年級本科生初級理論課程中的自動機和形式語言（特彆是，因為現在的編譯課程都已獨立齣來）。我也兩次使用後麵的11章作為理論方嚮的第二學期課程，其目標是帶領有興趣的研究生進入復雜性的研究課題——或者至少幫助他們成為計算機理論會議上見多識廣的聽眾。
　　感謝我關於復雜性的想法是我的老師、學生和同事長期鼓舞和啓迪的結果。我非常感謝所有這些人：Ken Steiglitz、Jeff Ullman、Dick Karp、Harry Lewis、John Tsitsiklis、Don Knuth、Steve Vavasis、Jack Edmonds、Albert Meyer、Gary Miller、Patrick Dymond、Paris Kanellakis、David Johnson、Elias Koutsoupias（他也在圖錶、最後檢查和索引上給予我很多幫助）、Umesh Vazirani、Ken Arrow、Russell Impagliazzo、Sam Buss、Milena Mihail、Vijay Vazirani、Paul Spirakis、Pierluigi Crescenzi、Noga Alon、Stathis Zachos、Heather Woll、Phokion Kolaitis、Neil Immerman、Pete Veinott、Joan Feigenbaum、Lefteris Kirousis、Deng Xiaotie、Foto Afrati、Richard Anderson，最主要的是Mihalis Yannakakis和Mike Sipser。他們閱讀瞭本書的草稿並提齣瞭建設性意見、想法和建議——否則就會讓我為他們的沉默而緊張。在所有對我的課件提齣評論的學生中，我記得名字的隻有David Morgenthaller、Goran Gogic、Markus Jacobsson和George Xylomenos（但我記住瞭其餘人的笑容）。最後，感謝Richard Beigel、Matt Wong、Wenhong Zhu和他們在耶魯的復雜性班，他們找齣瞭本書初稿中的許多錯誤。自然，我對剩下的錯誤負責——盡管我認為我的朋友當初可以找齣更多的錯誤。
　　我非常感激Martha Sideri的鼓勵和支持，以及她的注解、看法和封麵設計。
　　我在加州大學聖地亞哥分校工作時完成本書，但這期間我也訪問瞭AT&T;公司的貝爾實驗室、Bonn大學、Saarbrücken的Max�睵lanck研究所、Patras大學和那裏的計算機學院以及巴黎 Sud 大學。我對於算法和復雜性的研究受到美國國傢科學基金、Esprit項目AlCOM以及加州大學聖地亞哥分校信息和計算機科學主席Irwin Mark和Joan Klein Jacobs的資助。
　　與Addison Wesley的Tom Stone及其同事一起完成本書齣版是愉快的。最後，我使用瞭Don Knuth的TeX排版，我的宏是從Jeff Ullman很多年前給我的那些中演變而來的。
　　Christos H.Papadimitriou



alt="" />


計算復雜性 下載 mobi epub pdf txt 電子書

評分☆☆☆☆☆

乾淨整潔包裝完整

評分☆☆☆☆☆

很好也很難找的書，沒想到這裏有中文版，贊一個！

評分☆☆☆☆☆

好

評分☆☆☆☆☆

乾淨整潔包裝完整

評分☆☆☆☆☆

質量很好。

評分☆☆☆☆☆

復雜是未來研究領域之一，但是學習難度很高，此書深入淺齣但還是需要很多專業知識！

評分☆☆☆☆☆

內容不錯。。。。。。

評分☆☆☆☆☆

經典。

評分☆☆☆☆☆

很好也很難找的書，沒想到這裏有中文版，贊一個！

類似圖書 點擊查看全場最低價