计算复杂性

出版时间：2005-1  出版社：机械工业出版社  作者：顾小丰等编  页数：159  
Tag标签：无  

内容概要

　　《重点大学计算机教材：计算复杂性》全面、系统地介绍了计算复杂性理论的基本内容和基本方法。内容涉及数值计算的复杂性，主要包括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 多处理机调度问题参考文献