普通高等学校计算机科学与技术专业（本科）新编系列教材：算法设计与分析

　　1 引论
　　1.1 什么是算法
　　1.2 分析算法的准则
　　1.3 描述算法的语言和基本的数据结构
　　思考题与习题
　　2 分治与递归
　　2.1 折半查找
　　2.2 搜索二叉排序树
　　2.2.1 二叉排序树的定义
　　2.2.2 搜索二叉排序树
　　2.2.3 向二叉排序树中插入新结点
　　2.2.4 从二叉排序树中删除一个结点
　　2.2.5 平衡的二叉排序树
　　2.3 快速排序
　　2.4 归并排序
　　2.5 大整数乘法
　　2.6 矩阵乘积的Strassen算法
　　思考题与习题
　　3 贪心算法
　　3.1 最小生成树
　　3.2 单源最短路径
　　3.3 旅行商问题
　　思考题与习题
　　4 动态规划
　　4.1 动态规划在最短路径中的应用
　　4.2 矩阵连乘积问题
　　4.3 求最长公共子序列
　　4.4 凸多边形的最优三角形剖分
　　4.5 旅行商问题
　　思考题与习题
　　5 回溯法
　　5.1 树的深度优先遍历
　　5.2 数的全排列
　　5.3 八皇后问题
　　5.4 0-1背包问题
　　5.5 旅行商问题
　　思考题与习题
　　6 分支限界法
　　6.1 最小耗费搜索
　　6.2 背包问题
　　6.3 旅行商问题
　　思考题与习题
　　7 字符串
　　7.1 串概念及简单串匹配算法
　　7.1.1 字符串的概念
　　7.1.2 串的匹配
　　7.1.3 简单串模式匹配算法
　　7.2 Knuth-Morris-Pratt（KMP）算法
　　7.2.1 KMP算法
　　7.2.2 改进的KMP算法
　　7.3 Boyer.Moore算法
　　7.3.1 Boyer-Moore算法
　　7.4 Karp-Rabin串匹配随机算法
　　思考题与习题
　　8 NP完全问题与近似算法
　　8.1 确定型图灵机
　　8.2 非确定型图灵机
　　8.3 Cook定理和NP完全理论
　　8.3.1 NP完全理论
　　8.3.2 Cook定理
　　8.3.3 若干NP完全问题
　　8.4 。NP完全问题的近似算法
　　8.4.1 0-1背包问题
　　8.4.2 旅行商问题
　　思考题与习题
　　9 概率算法
　　9.1 随机抽样
　　9.2 判定素数的概率算法
　　9.2.1 Fermat素数测试法
　　9.2.2 MiLler-Rabin素数判定概率算法
　　思考题与习题
　　10 数据压缩算法
　　10.1.ASCII码压缩算法
　　10.2 哈夫曼编码
　　10.3 字典法
　　10.4 LZ算法
　　10.4.1 LZ77算法
　　10.4.2 LZ78算法
　　10.4.3 LZW算法
　　思考题与习题
　　11 公钥密码学基础
　　11.1 公钥密码体制的应用与基本思想
　　11.2 背包公钥密码
　　11.3 RSA公钥密码体制
　　10.4 数字签名和Hash算法
　　思考题与习题
　　参考文献

　　算法的基本概念及相关基本知识；常用的一些非数值算法的设计方法（分治法、贪心法、动态规划法、回溯法和分支限界法）；字符串的匹配算法；NP完全问题的近似算法；概念算法；目前常见的通用型数据压缩算法；公钥密码学的基础。
　　《算法设计与分析》可作为计算机科学与技术专业的本科生教材；也可供有关计算机工作者阅读。