注冊(cè) | 登錄讀書(shū)好,好讀書(shū),讀好書(shū)!
讀書(shū)網(wǎng)-DuShu.com
當(dāng)前位置: 首頁(yè)出版圖書(shū)科學(xué)技術(shù)計(jì)算機(jī)/網(wǎng)絡(luò)計(jì)算機(jī)科學(xué)理論與基礎(chǔ)知識(shí)計(jì)算復(fù)雜性導(dǎo)論

計(jì)算復(fù)雜性導(dǎo)論

計(jì)算復(fù)雜性導(dǎo)論

定 價(jià):¥53.00

作 者: 堵丁柱,葛可一,王潔著
出版社: 高等教育出版社
叢編項(xiàng): 當(dāng)代科學(xué)前沿論叢
標(biāo) 簽: 暫缺

ISBN: 9787040113075 出版時(shí)間: 2002-08-01 包裝: 平裝
開(kāi)本: 23cm 頁(yè)數(shù): 377 字?jǐn)?shù):  

內(nèi)容簡(jiǎn)介

  《計(jì)算復(fù)雜性導(dǎo)論(精)》可用作計(jì)算機(jī)專(zhuān)業(yè)、計(jì)算數(shù)學(xué)專(zhuān)業(yè)的計(jì)算機(jī)理論課程的教材,也是有關(guān)研究人員不可或缺的參考書(shū)。計(jì)算復(fù)雜性理論是用數(shù)學(xué)方法研究使用數(shù)位計(jì)算機(jī)解決各種算法問(wèn)題困難度的理論?!队?jì)算復(fù)雜性導(dǎo)論(精)》對(duì)計(jì)算機(jī)科學(xué)中這一重要理論做了全面的介紹。其內(nèi)容包含基本理論,如計(jì)算模型NP-完全性,以及較深入的課題,如線路復(fù)雜性、概率復(fù)雜性和交互證明系統(tǒng)等。此外,《計(jì)算復(fù)雜性導(dǎo)論(精)》還包括了復(fù)雜性理論近年來(lái)兩個(gè)較重大的突破,即概率可驗(yàn)證明及其在近似算法上的應(yīng)用和平均NP-完全理論?!队?jì)算復(fù)雜性導(dǎo)論(精)》中所有結(jié)果均有嚴(yán)格的數(shù)學(xué)證明,在每章后配有相關(guān)練習(xí)題。

作者簡(jiǎn)介

  堵丁柱,1948年生。中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)所運(yùn)籌學(xué)碩士(1981)。美國(guó)加里福利亞大學(xué)圣巴巴拉分校數(shù)學(xué)博士(1985)。美國(guó)伯克利數(shù)學(xué)科學(xué)研究所博士后(1985.1986)。美國(guó)麻省理工學(xué)院助理教授(1986-1987)。美國(guó)普林斯頓大學(xué)訪問(wèn)學(xué)者(1990-1991)。現(xiàn)任美國(guó)明尼蘇達(dá)大學(xué)計(jì)算機(jī)科學(xué)系教授,中國(guó)科學(xué)院應(yīng)用數(shù)學(xué)所研究員。Journal 0f Combinatorial Optimization主編,Book Series ofCombinatorial Optimization和Book Series of Networks Theory and Applications主編。主要研究方向?yàn)榻M合優(yōu)化,計(jì)算復(fù)雜性,算法分析與設(shè)計(jì),計(jì)算機(jī)和通訊網(wǎng)絡(luò)。發(fā)表論文130篇,著書(shū)7本。1993年獲中國(guó)科學(xué)院自然科學(xué)一等獎(jiǎng)。1995年獲中國(guó)自然科學(xué)二等獎(jiǎng)。1998年獲美國(guó)運(yùn)籌和管理學(xué)會(huì)CSTC獎(jiǎng)(計(jì)算機(jī)與運(yùn)籌學(xué)邊緣科學(xué)獎(jiǎng))。葛可一,1950年生。臺(tái)灣新竹清華大學(xué)數(shù)學(xué)學(xué)士(1972)。美國(guó)俄亥俄州立大學(xué)數(shù)學(xué)碩士(1974),計(jì)算機(jī)科學(xué)博士(1979)。現(xiàn)任美國(guó)紐約州立大學(xué)石溪分校計(jì)算機(jī)科學(xué)系教授.SIAM Journal on Computing與Journal of Complexity編輯。曾主持多項(xiàng)美國(guó)自然科學(xué)基金會(huì)研究課題。主要研究方向?yàn)橛?jì)算復(fù)雜性理論,數(shù)值計(jì)算復(fù)雜性和可計(jì)算性理論。發(fā)表論文55篇,著書(shū)3本。王杰,1961年生。中山大學(xué)計(jì)算機(jī)科學(xué)系計(jì)算數(shù)學(xué)專(zhuān)業(yè)學(xué)士(1982),軟件專(zhuān)業(yè)碩士(1984),美國(guó)波士頓大學(xué)計(jì)算機(jī)科學(xué)博士(1990)?,F(xiàn)任美國(guó)麻薩諸塞大學(xué)羅威爾分校計(jì)算機(jī)科學(xué)系教授,并任網(wǎng)絡(luò)與系統(tǒng)安全實(shí)驗(yàn)室主任。主要研究方向?yàn)槠骄?jì)算復(fù)雜性理論,網(wǎng)絡(luò)與系統(tǒng)安全,應(yīng)用算法。曾主持多項(xiàng)美國(guó)自然科學(xué)基金會(huì)的課題及美國(guó)英特爾(Intel)公司的課題。發(fā)表論文70篇及編書(shū)兩本。1991年獲美國(guó)自然科學(xué)基金會(huì)科研啟動(dòng)獎(jiǎng),2002年獲英特爾公司大學(xué)項(xiàng)目IXA研究獎(jiǎng)。

圖書(shū)目錄

第一章  計(jì)算模型                  
 1. 1  符號(hào)行, 編碼和布爾函數(shù)                  
 1. 2  確定型圖靈機(jī)                  
 1. 3  非確定型圖靈機(jī)                  
 練習(xí)題                  
 第二章  計(jì)算復(fù)雜性類(lèi)                  
 2. l  時(shí)間與空間                  
 2. 2  通用圖靈機(jī)                  
 2. 3  對(duì)角線方法                  
 2. 4  模擬                  
 練習(xí)題                  
 第三章  NP-完全問(wèn)題                  
 3. 1  NP                  
 3. 2  Cook定理                  
 3. 3  NP-完全問(wèn)題的例子                  
 3. 4  多項(xiàng)式時(shí)間圖靈歸約                  
 練習(xí)題                  
 第四章  多項(xiàng)式時(shí)間分層和多項(xiàng)式空間                  
 4. 1  非確定型帶神喻圖靈機(jī)                  
 4. 2  多項(xiàng)式時(shí)間分層                  
 4. 3  PH中的完全問(wèn)題                  
 4. 4  交替圖靈機(jī)                  
 4. 5  PSPACE-完全問(wèn)題                  
 練習(xí)題                  
 第五章  線路復(fù)雜性                  
 5. 1  布爾線路                  
 5. 2  單調(diào)遞增函數(shù)與單調(diào)線路                  
 5. 3  奇偶性函數(shù)與深度有界線路                  
 5. 4  多項(xiàng)式規(guī)模布爾線路                  
 練習(xí)題                  
 第六章  NP類(lèi)的結(jié)構(gòu)                  
 6. 1  NP中的非完全問(wèn)題                  
 6. 2  單向函數(shù)及其在密碼學(xué)中的應(yīng)用                  
 6. 3  NC                  
 6. 4  P-完全性                  
 6. 5  NP-完全問(wèn)題的密度                  
 6. 6  EXP-完全問(wèn)題的密度                  
 練習(xí)題                  
 第七章  概率機(jī)與復(fù)雜性類(lèi)                  
 7. 1  隨機(jī)算法                  
 7. 2  概率圖靈機(jī)及其時(shí)間復(fù)雜性                  
 7. 3  帶有界誤差的概率機(jī)                  
 7. 4  BPP, NP和多項(xiàng)式時(shí)間分層                  
 練習(xí)題                  
 第八章  計(jì)數(shù)復(fù)雜性                  
 8. 1  計(jì)數(shù)類(lèi)#尸                  
 8. 2  #P-完全問(wèn)題                  
 8. 3  P和多項(xiàng)式時(shí)間分層                  
 8. 4  #P和多項(xiàng)式時(shí)間分層                  
 練習(xí)題                  
 第九章  交互證明系統(tǒng)                  
 9. 1  例子與定義                  
 9. 2  亞瑟一默林證明系統(tǒng)                  
 9. 3  AM分層與多項(xiàng)式時(shí)間分層                  
 9. 4  IP與 AM                  
 9. 5  IP與 PSPACE                  
 練習(xí)題                  
 第十章  概率可驗(yàn)證明                  
 10. 1  PCP的定義                  
 10. 2  NEXPPOLY的PCP特征                  
 10. 2. 1  主要證明                  
 10. 2. 2  多重線性測(cè)試系統(tǒng)                  
 10. 2. 3  和檢驗(yàn)系統(tǒng)                  
 10. 3  NP的 PCP特征                  
 10. 3. 1  使用O(logn)個(gè)隨機(jī)數(shù)碼的  PCP系統(tǒng)                  
 10. 3. 2  低階測(cè)試系統(tǒng)                  
 10. 3. 3  兩個(gè)PCP系統(tǒng)的復(fù)合                  
 10. 3. 4  閱讀常數(shù)多神喻數(shù)碼的PCP系統(tǒng)                  
 練習(xí)題                  
 第十一章  近似解的復(fù)雜性                  
 11. 1  NP-完全優(yōu)化問(wèn)題                  
 11. 2  PCP和不可近似性                  
 11. 3  優(yōu)化問(wèn)題的歸約                  
 11. 4  難近似的優(yōu)化問(wèn)題                  
 練習(xí)題                  
 第十二章  平均NP-完全性理論                  
 12. l  平均易解性                  
 12. 2  多項(xiàng)式時(shí)間歸約                  
 12. 3  p-分布                  
 12. 4  平均NP-完全問(wèn)題                  
 12. 5  扁平分布與隨機(jī)歸約                  
 12. 6  扁平分布下的完全問(wèn)題                  
 12. 7  可抽樣分布                  
 練習(xí)題                  
 參考文獻(xiàn)                  
 名詞索引(漢英對(duì)照)                  
                   
                   

本目錄推薦

掃描二維碼
Copyright ? 讀書(shū)網(wǎng) m.ranfinancial.com 2005-2020, All Rights Reserved.
鄂ICP備15019699號(hào) 鄂公網(wǎng)安備 42010302001612號(hào)