本书不仅讲解传统的算法设计策略和技巧，而且关注算法领域不断涌现的新概念、新方法和新应用，帮助读者把握技术热点及发展趋势。书中引入了降维技术、并行算法、随机算法、层次化存储结构算法和流算法等新内容，大量使用了概率分析和随机化技术，并包含众多新颖的示例，特别是强调计算模型和计算环境，不再局限于理想化的随机存取机模型。全书内容简洁明快，并配有丰富的习题和拓展阅读资料，适合作为高等院校计算机相关专业的教材，也适合业界技术人员阅读参考。

刘铎，1978年9月生，北京人，2006年于清华大学计算机科学与技术系获工学博士学位，现为北京交通大学软件学院副教授，校级优秀主讲教师。主要研究方向为应用密码学、信息安全、组合算法的设计与分析。主持和参加国家级、省部级科研项目多项，作为第一作者在各类重要刊物和会议上发表论文二十余篇，目前主要承担“离散数学”“算法设计与实践”“信息安全理论与实践”等课程的教学与建设，作为课题执行负责人完成了北京交通大学多项教学改革项目。获得多项教学类成果奖，主持建设的“离散数学”课程成为2014年北京交通大学优质课程建设项目、国家示范性软件学院联盟第一批慕课课程建设项目等。

出版者的话
译者序
前言
致谢
第1章 模型与分析
1.1 计算斐波那契数
1.2 快速乘法
1.3 计算模型
1.4 随机算法简介
1.4.1 另一种随机算法
1.5 其他计算模型
1.5.1 外部存储器模型
1.5.2 并行模型
拓展阅读
习题
第2章 概率基础与尾部不等式
2.1 概率基础
2.2 尾部不等式
2.3 生成随机数
2.3.1 生成具有任意分布的随机变量
2.3.2 由顺序文件生成随机变量
2.3.3 生成随机置换
拓展阅读
习题
第3章 热身问题
3.1 计算最大公因子的欧几里得算法
3.1.1 扩展欧几里得算法
3.1.2 在密码学中的应用
3.2 寻找第k小的元素
3.2.1 选择随机的划分元
3.2.2 中位数的中位数
3.3 词的排序
3.4 可归并的堆
3.4.1 归并二项堆
3.5 一个简单的半动态词典
3.5.1 势能法与平摊分析
3.6 下界
拓展阅读
习题
第4章 优化I：蛮力法与贪婪策略
4.1 启发式搜索方法
4.1.1 博弈树
4.2 贪婪算法的框架
4.2.1 最大支撑树
4.2.2 寻找最小权值子集
4.2.3 一个调度问题
4.3 最小支撑树算法的高效数据结构
4.3.1 并查集的一种简单数据结构
4.3.2 更快的方案
4.3.3 增长最慢的函数
4.3.4 整合
4.3.5 仅做道路压缩
4.4 其他不同形式的贪婪策略
4.5 与贪婪策略的折中
4.6 梯度下降
4.6.1 应用
拓展阅读
习题
第5章 优化Ⅱ：动态规划
5.1 背包问题
5.2 上下文无关文法的解析
……
第6章 查找
第7章 多维查找与几何算法
第8章 字符串匹配与指纹函数
第9章 快速傅里叶变换及其应用
第10章 图算法
第11章 最大流及其应用
第12章 NP完全性与近似算法
第13章 降维
第14章 并行算法
第15章 层次化存储结构及高速缓存
第16章 流数据模型
附录A 递推关系与生成函数
参考文献