算法设计与分析(第3版在线教学版21世纪大学本科计算机专业系列教材)

本书为高等学校计算机 类专业核心课程“算法设计 与分析”教材，全书以算法 设计技术和分析方法为主线 来组织各知识单元，主要内 容包括基础知识、分治策略 、动态规划、贪心法、回溯 与分支限界、线性规划、网 络流算法、算法分析与问题 的计算复杂度、NP完全性 、近似算法、随机算法、处 理难解问题的策略等。力求 突出对问题本身的分析和求 解方法的阐述，从问题建模 、算法设计与分析、改进措 施等方面给出适当的建议， 同时也简要介绍了计算复杂 性理论的核心内容和处理难 解问题的一些新技术。 与本书配套的有习题解 答与学习指导用书、PPT电 子教案以及MOOC视频教学 资源等。 本书适合作为高等学校 计算机科学与技术、软件工 程、信息安全、信息与计算 科学等专业本科生和研究生 的教学用书，也可以作为从 事实际问题求解的算法设计 与分析工作的科技人员的参 考书。

王捍贫，博士，北京大学信息科学技术学院教授，博士生导师，软件研究所副所长，中国人工智能学会离散智能计算专委会主任。长期从事离散数学、形式化方法及算法设计与分析的教学和研究工作。主持完成多项国家研究课题，撰写和翻译多部离散数学和计算理论教材，曾获得北京市教学成果奖一等奖，系国家精品课“离散数学”课程主讲教师，国家级精品资源共享课“离散数学”课程主持人，“算法设计与分析”课程主讲教师。

第1章 基础知识 1.1 有关算法的基本概念 1.2 算法的伪码描述 1.3 算法的数学基础 1.3.1 函数的渐近的界 1.3.2 求和的方法 1.3.3 递推方程求解方法 习题1 第2章 分治策略 2.1 分治策略的基本思想 2.1.1 两个熟悉的例子 2.1.2 分治算法的一般性描述 2.2 分治算法的分析技术 2.3 改进分治算法的途径 2.3.1 通过代数变换减少子问题个数 2.3.2 利用预处理减少递归内部的计算量 2.4 典型实例 2.4.1 快速排序算法 2.4.2 选择问题 2.4.3 n-1次多项式在全体2n次方根上的求值 习题2 第3章 动态规划 3.1 动态规划的设计思想 3.1.1 多起点、多终点的最短路径问题 3.1.2 使用动态规划技术的必要条件 3.2 动态规划算法的设计要素 3.2.1 子问题的划分和递推方程 3.2.2 动态规划算法的递归实现 3.2.3 动态规划算法的迭代实现 3.2.4 一个简单实例的计算过程 3.3 动态规划算法的典型应用 3.3.1 投资问题 3.3.2 背包问题 3.3.3 最长公共子序列LCS 3.3.4 图像压缩 3.3.5 最大子段和 3.3.6 最优二分检索树 3.3.7 生物信息学中的动态规划算法 习题3 第4章 贪心法 4.1 贪心法的设计思想 4.2 关于贪心法的正确性证明 4.3 对贪心法得不到最优解情况的处理 4.4 贪心法的典型应用 4.4.1 最优前缀码 4.4.2 最小生成树 4.4.3 单源最短路径 习题4 第5章 回溯与分支限界 5.1 回溯算法的基本思想和适用条件