算法设计与分析

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

屈婉玲，北京大学信息科学技术学院教授，博士生导师，长期从事离散数学、算法分析和计算复杂性等方向的教学和研究工作。参与完成多项国家研究课题，撰写多部教材、教学参考书与译著，其中包括国家规划教材、北京市精品教材、教育部高等教育精品教材等，曾获得北京市教学成果奖一等奖，被评为北京大学靠前教师和北京市很好教师，系国家精品课“离散数学”课程主持人，“算法设计与分析”课程主讲教师。
刘田，博士，北京大学信息科学技术学院副教授，中国电子学会电路与系统分会图论与系统优化专委会副理事长，中国计算机学会理论计算机科学专委会委员，主要从事算法分析与计算复杂度方面的研究和教学工作，翻译多部国外有名离散数学和计算理论教材，系国家精品课“离散数学”课程主讲教师，“算法设计与分析”课程主讲教师。本书的编写得到国家自然科学基金（61370052）的资助。
张立昂，北京大学信息科学技术学院教授，博士生导师，一直从事数学和理论计算机科学的教学与研究工作，主要研究方向是计算复杂性理论和算法设计与分析，撰写多部教材、教学参考书与译著，其中包括国家规划教材、北京市精品教材、教育部高等教育精品教材等，曾获得北京市教学成果奖一等奖和教育部科技进步二等奖。 

第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.3n—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回溯算法的基本思想和适用条件
5.1.1几个典型的例子
5.1.2回溯算法的适用条件
5.2回溯算法的设计步骤
5.2.1回溯算法的递归实现和迭代实现
5.2.2几个典型的例子
5.3回溯算法的效率估计和改进途径
5.4分支限界
5.4.1背包问题
5.4.2最大团问题
5.4.3货郎问题
5.4.4圆排列问题
5.4.5连续邮资问题
习题5
第6章线性规划
6.1线性规划模型
6.1.1模型
6.1.2二维线性规划的图解法
6.2标准形
6.2.1标准形基本概念
6.2.2标准形的可行解的性质
6.3单纯形法
6.3.1确定初始基本可行解
6.3.2最优性检验
6.3.3基变换
6.3.4单纯形表
6.3.5人工变量和两阶段法
6.3.6单纯形法的有限终止
6.4对偶性
6.4.1对偶线性规划
6.4.2对偶单纯形法
6.5整数线性规划的分支限界算法
习题6
第7章网络流算法
7.1最大流问题
7.1.1网络流及其性质
7.1.2Ford—Fulkerson算法
7.1.3Dinic有效算法
7.2最小费用流
7.2.1Floyd算法
7.2.2最小费用流的负回路算法
7.2.3最小费用流的最短路径算法
7.3运输问题
7.3.1确定初始调运方案
7.3.2改进调运方案
7.3.3表上作业法
7.4二部图匹配
7.4.1二部图的最大匹配
7.4.2赋权二部图的匹配
习题7
第8章算法分析与问题的计算复杂度
8.1平凡下界
8.2直接计数求解该问题所需要的最少运算
8.3决策树
8.4检索算法的时间复杂度分析
8.5排序算法的时间复杂度分析
8.5.1冒泡排序算法
8.5.2堆排序算法
8.5.3排序算法的决策树与算法类时间复杂度的下界
8.6选择算法的时间复杂度分析
8.6.1找最大和最小问题
8.6.2找第二大问题
8.6.3找中位数的问题
8.7通过归约确认问题计算复杂度的下界
习题8
第9章NP完全性
9.1P类与NP类
9.1.1易解的问题与难解的问题
9.1.2判定问题
9.1.3NP类
9.2多项式时间变换与NP完全性
9.2.1多项式时间变换
9.2.2NP完全性及其性质
9.2.3Cook—Levin定理——第一个NP完全问题
9.3几个NP完全问题
9.3.1最大可满足性与三元可满足性
9.3.2顶点覆盖、团与独立集
9.3.3哈密顿回路与货郎问题
9.3.4恰好覆盖
9.3.5子集和、背包、装箱与双机调度
9.3.6整数线性规划
习题9
第10章近似算法
10.1近似算法及其近似比
10.2多机调度问题
10.2.1贪心的近似算法
10.2.2改进的贪心近似算法
10.3货郎问题
10.3.1最邻近法
10.3.2最小生成树法
10.3.3最小权匹配法
10.4背包问题
10.4.1一个简单的贪心算法
10.4.2多项式时间近似方案
10.4.3伪多项式时间算法与完全多项式时间近似方案
习题10
第11章随机算法
第12章处理难解问题的策略
参考文献