算法设计方法
2008-10
机械工业出版社
吴哲辉 等 著
201
算法是计算机科学的核心内容之一，也是应用电子计算机求解实际问题的基础。对复杂的实际应用问题的求解，大多都归结为算法的设计，然后把求解算法转化为计算机程序。同算法设计密切相关的内容是算法分析，即算法的正确性证明和算法的时空复杂性分析。因此，国内外各高校都把算法设计与分析作为计算机专业的重要课程。 自20世纪七八十年代以来，国内一些高校先后编写和出版过多种算法设计与分析教材，同时也引进或翻译出版了一些国外的经典教材。就国内编写出版的教材而言，20世纪的教材大多从问题入手进行内容组织和处理，即在同一章中叙述一类问题的各种不同的算法设计方法。2l世纪的教材则大多从方法入手来进行内容的组织和处理，即在一章中介绍一种典型的算法设计方法，而把适用于该种算法设计方法的各类问题作为实例在同一章中分节阐述。从问题入手转化为从方法入手编写教材，是学科发展(求解问题类大量增加)的必然，也是知识分类和内容组织的一种进步。不过，有些教材虽然从方法入手分章编写，但叙述重点还是放在对各类问题的求解算法的详细描述上，而对算法的设计思想的阐述仍不够透彻、突出。对各类问题的求解算法的详细描述虽然便于学生把书本上给出的算法转化为计算机程序，但如果不能理解和掌握各种典型算法的基本思想，就难以对适用于同类算法设计方法的(书本上未讨论过的)问题进行算法设计。 我们认为，算法设计与分析这门课程的主要教学目标是让学生领会和掌握各种典型算法的基本设计思路。因此一方面，我们采用从方法入手来对课程内容进行组织和处理；另一方面，在讲述每一种典型的算法设计方法时，首先对这种典型算法的基本思路进行充分的阐述，然后把适用于该典型算法的各类问题作为实例分节阐述，对每一类实际问题都要把典型算法设计思路在该类问题求解中的具体体现作为重点内容，并对所设计出的算法给出时间复杂性分析。本教材共分为8章。第l章是算法设计与分析概论，介绍了算法描述和算法分析的基本方法。第2-7章是本书的主体部分，依次讨论了分治与递归算法、散列与凝聚算法、贪心算法、动态规划算法、回溯算法和分支限界算法等典型的算法设计方法。第8章对NP完全问题进行了讨论，并介绍了求解NP困难问题常用的近似算法和概率算法。全书的讲授约需72学时。如果在各种典型算法中挑选一些问题类让学生自学，也可以用60左右学时完成本书的教学。
本书共分为8章。第1章介绍了算法的基本概念以及算法描述和算法分析的基本知识。第2章至第7章分别论述了分治与递归算法、散列与凝聚算法、贪心算法、动态规划算法、回溯算法和分支限界算法。在每一章的开头，都先对相应的典型算法的基本思路进行详细、清晰的阐述，然后通过多种实际问题的求解，对该典型算法的设计方法作进一步的剖析。第8章对NP完全问题的基本理论进行讨论，并介绍了求解NP困难问题的近似算法和概率算法。
吴哲辉，男，教授，博士生导师，中共党员。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年被评为全国教育系统劳动模范，并被授予全国模范教师称号和奖章。
前言第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 习题参考文献
第1章 算法设计与分析概论 1.1 算法的定义和特征 通常的算法定义是：一个算法是求解某一类特定问题的一组有穷规则的集合。 首先，一个算法是一组规则，通常称之为算法步骤，这组规则是有穷的，即能用有限的形式表示出来。其次，一个算法是针对一类问题而设计的。如果给出了求解某类问题的一个算法，那么对这类问题的任意一组（一个）初始数据，这个算法都有效的，也就是说，根据算法给出的求解步骤，都能求出这组初始数据所对应的计算结果。
本书可作为计算机和相关专业的本科课程教材，也可作为科技人员的参考书。
