无卡无码中文字幕免费,一本大道大臿蕉香蕉大视频

內容簡介

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

作者簡介

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

圖書目錄

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