计算复杂性导论

计算复杂性导论
分享
扫描下方二维码分享到微信
打开微信,点击右上角”+“,
使用”扫一扫“即可将网页分享到朋友圈。
作者:
出版社: 高等教育出版社
2002-08
版次: 1
ISBN: 9787040113075
定价: 53.00
装帧: 精装
开本: 16开
纸张: 胶版纸
页数: 378页
字数: 370千字
正文语种: 简体中文
  •   《计算复杂性导论(精)》可用作计算机专业、计算数学专业的计算机理论课程的教材,也是有关研究人员不可或缺的参考书。计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。《计算复杂性导论(精)》对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论,如计算模型NP-完全性,以及较深入的课题,如线路复杂性、概率复杂性和交互证明系统等。此外,《计算复杂性导论(精)》还包括了复杂性理论近年来两个较重大的突破,即概率可验证明及其在近似算法上的应用和平均NP-完全理论。《计算复杂性导论(精)》中所有结果均有严格的数学证明,在每章后配有相关练习题。   堵丁柱,1948年生。中国科学院应用数学所运筹学硕士(1981)。美国加里福利亚大学圣巴巴拉分校数学博士(1985)。美国伯克利数学科学研究所博士后(1985.1986)。美国麻省理工学院助理教授(1986-1987)。美国普林斯顿大学访问学者(1990-1991)。现任美国明尼苏达大学计算机科学系教授,中国科学院应用数学所研究员。Journal0fCombinatorialOptimization主编,BookSeriesofCombinatorialOptimization和BookSeriesofNetworksTheoryandApplications主编。主要研究方向为组合优化,计算复杂性,算法分析与设计,计算机和通讯网络。发表论文130篇,著书7本。1993年获中国科学院自然科学一等奖。1995年获中国自然科学二等奖。1998年获美国运筹和管理学会CSTC奖(计算机与运筹学边缘科学奖)。
      葛可一,1950年生。台湾新竹清华大学数学学士(1972)。美国俄亥俄州立大学数学硕士(1974),计算机科学博士(1979)。现任美国纽约州立大学石溪分校计算机科学系教授.SIAMJournalonComputing与JournalofComplexity编辑。曾主持多项美国自然科学基金会研究课题。主要研究方向为计算复杂性理论,数值计算复杂性和可计算性理论。发表论文55篇,著书3本。
      王杰,1961年生。中山大学计算机科学系计算数学专业学士(1982),软件专业硕士(1984),美国波士顿大学计算机科学博士(1990)。现任美国麻萨诸塞大学罗威尔分校计算机科学系教授,并任网络与系统安全实验室主任。主要研究方向为平均计算复杂性理论,网络与系统安全,应用算法。曾主持多项美国自然科学基金会的课题及美国英特尔(Intel)公司的课题。发表论文70篇及编书两本。1991年获美国自然科学基金会科研启动奖,2002年获英特尔公司大学项目IXA研究奖。 前言
    第一章计算模型
    1.1符号行,编码和布尔函数
    1.2确定型图灵机
    1.3非确定型图灵机
    练习题
    第二章计算复杂性类
    2.1时间与空间
    2.2通用图灵机
    2.3对角线方法
    2.4模拟
    练习题
    第三章NP-完全问题
    3.1NP
    3.2Cook定理
    3.3NP-完全问题的例子
    3.4多项式时间图灵归约
    练习题
    第四章多项式时间分层和多项式空间
    4.1非确定型带神喻图灵机
    4.2多项式时间分层
    4.3PH中的完全问题
    4.4交替图灵机
    4.5PSPACE-完全问题
    练习题
    第五章线路复杂性
    5.1布尔线路
    5.2单调递增函数与单调线路
    5.3奇偶性函数与深度有界线路
    5.4多项式规模布尔线路
    练习题
    第六章NP类的结构
    6.1NP中的非完全问题
    6.2单向函数及其在密码学中的应用
    6.3NC
    6.4P-完全性
    6.5NP-完全问题的密度
    6.6EXP-完全问题的密度
    练习题
    第七章概率机与复杂性类
    7.1随机算法
    7.2概率图灵机及其时间复杂性
    7.3带有界误差的概率机
    7.4BPP,NP和多项式时间分层
    练习题
    第八章计数复杂性
    8.1计数类#P
    8.2#P-完全问题
    8.3■P和多项式时间分层
    8.4#P和多项式时间分层
    练习题
    第九章交互证明系统
    9.1例子与定义
    9.2亚瑟默林证明系统
    9.3AM分层与多项式时间分层
    9.4IP与AM
    9.5IP与PSPACE
    练习题
    第十章概率可验证明
    10.1PCP的定义
    10.2NEXPPOLY的PCP特征
    10.2.1主要证明
    10.2.2多重线性测试系统
    10.2.3和检验系统
    10.3NP的PCP特征
    10.3.1使用O(logn)个随机数码的PCP系统
    10.3.2低阶测试系统
    10.3.3两个PCP系统的复合
    10.3.4阅读常数多神喻数码的PCP系统
    练习题
    第十一章近似解的复杂性
    11.1胆完全优化问题
    11.2PCP和不可近似性
    11.3优化问题的归约
    11.4难近似的优化问题
    练习题
    第十二章平均NP-完全性理论
    12.1平均易解性
    12.2多项式时间归约
    12.3p-分布
    12.4平均NP-完全问题
    12.5扁平分布与随机归约
    12.6扁平分布下的完全问题
    12.7可抽样分布
    练习题
    参考文献
    名词索引(汉英对照)
  • 内容简介:
      《计算复杂性导论(精)》可用作计算机专业、计算数学专业的计算机理论课程的教材,也是有关研究人员不可或缺的参考书。计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。《计算复杂性导论(精)》对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论,如计算模型NP-完全性,以及较深入的课题,如线路复杂性、概率复杂性和交互证明系统等。此外,《计算复杂性导论(精)》还包括了复杂性理论近年来两个较重大的突破,即概率可验证明及其在近似算法上的应用和平均NP-完全理论。《计算复杂性导论(精)》中所有结果均有严格的数学证明,在每章后配有相关练习题。
  • 作者简介:
      堵丁柱,1948年生。中国科学院应用数学所运筹学硕士(1981)。美国加里福利亚大学圣巴巴拉分校数学博士(1985)。美国伯克利数学科学研究所博士后(1985.1986)。美国麻省理工学院助理教授(1986-1987)。美国普林斯顿大学访问学者(1990-1991)。现任美国明尼苏达大学计算机科学系教授,中国科学院应用数学所研究员。Journal0fCombinatorialOptimization主编,BookSeriesofCombinatorialOptimization和BookSeriesofNetworksTheoryandApplications主编。主要研究方向为组合优化,计算复杂性,算法分析与设计,计算机和通讯网络。发表论文130篇,著书7本。1993年获中国科学院自然科学一等奖。1995年获中国自然科学二等奖。1998年获美国运筹和管理学会CSTC奖(计算机与运筹学边缘科学奖)。
      葛可一,1950年生。台湾新竹清华大学数学学士(1972)。美国俄亥俄州立大学数学硕士(1974),计算机科学博士(1979)。现任美国纽约州立大学石溪分校计算机科学系教授.SIAMJournalonComputing与JournalofComplexity编辑。曾主持多项美国自然科学基金会研究课题。主要研究方向为计算复杂性理论,数值计算复杂性和可计算性理论。发表论文55篇,著书3本。
      王杰,1961年生。中山大学计算机科学系计算数学专业学士(1982),软件专业硕士(1984),美国波士顿大学计算机科学博士(1990)。现任美国麻萨诸塞大学罗威尔分校计算机科学系教授,并任网络与系统安全实验室主任。主要研究方向为平均计算复杂性理论,网络与系统安全,应用算法。曾主持多项美国自然科学基金会的课题及美国英特尔(Intel)公司的课题。发表论文70篇及编书两本。1991年获美国自然科学基金会科研启动奖,2002年获英特尔公司大学项目IXA研究奖。
  • 目录:
    前言
    第一章计算模型
    1.1符号行,编码和布尔函数
    1.2确定型图灵机
    1.3非确定型图灵机
    练习题
    第二章计算复杂性类
    2.1时间与空间
    2.2通用图灵机
    2.3对角线方法
    2.4模拟
    练习题
    第三章NP-完全问题
    3.1NP
    3.2Cook定理
    3.3NP-完全问题的例子
    3.4多项式时间图灵归约
    练习题
    第四章多项式时间分层和多项式空间
    4.1非确定型带神喻图灵机
    4.2多项式时间分层
    4.3PH中的完全问题
    4.4交替图灵机
    4.5PSPACE-完全问题
    练习题
    第五章线路复杂性
    5.1布尔线路
    5.2单调递增函数与单调线路
    5.3奇偶性函数与深度有界线路
    5.4多项式规模布尔线路
    练习题
    第六章NP类的结构
    6.1NP中的非完全问题
    6.2单向函数及其在密码学中的应用
    6.3NC
    6.4P-完全性
    6.5NP-完全问题的密度
    6.6EXP-完全问题的密度
    练习题
    第七章概率机与复杂性类
    7.1随机算法
    7.2概率图灵机及其时间复杂性
    7.3带有界误差的概率机
    7.4BPP,NP和多项式时间分层
    练习题
    第八章计数复杂性
    8.1计数类#P
    8.2#P-完全问题
    8.3■P和多项式时间分层
    8.4#P和多项式时间分层
    练习题
    第九章交互证明系统
    9.1例子与定义
    9.2亚瑟默林证明系统
    9.3AM分层与多项式时间分层
    9.4IP与AM
    9.5IP与PSPACE
    练习题
    第十章概率可验证明
    10.1PCP的定义
    10.2NEXPPOLY的PCP特征
    10.2.1主要证明
    10.2.2多重线性测试系统
    10.2.3和检验系统
    10.3NP的PCP特征
    10.3.1使用O(logn)个随机数码的PCP系统
    10.3.2低阶测试系统
    10.3.3两个PCP系统的复合
    10.3.4阅读常数多神喻数码的PCP系统
    练习题
    第十一章近似解的复杂性
    11.1胆完全优化问题
    11.2PCP和不可近似性
    11.3优化问题的归约
    11.4难近似的优化问题
    练习题
    第十二章平均NP-完全性理论
    12.1平均易解性
    12.2多项式时间归约
    12.3p-分布
    12.4平均NP-完全问题
    12.5扁平分布与随机归约
    12.6扁平分布下的完全问题
    12.7可抽样分布
    练习题
    参考文献
    名词索引(汉英对照)
查看详情
好书推荐 / 更多
计算复杂性导论
北平学人访问记(上)(碎金文丛5)
贺逸文
计算复杂性导论
文青之死
赖香吟 ;后浪
计算复杂性导论
立马上菜
M.F.K.费雪
计算复杂性导论
自愈之路:开创癌症免疫疗法的科学家们
[美]尼尔·卡纳万(Neil Canavan)
计算复杂性导论
哲思与海:一部诗意的哲学随笔
[美]戴维·法雷尔·克雷尔 著;陈瑾 译
计算复杂性导论
锥形帐篷的起源
乔尼·休斯
计算复杂性导论
事邦国之神祇:唐至北宋吉礼变迁研究
朱溢 著
计算复杂性导论
《剑桥非洲史·20世纪卷(1905—1940)》 《剑桥非洲史·20世纪卷(1940—1975)》(丛书2册)
安德鲁·罗伯茨;迈克尔·克劳德
计算复杂性导论
面具与乌托邦:墨西哥人民及其文化剪影
[墨]萨穆埃尔·拉莫斯
计算复杂性导论
苏联的外宾商店:为了工业化所需的黄金
[俄罗斯]叶列娜·亚历山德罗夫娜·奥金娜
计算复杂性导论
警治的终结
[英]亚历克斯·S.维塔莱 著;王飞、张鹏瀚 译
计算复杂性导论
用电影燃尽欲望
[【日】]园子温;余梦娇