普通高等教育“十一五”计算机类规划教材：算法设计方法

　　前言
　　第1章 算法设计与分析概论
　　1.1 算法的定义和特征
　　1.2 算法的描述
　　1.3 算法分析
　　1.4 递归方程求解
　　1.4.1 递归公式的展开
　　1.4.2 常系数线性齐次递归方程的特征方程求解方法
　　1.4.3 常系数线性非齐次递归方程求解
　　1.5 生成函数
　　1.6 习题
　　第2章 分治与递归算法
　　2.1 分治与递归算法的基本思路
　　2.2 查找中的分治与递归算法
　　2.2.1 二分查找算法
　　2.2.2 二叉树查找
　　2.2.3 AVL树
　　2.3 排序问题的分治与递归算法
　　2.3.1 合并排序
　　2.3.2 快速排序
　　2.4 矩阵乘法的strassen算法
　　2.5 快速傅里叶变换
　　2.5.1 离散傅里叶变换
　　2.5.2 快速傅里叶变换算法
　　2.6 减治与递归
　　2.7 变治与递归
　　2.8 习题
　　第3章 散列与凝聚算法
　　3.1 散列算法
　　3.1.1 散列查找算法
　　3.1.2 桶排序算法
　　3.2 矩阵乘法的凝聚算法
　　3.2.1 非负整数矩阵乘法的凝聚算法
　　3.2.2 矩阵乘法的凝聚算法的改进
　　3.2.3 布尔矩阵乘法的凝聚算法
　　3.3 非负整数向量卷积的凝聚算法
　　3.4 习题
　　第4章 贪心算法
　　4.1 背包问题的贪心算法
　　4.2 求最小生成树的Kruskal算法
　　4.3 求最小生成树的Prim算法
　　4.4 求单源最短路的Dijkstra算法
　　4.5 哈夫曼编码
　　4.6 习题
　　第5章 动态规划算法
　　5.1 多段图问题
　　5.2 矩阵连乘积问题
　　5.3 0.1背包问题
　　5.4 旅行售货员问题
　　5.5 最长公共子序列问题
　　5.6 流水作业调度问题
　　5.7 资源分配问题
　　5.8 动态规划小结
　　5.9 习题
　　第6章 回溯算法
　　6.1 回溯算法的基本思想
　　6.2 旅行售货员问题
　　6.3 n后问题
　　6.4 图的m着色问题
　　6.5 0-1背包问题
　　6.6 批处理作业调度问题
　　6.7 哈密尔顿回路问题
　　6.8 子集和数问题
　　6.9 回溯法效率分析
　　6.10 习题
　　第7章 分支限界算法
　　7.1 基本思想
　　7.2 0-1背包问题
　　7.3 旅行售货员问题
　　7.4 任务分配问题
　　7.5 批处理作业调度问题
　　7.6 重排九宫问题
　　7.7 习题
　　第8章 NP-完全问题
　　8.1 图灵机——可计算性和计算复杂性的度量标准
　　8.1.1 确定的图灵机
　　8.1.2 图灵机用于计算整函数
　　8.1.3 多带图灵机
　　8.1.4 不确定的图灵机
　　8.1.5 图灵机的停机问题与可计算性度量
　　8.1.6 计算复杂性的度量
　　8.2 P类和NP类问题
　　8.2.1 P类问题的实例
　　8.2.2 NP类问题的实例
　　8.3 NP完全问题与Cook定理
　　8.3.1 多项式规约与NP完全问题的基本理论
　　8.3.2 Cook定理
　　8.3.3 其他NP完全问题
　　8.3.4 CO-NP问题与NPI问题
　　8.4 NP困难问题的近似算法和概率算法
　　8.4.1 近似算法
　　8.4.2 概率算法
　　8.5 习题
　　参考文献

　　吴哲辉，男，教授，博士生导师，中共党员。1941年生于广东省连县（现连州市）。1965年毕业于中山大学数学专业，1981年12月到1983年12月在美国芝加哥伊利诺大学作访问学者。现任山东科技大学信息科学与工程学院教授、博士生导师，中国科学院计算技术研究所兼职博士生导师，中国计算机学会理事，中国计算机学会petri网专业委员会主任。
　　主要研究领域有：petri网理论与并行分时系统、算法设计与分析、形式语言与自动机理论、密码学等。先后主持承担国家自然科学基金项目6项（从1987年到2004年，每3年1项）、山东省自然科学基金项目2项、煤炭科学基金项目2项；在《中国科学》、《科学通报》、《计算机学报》、《软件学报》等国内核心刊物，以及高校学报、国外刊物和国际学术会议发表学术论文90多篇，出版编、译著3部；获得过全国煤炭系统出国留学人员科研成果一等奖1项（独立）、国家教委科技进步三等奖1项（首位）、山东省科技进步二等奖1项（1项首位，1项第二位），山东省优秀教学成果一等奖1项（首位）、二等奖2项（均首位）。
　　1989年被评为全国优秀教师；1991年被评为全国有突出贡献的回国留学人员，并获得国务院颁发的政府特殊津贴；1992年被评为国家有突出贡献的中青年专家；1993年和1994年两度被评为山东省专业技术拔尖人才；1995年被评为山东省十大优秀教师；1998年被评为全国教育系统劳动模范，并被授予全国模范教师称号和奖章。

　　本书共分为8章。第1章介绍了算法的基本概念以及算法描述和算法分析的基本知识。第2章至第7章分别论述了分治与递归算法、散列与凝聚算法、贪心算法、动态规划算法、回溯算法和分支限界算法。在每一章的开头，都先对相应的典型算法的基本思路进行详细、清晰的阐述，然后通过多种实际问题的求解，对该典型算法的设计方法作进一步的剖析。第8章对NP完全问题的基本理论进行讨论，并介绍了求解NP困难问题的近似算法和概率算法。