Fundamentals of Algorithmics

第1章 预备知识

1.1 简介

1.2 什么是算法

1.3 程序符号

1.4 数学符号

1.4.1 命题演算

1.4.2 集合论

1.4.3 整数、实数和区间

1.4.4 函数和关系

1.4.5 量词

1.4.6 累加与累积

1.4.7 杂项

1.5 证明技巧1——反证法

1.6 证明技巧2——数学归纳法

1.6.1 数学归纳法的法则

1.6.2 不同颜色的马

1.6.3 一般化的数学归纳法

1.6.4 构造性归纳

1.7 一些回顾

1.7.1 极限

.1.7.2 简单级数

1.7.3 基本组合

1.7.4 概率基础

1.8 习题

1.9 参考与深入阅读

第2章 基本算法

2.1 简介

2.2 问题和实例

2.3 算法的效率

2.4 平均和最坏情况分析

2.5 什么是基本运算？

2.6 为什么寻求效率？

2.7 一些例子

2.7.1 计算行列式的值

2.7.2 排序

2.7.3 大整数的乘法

2.7.4 计算最大公约数

2.7.5 计算斐波纳契序列

2.7.6 傅立叶变换

2.8 什么时候算法是确定的？

2.9 习题58

2.10 参考与深入阅读

第3章 渐近记法

3.1 引言

3.2 同阶记法

3.3 其他渐近记法

3.3.1 ω记法

3.3.2 θ记法

3.4 条件渐近记法

3.5 具有多个参数的渐近记法

3.6 渐近记法的操作

3.7 习题

3.8 参考与深入阅读

第4章 算法分析

4.1 引言

4.2 分析控制结构

4.2.1 先后顺序

4.2.2 for循环

4.2.3 递归调用

4.2.4 while和repeat循环

4.3 使用标称

4.4 补充例子

4.4.1 选择排序

4.4.2 插入排序

4.4.3 欧几里德算法

4.4.4 汉诺塔

4.4.5 计算行列式的值

4.5 平均情况分析

4.6 分期分析

4.6.1 势函数

4.6.2 账户戏法

4.7 求解递归式

4.7.1 推测

4.7.2 齐次递归式

4.7.3 非齐次递归式

4.7.4 变量变换

4.7.5 范围转换

4.7.6 渐近递归式

4.8 习题

4.9 参考与深入阅读

第5章 一些数据结构

5.1 数组、栈和队列

5.2 记录和指针

5.3 链表

5.4 图

5.5 树

5.6 关联表

5.7 堆

5.8 二项堆

5.9 不相交集结构

5.10 习题

5.11 参考与深入阅读

第6章 贪婪算法

6.1 找零钱(1)

6.2 贪婪算法的一般特性

6.3 图：最小生成树

6.3.1 kruskal算法

6.3.2 prim算法

6.4 图：最短路径

6.5 背包问题(1)

6.6 日程安排

6.6.1 最小化时间

6.6.2有期限的日程安排

6.7 习题

6.8 参考与深入阅读

第7章 分治算法

7.1 简介：大整数乘法

7.2 通用模板

7.3 二分搜索

7.4 排序

7.4.1 归并排序

7.4.2 快速排序

7.5 查找中值

7. 6矩阵乘法

7.7 求幂

7.8 综合：密码学简介

7.9 习题

7.10 参考与深入阅读

第8章 动态规划

8.1 两个简单的例子

8.1.1 计算二项式系数

8.1.2 系列赛

8.2 找零钱(2)

8.3 最优性原则

8.4 背包问题(2)

8.5 最短路径

8.6 链式矩阵乘法

8.7 使用递归

8.8 存储函数

8.9 习题

8.10 参考与深入阅读

第9章 搜索图

9.1 图和游戏：简介

9.2 遍历树

9.2.1 预处理

9.3 深度优先搜索：无向图

9.3.1 关节点

9.4 深度优先搜索：有向图

9.4.1 无环图：拓扑排序

9.5 广度优先搜索

9.6 回溯法

9.6.1 背包问题(3)

9.6.2 八皇后问题

9.6.3 通用模板

9.7 分支界限

9.7.1 分配任务问题

9.7.2 背包问题(4)

9.7.3 一般考虑

9.8 极小化原则

9.9 习题

9.10 参考与深入阅读

第10章 概率算法

10.1 简介

10.2 概率不意味着不确定

10.3 预期与平均时间

10.4 生成伪随机数

10.5 数值概率算法

10.5.1 buffon的针

10.5.2 数值积分

10.5.3 概率计数

10.6 monte carlo算法

10.6.1 验证矩阵乘法

10.6.2 素数性测试

10.6.3 一个数可能是素数吗？

10.6.4 随机优势的扩大

10.7 las vegas算法

10.7.1 重访八皇后问题

10.7.2 概率选择与排序

10.7.3 通用散列

10.7.4 大整数分解因数

10.8 习题

10.9 参考与深入阅读

第11章 并行算法

11.1 并行计算的模型

11.2 一些基本的技术

11.2.1 计算完全二叉树

11.2.2 指针倍增

11.3 工作量与效率

11.4 图论的两个例子

11.4.1 最短路径

11.4.2 连通分量

11.5 表达式的并行求值

11.6 并行排序网络

11.6.1 0-1原理

11.6.2 并行合并网络

11.6.3 改进的排序网络

11.7 并行排序

11.7.1 预备工作

11.7.2 核心思想

11.7.3 算法

11.7.4 细节概述

11.8 erew和crcw pram的一些注意点

11.9 分布式计算

11.10 习题

11.11 参考与深入阅读

第12章 计算复杂性

12.1 引言：一个简单的例子

12.2 信息怖砺勐壑

12.2.1 排序的复杂性

12.2.2 复杂性对算法设计的帮助

12.3 对手论证

12.3.1 查找数组的最大项

12.3.2 测试图的连通性

12.3.3 中值再考察

12.4 线性归约

12.4.1 形式定义

12.4.2 矩阵问题中的归约

12.4.3 最短路径问题中的归约

12.5 np完全性介绍

12.5.1 p和np类

12.5.2 多项式归约

12.5.3 np完全性问题

12.5.4 一些np完全性证明

12.5.5 np难问题

12.5.6 非确定性算法

12.6 复杂性类纵览

12.7 习题

12.8 参考与深入阅读

第13章 启发式和近似算法

13.1 启发式算法

13.1.1 图着色

13.1.2 旅行商

13.2 近似算法

13.2.1 度量旅行商

13.2.2 背包问题（5）

13.2.3 装箱问题

13.3 np难近似问题

13.3.1 绝对难近似问题

13.3.2 相对难近似问题

13.4 相同，惟一不同

13.5 近似模式

13.5.1 重访装箱问题

13.5.2 背包问题（6）

13.6 习题

13.7 参考与深入阅读

参考文献