计算机常用算法（第二版）

第1章 算法及其基本设计方法                  
 1.1 算法的基本概念                  
 1.1.1 算法的一般特征                  
 1.1.2 数值型算法的特点                  
 1.2 算法描述语言                  
 1.3 算法的基本设计方法                  
 1.3.1 列举法                  
 1.3.2 归纳法                  
 1.3.3 速推                  
 1.3.4 速归                  
 1.3.5 减半递推                  
 1.3.6 回溯法                  
 1.3.7 数字模拟法                  
 1.3.8 数值法                  
 习题                  
 第2章 算法分析                  
 2.1 误差与运算误差分析                  
 2.1.1 误差的来源                  
 2.1.2 绝对误差与相对误差                  
 2.1.3 有效数字与对称舍入                  
 2.1.4 运算误差分析                  
 2.2 算法的稳定性                  
 2.2.1 算法稳定性的基本概念                  
 2.2.2 三项递推关系的稳定性分析                  
 2.3 算法的复杂度与最优性                  
 2.3.1 算法的时间复杂度                  
 2.3.2 算法的空间复杂度                  
 2.3.3 算法的最优性                  
 2.4 算法的自适应                  
 2.5 NP问题简介                  
 2.5.1 NP问题的概念                  
 2.5.2 近似算法与分析                  
 习题                  
 第3章 多项式                  
 3.1 多项式的基本概念                  
 3.2 多项式的欧几里得算法                  
 3.3 多项式的中国剩余定理                  
 3.4 多项式的快速求值                  
 3.4.1 多项式求值的秦九韶方法                  
 3.4.2 具有系数预处理的多项式求值                  
 3.5 切比雪夫正交多项式                  
 3.5.1 正交多项式的概念                  
 3.5.2 切比雪夫正交多项式                  
 3.5.3 切比雪夫正交多项式在近似计算中的应用                  
 习题                  
 第4章 矩阵与线性代教方程组                  
 4.1 线性代数方程组的直接解法                  
 4.1.1 高斯消去法                  
 4.1.2 选主元                  
 4.1.3 约当消去法                  
 4.2 三对角线线性代数方程组                  
 4.2.1 三对角矩阵的压缩                  
 4.2.2 追赶法                  
 4.3 一般带型线性代数方程组                  
 4.3.1 带型矩阵的压缩                  
 4.3.2 列选主元高斯消去法                  
 4.4 线性代数方程组的迭代解法                  
 4.4.1 简单迭代法                  
 4.4.2 赛德尔迭代法                  
 4.4.3 松弛法                  
 4.5 共轭梯度法                  
 4.5.1 对称正定矩阵. 向量的正交与共轭变换                  
 4.5.2 梯度法的基本思想                  
 4.5.3 共轭梯度法                  
 4.6 矩阵相乘的快速算法                  
 4.6.1 维诺格拉德方法                  
 4.6.2 斯特拉森方法                  
 4.7 矩阵分解                  
 4.7.1 矩阵的三角分解                  
 4.7.2 矩阵的QR分解                  
 4.8 矩阵求逆                  
 4.8.1 高斯-约当法                  
 4.8.2 全主元矩阵求逆                  
 习题                  
 第5章 矩阵特征值的计算                  
 5.1 计算绝对值最大的特征值的乘幂法                  
 5.2 求对称矩阵特征值的雅可比方法                  
 5.3 QR方法求实矩阵的全部特征值与多项式方程的全部根                  
 5.3.1 QR方法的基本思想                  
 5.3.2 化一般矩阵为上H矩阵                  
 5.3.3 QR方法求实矩阵的全部特征值                  
 5.3.4 QR方法求多项式方程的根                  
 习题                  
 第6章 非线性方程与方程组                  
 6.1 非线性方程求根的基本过程                  
 6.2 简单迭代法                  
 6.2.1 简单迭代法的迭代过程                  
 6.2.2 迭代过程的误差与收敛性                  
 6.2.3 埃特金迭代格式                  
 6.3 牛顿活与插值法                  
 6.3.1 牛顿迭代法                  
 6.3.2 插值法                  
 6.4 有记忆的单点迭代法                  
 6.5 对控制选代过程的讨论                  
 6.6 应用举例——非线性电路分析                  
 6.7 非线性方程组                  
 6.7.1 牛顿法                  
 6.7.2 拟牛顿法                  
 习题                  
 第7章 插值与逼近                  
 7.1 插值与逼近的基本概念                  
 7.2 拉格朗日插值法                  
 7.2.1 插值问题的提法                  
 7.2.2 拉格朗日插值多项式                  
 7.2.3 拉格朗日插值多项式的余项                  
 7.2.4 插值的逼近性质                  
 7.3 埃特金逐步插值法                  
 7.4 埃尔米特插值法                  
 7.5 样条插值法                  
 7.5.1 样条函数                  
 7.5.2 三次样条插值函数的构造                  
 7.6 离散点连成光滑曲线的阿克玛方法                  
 7.7 最佳均方逼近                  
 7.8 最佳一致逼近                  
 7.8.1 最佳一致逼近多项式                  
 7.8.2 里米兹算法                  
 7.9 曲线拟合的最小二乘法                  
 7.9.1 线性拟合                  
 7.9.2 一般多项式拟合                  
 7.9.3 利用正交多项式作最小二乘拟合                  
 习题                  
 第8章 数值微分与数值积分                  
 8.1 数值微分                  
 8.2 插值求积公式                  
 8.3 变步长梯形求积法                  
 8.4 龙贝格求积法                  
 8.5 高斯求积法                  
 8.5.1 代数精度的概念                  
 8.5.2 高斯求积公式                  
 8.6 自适应梯形求积法                  
 8.7 高振荡函数的求积法                  
 8.7.1 问题的提出                  
 8.7.2 分部积分法                  
 8.7.3 利用样条函数计算高振荡积分                  
 习题                  
 第9章 常微分方程初值问题的数值解法                  
 9.1 数值解法的基本思想与途径                  
 9.2 欧拉方法                  
 9.2.1 基本公式                  
 9.2.2 欧拉公式的几何解释                  
 9.2.3 欧拉方法的误差分析                  
 9.2.4 改进的欧拉公式                  
 9.3 龙格-库塔法                  
 9.3.1 问题的提出                  
 9.3.2 龙格-库塔法                  
 9.3.3 步长的自动选择                  
 9.3.4 求解一阶微分方程组的龙格-库塔法                  
 9.3.5 求解高阶微分方程的龙格-库塔法                  
 9.4 阿当姆斯预报-校正公式                  
 9.5 哈明方法                  
 9.6 常微分方程数值解法的相容性. 收敛性与稳定性                  
 9.6.1 相容性                  
 9.6.2 收敛性                  
 9.6.3 稳定性                  
 9.7 求解刚性方程的吉尔方法                  
 习题                  
 第10章 连分式及其计算法                  
 10.1 连分式                  
 10.1.1 连分式的基本概念                  
 10.1.2 连分式的主要性质                  
 10.2 函数连分式                  
 10.2.1 函数连分式的基本概念                  
 10.2.2 函数连分式的主要性质                  
 10.2.3 函数连分式的计算                  
 10.3 变换级数为连分式                  
 10.4 连分式插值法                  
 10.4.1 连分式插值的基本概念                  
 10.4.2 连分式插值函数的构造                  
 10.4.3 连分式逐步插值                  
 10.5 非线性方程的连分式解法                  
 10.6 利用连分式计算一维积分                  
 10.7 常微分方程初值问题的连分式解法                  
 习题                  
 第11章 数字信号处理中的快速算法                  
 11.1 数字信号处理                  
 11.2 快速傅里叶变换                  
 11.2.1 离散傅里叶变换                  
 11.2.2 单位根的性质                  
 11.2.3 快速傅里叶变换（FFT）                  
 11.3 循环卷积与线性卷积                  
 11.3.1 循环卷积                  
 11.3.2 利用FFT计算循环卷积                  
 11.3.3 线性卷积                  
 11.4 多项式的快速乘法                  
 11.4.1 多项式相乘与卷积的关系                  
 11.4.2 多项式相乘的快速算法                  
 11.5 短序列卷积的快速算法                  
 11.5.1 维诺格拉德短序列卷积算法                  
 11.5.2 短序列线性卷积快速算法的设计                  
 11.5.3 短序列循环卷积快速算法的设计                  
 11.6 滤波算法                  
 11.6.1 逐段卷积                  
 11.6.2 短序列滤波段快速算法的设计                  
 11.6.3 滤波段的速归算法                  
 11.7 解托伯利兹系统的快速算法                  
 11.7.1 托伯利兹矩阵快速求逆的特兰持算法                  
 11.7.2 解托伯利兹型线性代数方程组的列文松算法                  
 11.8 快速沃什变换                  
 11.8.1 沃什函数                  
 11.8.2 快速沃什变换（FWT）                  
 习题                  
 第12章 非数值问题的常用算法                  
 12.1 数据结构                  
 12.1.1 线性表                  
 12.1.2 栈和队列                  
 12.1.3 二叉树                  
 12.2 寻找最大项和次大项                  
 12.3 有序表的对分查找和分块查找                  
 12.3.1 对分查找法                  
 12.3.2 分块查找                  
 12.4 树表的查找                  
 12.4.1 二叉排序树及其构造                  
 12.4.2 二叉排序树的查找                  
 12.4.3 平衡二叉排序树                  
 12.5 字符串匹配的KMP算法                  
 12.5.1 字符串匹配的简单算法                  
 12.5.2 有限自动机                  
 12.5.3 KMP算法                  
 12.6 冒泡排序与快速排序                  
 12.6.1 冒泡排序                  
 12.6.2 快速排序                  
 12.7 希尔排序                  
 12.8 堆排序                  
 习题                  
 参考书目                  
 附录 短序列循环卷积算法