算法设计与分析

第1章 算法概述

1.1 算法的概念

1.1.1 算法与程序

1.1.2 算法与数据结构

1.1.3 算法表示的基本方法

1.1.4 算法设计

1.2 算法复杂性分析的方法

1.2.1 两个算法的效率对比

1.2.2 算法复杂性的度量

1.2.3 复杂性的渐近性态及其阶

1.2.4 复杂性渐近阶的重要性

1.2.5 递归方程解的渐近阶的求法

小结

习题

第2章 分治与递归

2.1 递归概述

2.2 分治法概述

2.3 分治法的应用

2.3.1 排队购票问题

2.3.2 整数划分问题

2.3.3 "放苹果问题

2.3.4

第后选择问题

2.4 典型问题分析

2.4.1 红与黑

2.4.2 循环赛日程表

2.4.3 0／1背包问题

2.5 递归和递推

2.5.1 递归和递推的比较

2.5.2 "最少汽油过沙漠问题

2.5.3 整数划分递推设计

2.6 递归的消除

小结

习题

第3章 贪心算法

3.1 贪心算法概述

3.2 活动安排问题

3.3 背包问题

3.4 贪心算法的两个基本要素

3.4.1 贪心选择性质

3.4.2 最优子结构性质

3.5 典型问题分析

3.5.1 最优装载问题

3.5.2 删数问题

3.5.3 均分纸牌

3.5.4 拦截导弹问题

小结

习题

第4章 动态规划

4.1 矩阵连乘问题

4.2 凸多边形最优三角剖分

4.3 最长公共子序列

4.4 DNA序列比对

4.5 0／1背包问题

4.6 多段图问题

4.7 数字三角形问题

4.8 备忘录方法

4.9 典型问题分析

4.9.1 游船费问题

4.9.2 航线设置

4.9.3 复制书稿

4.9.4 括号序列

小结

习题

第5章 搜索算法

5.1 问题解空间的分析

5.1.1 两种常见的树形问题解空间

5.1.2 解空间的两种搜索方式

5.2 回溯法概述

5.3 分支限界法概述

5.4 装载问题

5.4.1 回溯法解装载问题

5.4.2 分支限界法解装载问题

5.5 0／1背包问题

5.5.1 回溯法解0／1背包问题

5.5.2 分支限界法解0／1背包问题

5.6 旅行售货员问题

5.6.1 回溯法解旅行售货员问题

5.6.2 分支限界法解旅行售货员问题

5.7 典型问题分析

5.7.1 子集和问题

5.7.2 油田勘探问题

小结

习题

第6章 网络流和匹配

6.1 最大流问题

6.1.1 概念

6.1.2 基本定理

6.1.3 求最大流的标号法

6.2 最小费用流问题

6.3 匹配

6.3.1 二部图

6.3.2 匹配

6.4 典型问题分析

6.4.1 物流运输

6.4.2 电力网络

6.4.3 选择课程

6.4.4 小行星

小结

习题

第7章 线性规划

7.1 线性规划问题及其表示

7.2 线性规划问题的数学形式

7.3 一般问题转化为约束标准型

7.4 线性规划的基、基础可行解

7.5 单纯形法算法

7.5.1 用消元法描述单纯形法算法

7.5.2 单纯形算法的框架

7.6 线性规划应用

小结

习题

参考文献

《高等学校“十二五”规划教材·计算机软件工程系列：算法设计与分析》为大学计算机相关专业核心课程——“算法设计与分析”教材。全书以算法设计策略为知识单元，系统介绍算法设计方法与分析技巧，主要内容包括：算法概述、分治与递归、贪心算法、动态规划、搜索算法、网络流和匹配、线性规划。在介绍每一种方法时，阐述了它的应用背景，并注意与其他方法的比较。
《高等学校“十二五”规划教材·计算机软件工程系列：算法设计与分析》结构简明、内容丰富，为突出教材的可读性和可用性，章内设有典型例题分析，章末配有难易适度的习题，有利于读者对相关内容的理解。本书适合于作为大学计算机科学与技术专业、软件工程专业及相关专业本科生和研究生教材，也适合广大工程技术人员学习参考。