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

图书标准信息

• 作者 顾小丰 著
• 出版社 机械工业出版社
• 出版时间 2005-01
• 版次 1
• ISBN 9787111153146
• 定价 19.00元
• 装帧 平装
• 开本 16开
• 纸张 其他
• 页数 159页
• 正文语种 简体中文

【内容简介】

《重点大学计算机教材：计算复杂性》全面、系统地介绍了计算复杂性理论的基本内容和基本方法。内容涉及数值计算的复杂性，主要包括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.3Kuhn算法的收敛性(一)
2.4Kuhn算法的收敛性(二)
第3章Kuhn算法的效率
3.1误差估计
3.2成本估计
3.3单调性问题
3.4关于单调性的结果
第4章牛顿法及其计算复杂性简介

第二部分计算机科学的复杂性理论
第5章算法的计算复杂性和计算模型
5.1算法及其计算复杂性
5.2确定型图灵机
5.3随机存取机
5.4RAM机的程序的计算复杂性
5.5图灵机和RAM机的相关性
5.6PIDGINALGOL--一种高级语言
第6章几个"难"问题的算法设计
6.1贪心法和背包问题
6.2动态规划和货郎担问题
6.3回溯法和图的可着色性问题
6.4分枝限界法和带时限的作业调度问题
第7章NP完全问题
7.1判定问题.语言和编码
7.2多项式变换与可满足性问题
7.3非确定型图灵机
7.4NP类
7.5NP完全问题与Cook定理
7.6强NP完全问题
7.7Co-NP类问题
7.8NP困难问题
7.9空间复杂性简介
第8章NP完全性证明
8.1六个基本的NP完全问题
8.2NP完全性的证明方法
8.3P类问题的证明
第9章近似算法
9.1近似的接近程度衡量
9.20-1背包问题
9.3装箱问题
9.4图的着色问题
9.5货郎担问题
9.6多处理机调度问题
参考文献