《計算複雜性導論》是2002年高等教育出版社出版的圖書，作者是堵丁柱、葛可一、王傑。本書對計算機科學中這一重要理論做了全面的介紹。其內容包含基本理論，如計算模型NP-完全性，以及較深入的課題，如線路複雜性、機率複雜性和互動證明系統等。
基本介紹
- 書名：計算複雜性導論
- ISBN：9787040113075
- 頁數： 378頁
- 出版社： 高等教育出版社
- 出版時間：2002年8月1日
- 裝幀：精裝
- 開本：16
- 叢書名：當代科學前沿論叢
作者簡介,內容簡介,目錄,
作者簡介
堵丁柱，1948年生。中國科學院套用數學所運籌學碩士（1981）。美國加里福利亞大學聖巴巴拉分校數學博士（1985）。美國伯克利數學科學研究所博士後（1985.1986）。美國麻省理工學院助理教授（1986－1987）。美國普林斯頓大學訪問學者（1990－1991）。現任美國明尼蘇達大學計算機科學系教授，中國科學院套用數學所研究員。Journal 0f Combinatorial Optimization主編，Book Series ofCombinatorial Optimization和Book Series of Networks Theory and Applications主編。主要研究方向為組合最佳化，計算複雜性，算法分析與設計，計算機和通訊網路。發表論文130篇，著書7本。1993年獲中國科學院自然科學一等獎。1995年獲中國自然科學二等獎。1998年獲美國運籌和管理學會CSTC獎（計算機與運籌學邊緣科學獎）。
葛可一，1950年生。台灣新竹清華大學數學學士（1972）。美國俄亥俄州立大學數學碩士（1974），計算機科學博士（1979）。現任美國紐約州立大學石溪分校計算機科學系教授.SIAM Journal on Computing與Journal of Complexity編輯。曾主持多項美國自然科學基金會研究課題。主要研究方向為計算複雜性理論，數值計算複雜性和可計算性理論。發表論文55篇，著書3本。
王傑，1961年生。中山大學計算機科學系計算數學專業學士（1982），軟體專業碩士（1984），美國波士頓大學計算機科學博士（1990）。現任美國麻薩諸塞大學羅威爾分校計算機科學系教授，並任網路與系統安全實驗室主任。主要研究方向為平均計算複雜性理論，網路與系統安全，套用算法。曾主持多項美國自然科學基金會的課題及美國英特爾（Intel）公司的課題。發表論文70篇及編書兩本。1991年獲美國自然科學基金會科研啟動獎，2002年獲英特爾公司大學項目IXA研究獎。
內容簡介
《計算複雜性導論》可用作計算機專業、計算數學專業的計算機理論課程的教材，也是有關研究人員不可或缺的參考書。計算複雜性理論是用數學方法研究使用數位計算機解決各種算法問題困難度的理論。此外，《計算複雜性導論》還包括了複雜性理論近年來兩個較重大的突破，即機率可驗證明及其在近似算法上的套用和平均NP-完全理論。《計算複雜性導論》中所有結果均有嚴格的數學證明，在每章後配有相關練習題。
目錄
1，計算模型
2，計算複雜性類
3，NP-完全問題
4，多項式時間分層和多項式空間
5，線路複雜性
6，NP類的結構
7，機率機與複雜性類
8，計數複雜性
9，互動證明系統
10，機率可驗證明
11，近似解的複雜性
12，平均NP-完全性理論
