算法设计与分析

出版时间：2007-6  出版社：武汉大学  作者：夏红霞  页数：344  

内容概要

　　本书作为普通高等学校计算机与信息安全专业本科生的教材，根据国内外计算机技术的最新发展，阐述计算机算法的各种设计策略、算法分析和一些经典及应用问题的算法。　　全书共11章，第1章介绍算法引论；第2章阐述了排序算法；第3章介绍了分治算法；第4章介绍了图的搜索算法；第5章介绍了贪心算法；第6章介绍了动态规划算法；第7章介绍了分支限界法；第8章介绍了并行算法；第9 章介绍了NP-完全问题；第10章介绍了近似算法；第11章介绍了概率算法。　　本书是一本注重系统性、科学性的教材，内容丰富、理论性强，可作为计算机与信息安全专业及其他相关专业的本科教材，也可作为计算机及信息安全领域软件开发人员的技术参考书。

书籍目录

第1章 算法引论1.1 算法1.2 算法描述1.2.1 算法描述约定1.2.2 一个简单问题的求解过程1.3 算法分析基础1.3.1 算法分析的评估体系1.3.2 算法的时间复杂度1.3.3 算法的空间复杂度1.3.4 NP-完全问题1.4 基本数据结构1.4.1 栈和队列1.4.2 树1.4.3 图1.5 迭代法1.5.1 递推法1.5.2 倒推法1.5.3 迭代法解方程1.6 递归和消除递归1.6.1 递归1.6.2 消除递归本章小结习题1第2章 排序算法2.1 排序2.1.1 排序问题2.1.2 冒泡问题2.1.3 交换排序2.1.4 选择排序2.1.5 插入排序2.2 堆排序2.2.1 堆2.2.2 建堆2.2.3 堆排序算法2.2.4 堆排序的应用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 基数排序2.4.4 桶排序2.5 中数排序2.5.1 最大和最小元素2.5.2 一般选择问题本章小结习题2第3章 分治法3.1 一般算法3.2 二分检索3.3 找最大值和最小值3.4 归并分类3.4.1 基本方法3.4.2 改进的归并算法3.5 快速分类3.5.1 快速分类算法3.5.2 快速分类分析3.6 选择问题3.6.1 选择问题算法3.6.2 SELECT2实现本章小结习题3第4章 图的搜索算法4.1 图的基本概念4.1.1 图的定义4.1.2 图的基本术语4.2 图的检索与遍历4.2.1 广度优先检索与遍历4.2.2 深度优先检索与遍历4.3 回溯法4.3.1 回溯法的一般方法4.3.2 回溯算法的抽象描述4.3.3 n-皇后问题4.3.4 子集和数问题4.3.5 0/1背包问题4.3.6 图的m-着色问题4.3.7 哈密顿环4.3.8 连续邮资问题4.3.9 回溯法的效率估计本章小结习题4第5章 贪心算法5.1 算法概述5.1.1贪心选择性质5.1.2 最优子结构性质5.1.3活动安排问题5.2 背包问题5.3 带有限期的作业排序5.3.1 带有限期的作业排序算法5.3.2 改进的带有限期的作业排序算法5.4 最优归并模式5.5 哈夫曼编码5.5.1 前缀码5.5.2 哈夫曼编码5.6 最小生成树5.6.1 Prim算法5.6.2 Kruskal算法5.7 单源点最短路径本章小结习题5第6章 动态规划算法6.1 一般方法6.2 多段图6.3 每对结点之间的最短路径6.4 最优二分检索树6.5 0/1背包问题6.5.1 0/1背包问题实现的实例分析6.5.2 DKP的实现6.5.3 过程DKNAP的分析6.6 可靠性设计6.7 货郎担问题6.8 流水线调度问题本章小结习题6第7章 分支限界法7.1 一般方法7.1.1 FIFO和LIFO-检索7.1.2 LC-检索7.1.3 LC-检索的抽象化描述7.1.4 分支限界法解最优化问题7.2 0/1背包问题7.2.1 LC-分支限界求解7.2.2 FIFO –分支限界求解7.3 货郎担问题7.4 效率分析本章小结习题7第8章 并行算法8.1 并行计算机及并行模型8.1.1 并行计算机8.1.2 并行计算模型8.1.3 并行计算机网络8.1.4 并行算法的一般术语8.2 SIMD共享存储模型的并行算法8.2.1 播送算法8.2.2 求和算法8.2.3 并行k-选择算法8.2.4 并行桶排序算法8.2.5 有序表搜索并行算法8.3 SIMD互联网络模型的并行算法8.3.1 网孔上的随机序列搜索算法8.3.2 树机上的矩阵和向量乘法8.3.3 一维线性陈列上的奇偶转置排序算法8.3.4 树机上求最小值算法8.3.5 树机上的连通分量算法8.4 MIMD共享存储模型的并行算法8.4.1 异步枚举排序算法8.4.2 单源点最短路径并行算法8.4.3 最小生成树并行算法8.4.4 Gauss-Seidel算法8.4.5 牛顿求根并行算法8.5 MIMD异步通信模型的并行算法8.5.1 快速排序并行算法8.5.2 二维网孔上的矩阵转置并行算法8.5.3 矩阵并行分块乘法算法8.5.4 分布式矩阵求逆的并行算法8.5.5 分布式高斯消去并行算法本章小结习题8第9章 NP-完全问题9.1 计算模型9.1.1 有限自动机9.1.2 下推自动机9.1.3 图灵机9.2 P类与NP类问题9.2.1 多项式时间界9.2.2 P类问题9.2.3 NP类问题9.3 NP-完全问题9.3.1 判定NP-完全问题的关键概念9.3.2 NP-完全性9.3.3 Cook定理9.4 典型的NP-完全问题9.4.1 NP-完全性的证明方法9.4.2 典型的NP-完全问题9.4.3 NP-完全问题的计算机实现本章小结习题9第10章 近似算法10.1 近似算法的性能10.2 启发式算法10.2.1 图着色问题10.2.2 旅行商问题10.3 任务安排的近似算法10.4 覆盖问题的近似算法10.4.1 顶点覆盖问题的近似算法10.4.2 集合覆盖问题的近似算法10.5 旅行售货员问题近似算法10.5.1 具有三角不等式的旅行售货员问题10.5.2 一般旅行售货员问题10.6 背包问题10.7 子集合问题的近似算法10.7.1 解子集合问题的指数时间算法10.7.2 子集合问题的完全多项式时间近似格式本章小结习题10第11章 概率算法11.1 概率算法概述11.2 伪随机数11.3 数值概率算法11.3.1 用随机投点法计算圆周率值11.3.2 计算定积分11.3.3 解非线性方程组11.4 Sherwood算法11.4.1 线性时间选择算法11.4.2 搜索有序表11.4.3 跳跃表11.5 Las Vegas算法11.5.1 n后问题11.5.2 整数因子分解11.6 Monte Carlo算法11.6.1 Monte Carlo算法的基本思想11.6.2 主元素问题11.6.3 素数性测试本章小结习题11主要参考文献

编辑推荐

这是一本注重系统性、科学性的教材，内容丰富，理论性强。根据国内外计算机技术的最新发展，阐述计算机算法的各种设计策略、算法分析和一些经典及应用问题的算法。本书可作为普通高等学校计算机与信息安全专业本科生教材。

用户评论 (总计1条)

•   用的是pascal语言描述的,看起来不是太习惯.但只要有其它语言基础,就能看的懂的.