《计算的复杂性》

前言 王元1

第一章数值计算的复杂性问题1

1 代数方程的不动点迭代算法2

前言 王则柯3

2收敛性和复杂性——算法优劣判别的两个层次10

3 可怕的指数增长——古印度数学故事14

4 寻求多项式时间算法20

5 温故而创新的代数基本定理24

第二章库恩算法及其计算复杂性29

1 库恩算法的描述30

2 可行性和收敛性的论证37

3 全标三角形与根的距离42

4 积木结构的计算复杂性讨论46

第三章斯梅尔对牛倾算法的研究52

1 多项式求根的牛顿算法53

2 牛顿方法什么时候听话58

3 概率论定牛顿算法是多项式时间算法64

4 从最坏情形分析到概率情形分析70

5 算法之比较和配合74

第四章线性规划问题算法的竞争79

1 线性规划问题80

2 丹齐克的单纯形算法89

3 哈奇安的椭球算法94

4 卡马卡的内点算法99

5 斯梅尔论证了丹齐克的信念102

6 复杂性讨论的学科环境106

编后记 冯克勤110