第1部分基 本 算 法

第1章数学准备

11母函数

12递推关系

13Fibonacci 数列

131Fibonacci 数列是典型的递推关系

132问题的解

14线性常系数递推关系举例

15其他类型的递推关系举例

习题

第2章优先策略与分治策略

21优先策略：求最短树的 Kruskal 算法

22求最短树的 Prim 算法

23求最短路径的 Dijkstra 算法

24文件存储问题

25有期限的任务安排问题

26数据压缩和 Huffman 树

27分治策略与二分查找

28整数乘法

29矩阵乘积的 Strassen 算法

210矩阵乘积的Winograd算法

211布尔矩阵乘积的分段预处理方法

212归并排序法

213快速排序法

214求序列中的第k个元素

习题

第3章动态规划

31最短路径问题

32最佳原理

33流动推销员问题

331算法及例题

332复杂性估计

34矩阵链乘问题

35最长公共子序列

36图的任意两点间的最短距离

37同顺序流水作业的任务安排问题

38可靠性问题

39最佳二分树

391二分树的一些性质

392最佳二分树的构成

习题

第4章概率算法

41生日问题

42概率算法举例

43随机数的产生器

431线性同余式法

432离散对数法

433BBS法

434素数法

44素数的概率判定算法

441关于素数的若干定理

442Fermat数

443MillerRabin的素数概率测试法

45定理证明的数学准备

451数论的基本知识

452群论的基本知识

453中国剩余定理

454xn≡1 mod p 的解

46定理A的证明

47定理B的证明

习题

第5章并行算法

51并行计算机和并行算法的基本概念

52递推关系的并行计算

53图的并行算法举例

54矩阵乘积的并行计算

55分布计算

56快速傅里叶变换

561FFT问题的背景

562预备定理

563快速算法

564傅里叶逆变换

565计算结果的重排

566复杂性估计

57卷积及其应用

571卷积

572多项式的一种快速乘法

58数论变换

59排序网络

591引论

59201原理

593Bn 型网络

594Mn 归并网络

510Batcher 奇偶归并网络

511脉动阵列的并行处理

5111矩阵和向量乘法的并行处理

5112矩阵乘法的并行处理

5113带状矩阵的并行乘法

习题

第6章搜索法

61引论

62DFS 搜索法

63无向图的 DFS 算法

64有向图的 DFS 算法

65互通块问题

66强连通块问题

67BFS 算法

68拓扑排序

69minmax 搜索法

610流动推销员问题的分支定界法

611同顺序加工任务安排问题

习题

第7章数据结构

71“堆”和“堆集排序法”

711堆

712堆集排序法

713优先级队和二进制堆

7223树

73234树

74红黑树

741RB树性质

742插入

743删除

75B树

751B树性质

752B树的插入

753B树的删除

76关于高度的均衡树

761AVL树——关于高度均衡的二分树

762关于高度均衡的二分树的插入和删除

77哈希表

771什么是哈希表

772哈希函数的构造方法

773解决冲突的方法

774哈希算法的分析(线性探测法分析)

775二重哈希法

习题

第2部分若 干 专 题

第8章排序算法

81排序

82下界估计

83二分插入排序法

84下溢排序法

85FordJohnson 归并插入排序法

851算法的非形式化描述

852一般情形的讨论

853算法分析

86外存排序

861外存归并排序法

862三条带的外存归并排序法

863阶式归并法

第9章计算几何及计算数论

91关于线段问题

92凸包问题与Voronoi问题

921凸包问题

922Voronoi图

923Voronoi图的构造法

924Voronoi图的应用简介

925Voronoi图的拓广

93串匹配

931搜索法

932KMP 算法

933BM 算法

934RK 算法

94数论的算法问题

941求最大公因数

942因数分解之一： Pollard ρ法

943Dixon 随机平方因数分解法

944椭圆曲线因数分解法

95大数模幂运算

951常规算法

96N mod M

961Barrett归约

962模乘算法

963Montgomery 模幂运算

964n是偶数的情况

第10章线性规划

101问题的提出

102线性规划的几何意义

103单纯形法理论基础

104单纯形法及单纯形表格

105改善的单纯形法表格

106对偶原理

1061对偶概念

1062对偶问题的经济意义

1063对偶问题的性质

1064对偶定理

1065影子价格

107对偶单纯形法

108退化情况及其他

1081退化情况

1082退化情况的循环不已与Bland 法则

109DantzigWolfe 分解算法

1010整数规划

10101问题的提出

1010201 规划和DFS 搜索法

10103分支定界法

1011Klee 与 Minty举例

第3部分复杂性理论与智能型算法

第11章算法复杂性理论

111图灵机

112图灵机和算法

113k 条带的图灵机

114非确定型图灵机

115停机问题

116布尔表达式

117布尔变量和网络

118问题的转换

119Cook 定理

1110几个 NP 完备的例子

1111复杂度类

1112近似解法

11121任务安排的近似算法

11122装箱问题的近似算法

11123流动推销员问题的近似算法

11124顶点覆盖问题的近似算法

1113近代密码学简介

11131密码概念

11132背包公钥密码

11133RSA 公钥密码

第12章智能型算法

121遗传算法

122什么是遗传算法

123TSP 问题

1231编码

1232初始“种群”的生成

1233杂交

1234变异算术

1235模式定理

124模拟退火算法简介

习题