計算機常用算法（第二版）

第1章 算法及其基本設計方法                  
 1.1 算法的基本概念                  
 1.1.1 算法的一般特征                  
 1.1.2 數(shù)值型算法的特點                  
 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 數(shù)字模擬法                  
 1.3.8 數(shù)值法                  
 習題                  
 第2章 算法分析                  
 2.1 誤差與運算誤差分析                  
 2.1.1 誤差的來源                  
 2.1.2 絕對誤差與相對誤差                  
 2.1.3 有效數(shù)字與對稱舍入                  
 2.1.4 運算誤差分析                  
 2.2 算法的穩(wěn)定性                  
 2.2.1 算法穩(wěn)定性的基本概念                  
 2.2.2 三項遞推關(guān)系的穩(wěn)定性分析                  
 2.3 算法的復雜度與最優(yōu)性                  
 2.3.1 算法的時間復雜度                  
 2.3.2 算法的空間復雜度                  
 2.3.3 算法的最優(yōu)性                  
 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 具有系數(shù)預處理的多項式求值                  
 3.5 切比雪夫正交多項式                  
 3.5.1 正交多項式的概念                  
 3.5.2 切比雪夫正交多項式                  
 3.5.3 切比雪夫正交多項式在近似計算中的應用                  
 習題                  
 第4章 矩陣與線性代教方程組                  
 4.1 線性代數(shù)方程組的直接解法                  
 4.1.1 高斯消去法                  
 4.1.2 選主元                  
 4.1.3 約當消去法                  
 4.2 三對角線線性代數(shù)方程組                  
 4.2.1 三對角矩陣的壓縮                  
 4.2.2 追趕法                  
 4.3 一般帶型線性代數(shù)方程組                  
 4.3.1 帶型矩陣的壓縮                  
 4.3.2 列選主元高斯消去法                  
 4.4 線性代數(shù)方程組的迭代解法                  
 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 插值的逼近性質(zhì)                  
 7.3 埃特金逐步插值法                  
 7.4 埃爾米特插值法                  
 7.5 樣條插值法                  
 7.5.1 樣條函數(shù)                  
 7.5.2 三次樣條插值函數(shù)的構(gòu)造                  
 7.6 離散點連成光滑曲線的阿克瑪方法                  
 7.7 最佳均方逼近                  
 7.8 最佳一致逼近                  
 7.8.1 最佳一致逼近多項式                  
 7.8.2 里米茲算法                  
 7.9 曲線擬合的最小二乘法                  
 7.9.1 線性擬合                  
 7.9.2 一般多項式擬合                  
 7.9.3 利用正交多項式作最小二乘擬合                  
 習題                  
 第8章 數(shù)值微分與數(shù)值積分                  
 8.1 數(shù)值微分                  
 8.2 插值求積公式                  
 8.3 變步長梯形求積法                  
 8.4 龍貝格求積法                  
 8.5 高斯求積法                  
 8.5.1 代數(shù)精度的概念                  
 8.5.2 高斯求積公式                  
 8.6 自適應梯形求積法                  
 8.7 高振蕩函數(shù)的求積法                  
 8.7.1 問題的提出                  
 8.7.2 分部積分法                  
 8.7.3 利用樣條函數(shù)計算高振蕩積分                  
 習題                  
 第9章 常微分方程初值問題的數(shù)值解法                  
 9.1 數(shù)值解法的基本思想與途徑                  
 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 常微分方程數(shù)值解法的相容性. 收斂性與穩(wěn)定性                  
 9.6.1 相容性                  
 9.6.2 收斂性                  
 9.6.3 穩(wěn)定性                  
 9.7 求解剛性方程的吉爾方法                  
 習題                  
 第10章 連分式及其計算法                  
 10.1 連分式                  
 10.1.1 連分式的基本概念                  
 10.1.2 連分式的主要性質(zhì)                  
 10.2 函數(shù)連分式                  
 10.2.1 函數(shù)連分式的基本概念                  
 10.2.2 函數(shù)連分式的主要性質(zhì)                  
 10.2.3 函數(shù)連分式的計算                  
 10.3 變換級數(shù)為連分式                  
 10.4 連分式插值法                  
 10.4.1 連分式插值的基本概念                  
 10.4.2 連分式插值函數(shù)的構(gòu)造                  
 10.4.3 連分式逐步插值                  
 10.5 非線性方程的連分式解法                  
 10.6 利用連分式計算一維積分                  
 10.7 常微分方程初值問題的連分式解法                  
 習題                  
 第11章 數(shù)字信號處理中的快速算法                  
 11.1 數(shù)字信號處理                  
 11.2 快速傅里葉變換                  
 11.2.1 離散傅里葉變換                  
 11.2.2 單位根的性質(zhì)                  
 11.2.3 快速傅里葉變換（FFT）                  
 11.3 循環(huán)卷積與線性卷積                  
 11.3.1 循環(huán)卷積                  
 11.3.2 利用FFT計算循環(huán)卷積                  
 11.3.3 線性卷積                  
 11.4 多項式的快速乘法                  
 11.4.1 多項式相乘與卷積的關(guān)系                  
 11.4.2 多項式相乘的快速算法                  
 11.5 短序列卷積的快速算法                  
 11.5.1 維諾格拉德短序列卷積算法                  
 11.5.2 短序列線性卷積快速算法的設計                  
 11.5.3 短序列循環(huán)卷積快速算法的設計                  
 11.6 濾波算法                  
 11.6.1 逐段卷積                  
 11.6.2 短序列濾波段快速算法的設計                  
 11.6.3 濾波段的速歸算法                  
 11.7 解托伯利茲系統(tǒng)的快速算法                  
 11.7.1 托伯利茲矩陣快速求逆的特蘭持算法                  
 11.7.2 解托伯利茲型線性代數(shù)方程組的列文松算法                  
 11.8 快速沃什變換                  
 11.8.1 沃什函數(shù)                  
 11.8.2 快速沃什變換（FWT）                  
 習題                  
 第12章 非數(shù)值問題的常用算法                  
 12.1 數(shù)據(jù)結(jié)構(gòu)                  
 12.1.1 線性表                  
 12.1.2 棧和隊列                  
 12.1.3 二叉樹                  
 12.2 尋找最大項和次大項                  
 12.3 有序表的對分查找和分塊查找                  
 12.3.1 對分查找法                  
 12.3.2 分塊查找                  
 12.4 樹表的查找                  
 12.4.1 二叉排序樹及其構(gòu)造                  
 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 堆排序                  
 習題                  
 參考書目                  
 附錄 短序列循環(huán)卷積算法