大学算法教程

本书是美国德保罗大学(DePaul University)教授R.Johnsonbaugh等人长期从事算法课程教学经验的结晶，是一本关于算法基础知识和基本方法的教科书。内容包括：算法必备的数学基础、数据结构和描述算法的语言与记号；常用算法的设计分析及其正确性证明；NP和NP完全问题的特征及其近似处理方法。 全书含300多个生动有趣的算法实际示例和1450多道习题，从经典方法到最新成果，层层剖析、逐步深入。根据相关方法的重要程度，详简适度地作了富有启发性的介绍和论证。 本书可以作为大学计算机科学技术及相关专业本科生和研究生算法课程的教材，也可作为高职相关专业教学的参考用书。

第1章 引言 1.1 算法 1.2 表述算法的伪代码 1.3 现状 1.4 未来发展 备考 本章习题 第2章 算法涉及的基本数学概念 2.1 定义、记号和基本结论 2.2 数学归纳法 2.3 算法分析 2.4 递推关系 2.5 图 2.6 树 备考 本章习题 第3章 数据结构 3.1 抽象数据类型 3.2 堆栈和队列 3.3 链接表 3.4 二叉树 3.5 优先队列，二分堆阵，堆阵排序 3.6 不相交集 备考 本章习题 第4章 搜索 4.1 对分搜索 4.2 深度优先搜索 4.3 广度优先搜索 4.4 拓扑排序 4.5 回溯法 备考 本章习题 第5章 分而治之 5.1 平铺问题 5.2 归并排序 5.3 寻找最近点对 5.4 Strassen的矩阵乘法算法 备考 本章习题 第6章 排序和选择 6.1 插入排序 6.2 快速排序 6.3 排序问题的下界 6.4 计数排序和基数排序 6.5 选择 备考 本章习题 第7章 贪心算法 7.1 硬币兑换 7.2 kruskal算法 7.3 Prim算法 7.4 Dijkstra算法 7.5 霍夫曼编码 7.6 连续背包问题 备考 本章习题 第8章 动态规划算法 8.1 计算斐波那契数列 8.2 硬币兑换问题再探讨 8.3 矩阵乘法 8.4 最长公共子串问题 8.5 Floyd算法和Warshall算法 备考 本章习题 第9章 文本搜索 9.1 简单的文本搜索 9.2 Rabin-Karp算法 9.3 Knuth-Morris-Pratt算法 9.4 Boyrer-Moore-Horspool算法 9.5 近似模式匹配 9.6 正则表达式匹配 备考 本章习题 第10章 P和NP问题 10.1 多项式时间 10.2 不确定算法和NP 10.3 可归约性和NP完全性 10.4 NP完全性问题 1O.5 NP完全性进一步探讨 备考 本章习题 第11章 NP完全性问题的处理 11.1 蛮干法 11.2 随机方法 11.3 近似方法 11.4 参数化方法 11.5 启发式搜索 备考 本章习题 第12章 并行和分布算法 12.1 引言 12.2 并行随机存取机器(PRAM) 12.3 排序网络 12.4 并行体系结构 12.5 分布式算法 备考 本章习题 参考文献 习题选解