计算复杂性/重点大学计算机教材

本书全面、系统地介绍了计算复杂性理论的基本内容和基本方法。内容涉及数值计算的复杂性，主要包括Kuhn算法设计、正确性证明和复杂性分析；算法复杂性和计算模型；贪心法、动态规划、回溯法和分枝限界法等问题的算法设计方法以及P类、NP类和NPC类问题及其证明方法、若干NPC问题的近似算法。 本书可作为计算机专业及数学专业的本科生或研究生的教材，也可供从事数学和计算机科学的教师和研究人员参考。

顾小丰，1966年，1991年生于兰州大学数学系获理学硕士学位。现任电子科技大学计算机学院高级工程师，硕士研究生导师。主要从事网络计算机及应用、并行计算研究和教学。参与完成了“八五”、“九五”军事预研项目两项，获2001年度“国防科学技术进步奖”二等奖，撰写《离散数学》和《离散数学及其应用》两本教材。 孙世新教授，1940年3月生。电子科技大学计算机学院教授，计算机应用技术博士生导师，主要从事计算机科学理论的研究与教学工作，主要研究方向为网络计算技术、并行/分布式计算及其应用、信息压缩技术、数值计算与组合算法等。主持参与“九五”军事预研项目、国家高性能计算基金、863计划等多项课题研究。自88年至今，在国内外著名期刊杂志发表论文60余篇，其中近20余篇被国际著名的三大检索系统SCI、EI、ISTP以及美国的著名检索杂M.R.和西德的“数学文摘”等收录评论，出版《组合数学》教材一部。获省科技进步三等奖，国防科技二等奖。

前言 作者简介 第一部分 数值计算的复杂性   第1章 代数方程和数值计算的复杂性理论简介     1.1 代数方程的不动点迭代算法     1.2 收敛性和复杂性--算法优劣判别的两个层次   第2章 代数方程的Kuhn算法     2.1 剖分法与标号法     2.1.1 剖分法     2.1.2 标号法     2.2 互补轮回算法     2.2.1 互补轮回算法原理     2.2.2 进口出口分析     2.3 Kuhn算法的收敛性(一)     2.4 Kuhn算法的收敛性(二)   第3章 Kuhn算法的效率     3.1 误差估计     3.2 成本估计     3.3 单调性问题     3.4 关于单调性的结果   第4章 牛顿法及其计算复杂性简介 第二部 分计算机科学的复杂性理论   第5章 算法的计算复杂性和计算模型     5.1 算法及其计算复杂性     5.2 确定型图灵机     5.3 随机存取机     5.4 RAM机的程序的计算复杂性     5.5 图灵机和RAM机的相关性     5.6 PIDGIN ALGOL--一种高级语言   第6章 几个"难"问题的算法设计     6.1 贪心法和背包问题     6.2 动态规划和货郎担问题     6.3 回溯法和图的可着色性问题     6.4 分枝限界法和带时限的作业调度问题   第7章 NP完全问题     7.1 判定问题.语言和编码     7.2 多项式变换与可满足性问题     7.3 非确定型图灵机     7.4 NP类     7.5 NP完全问题与Cook定理     7.6 强NP完全问题     7.7 Co-NP类问题     7.8 NP困难问题     7.9 空间复杂性简介   第8章 NP完全性证明     8.1 六个基本的NP完全问题     8.2 NP完全性的证明方法     8.3 P类问题的证明   第9章 近似算法     9.1 近似的接近程度衡量     9.2 0-1背包问题     9.3 装箱问题     9.4 图的着色问题     9.5 货郎担问题     9.6 多处理机调度问题 参考文献