算法分析与设计及案例教程(计算机科学与技术21世纪高等学校规划教材)

师智斌、靳雁霞、井超、梁志剑、雷海卫编著的 《算法分析与设计及案例教程》介绍了算法的概念， 算法分析的基本理论、过程和方法以及算法设计的基 本策略。主要内容包括 算法概述、算法效率分析基础、蛮力法、分治法、分 治策略变体——减治策略和变治策略、动态规划、时 空权 衡技术、贪心算法、回溯法和分支限界法、NP完全性 理论等。本书最后对ACM竞赛精选案例进行了分析 和讲解，书中既有新创趣题，也有经典名题，难度适 宜，使读者能够沿着一条清晰的、一致的、连贯的思 路来 探索算法设计与分析这一领域。 本书内容丰富，逻辑性强，既注重理论知识，又 强调工程实用，既可以作为高等院校计算机及相关专 业 本科生、研究生“算法分析与设计”课程的教材，也 可以作为广大计算机工程与应用行业的读者的参考书 。 此外，本书还可以作为参加ACM程序设计大赛的爱好 者的参考书或培训教材。

第1章 绪论 1.1 什么是算法 1.1.1 算法的由来 1.1.2 算法的发展 1.1.3 算法的例子 1.2 重要的问题类型 1.2.1 排序 1.2.2 查找 1.2.3 字符串匹配 1.2.4 图问题 1.2.5 组合问题 1.2.6 几何问题 1.2.7 数值问题 1.3 基本数据结构 1.3.1 线性结构 1.3.2 树结构 1.3.3 图结构 1.3.4 集合 1.3.5 数据的物理结构 1.4 算法问题求解基础 1.4.1 算法求解框架 1.4.2 算法设计步骤 1.5 算法的表示 1.6 为什么学习算法 总结 习题1 第2章 算法效率分析基础 2.1 算法分析框架 2.1.1 算法分析概述 2.1.2 算法正确性分析 2.1.3 时空效率分析 2.1.4 算法分析过程 2.2 渐进符号和基本效率类型 2.2.1 三种渐进符号 2.2.2 渐进符号的特性 2.2.3 基本效率类型 2.3 非递归算法的数学分析方法 2.4 递归算法的数学分析 2.4.1 递归算法的数学分析方法 2.4.2 斐波那契数列 2.5 算法的其他分析方法 总结 习题2 第3章 蛮力法 3.1 概述 3.2 排序问题 3.2.1 选择排序 3.2.2 冒泡排序 3.3 查找问题 3.3.1 顺序查找 3.3.2 字符串匹配 3.4 几何问题 3.4.1 最近对问题 3.4.2 凸包问题 3.5 组合问题 3.5.1 旅行商问题 3.5.2 背包问题 总结 习题3 第4章 分治法 4.1 概述 4.2 分治法的基本策略及步骤 4.2.1 分治法的基本策略 4.2.2 分治法的基本步骤 4.3 排序问题 4.3.1 合并排序 4.3.2 快速排序 4.4 查找问题 4.4.1 折半查找 4.4.2 二叉树遍历及其相关特性 4.5 数值计算问题 4.5.1 大整数乘法 4.5.2 Strassen矩阵乘法 4.6 几何问题 4.6.1 用分治法解最近对问题 4.6.2 用分治法解凸包问题 4.7 分析分治法在安排循环赛中的应用 总结 习题4 第5章 分治策略变体——减治策略和变治策略 5.1 减治策略 5.1.1 插入排序 5.1.2 拓扑排序 5.1.3 生成组合对象的算法 5.1.4 减常因子算法 5.1.5 减可变规模算法 5.2 变治策略 5.2.1 排序问题 5.2.2 平衡查找树 5.2.3 霍纳法则和二进制幂 5.2.4 问题化简 总结 习题5 第6章 动态规划 6.1 概述 6.2 算法特点 6.2.1 备忘录方法 6.2.2 最优化原理 6.2.3 求解步骤 6.3 矩阵连乘问题 6.4 最长公共子序列 6.5 0-1背包问题 6.6 最大子段和 6.7 最优二叉查找树 总结 习题6 第7章 时空权衡技术 7.1 时空权衡策略 7.2 计数排序 7.3 字符串匹配 7.4 散列法 总结 习题7 第8章 贪心算法 8.1 概述 8.1.1 贪心算法的基本要素 8.1.2 贪心算法的求解过程 8.2 活动安排问题 8.3 背包问题 8.4 最小生成树问题 8.4.1 Prim算法 8.4.2 Kruskal算法 8.5 单源(点)最短路径问题 8.6 哈夫曼编码 总结 习题8 第9章 回溯法和分支限界法 9.1 回溯法 9.1.1 概述 9.1.2 子集和问题 9.1.3 n皇后问题 9.1.4 哈密顿回路 9.1.5 装载问题 9.2 分支限界法 9.2.1 概述 9.2.2 0-1背包问题 9.2.3 任务分配问题 9.2.4 多段图的最短路径问题 9.2.5 旅行商问题 总结 习题9 第10章 NP完全性理论 10.1 判定问题和最优化问题 10.2 P类问题 10.3 NP类问题 10.4 NP完全问题 10.5 典型的NP完全问题 10.6 其他NP完全问题 10.7 NP完全问题的计算机处理 总结 习题10 第11章 案例精选 11.1 果园篱笆问题 11.2 空中飞行管理问题 11.3 去数问题 11.4 极差问题 11.5 最优合并问题 11.6 在棋盘中实现从初始布局到目标布局的转变 11.7 商店购物问题 11.8 旅游预算问题 11.9 防卫导弹问题 11.10 钓鱼问题 11.11 胖男孩问题 11.12 护卫队问题 参考文献