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

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

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

定 價:¥53.00

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

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

內(nèi)容簡介

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

作者簡介

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

圖書目錄

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

本目錄推薦

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