內容簡介
《算法設計方法》共分為8章。第1章介紹了算法的基本概念以及算法描述和算法分析的基本知識。第2章至第7章分別論述了分治與遞歸算法、散列與凝聚算法、貪心算法、動態規划算法、回溯算法和分支限界算法。在每一章的開頭，都先對相應的典型算法的基本思路進行詳細、清晰的闡述，然後通過多種實際問題的求解，對該典型算法的設計方法作進一步的剖析。第8章對NP完全問題的基本理論進行討論，並介紹了求解NP困難問題的近似算法和機率算法。
作者簡介
吳哲輝，男，教授，博士生導師，中共黨員。1941年生於廣東省連縣（現連州市）。1965年畢業於中山大學數學專業，1981年12月到1983年12月在美國芝加哥伊利諾大學作訪問學者。現任山東科技大學信息科學與工程學院教授、博士生導師，中國科學院計算技術研究所兼職博士生導師，中國計算機學會理事，中國計算機學會petri網專業委員會主任。
主要研究領域有：petri網理論與並行分時系統、算法設計與分析、形式語言與自動機理論、密碼學等。先後主持承擔國家自然科學基金項目6項（從1987年到2004年，每3年1項）、山東省自然科學基金項目2項、煤炭科學基金項目2項；在《中國科學》、《科學通報》、《計算機學報》、《軟體學報》等國核心心刊物，以及高校學報、國外刊物和國際學術會議發表學術論文90多篇，出版編、譯著3部；獲得過全國煤炭系統出國留學人員科研成果一等獎1項（獨立）、國家教委科技進步三等獎1項（首位）、山東省科技進步二等獎1項（1項首位，1項第二位），山東省優秀教學成果一等獎1項（首位）、二等獎2項（均首位）。
1989年被評為全國優秀教師；1991年被評為全國有突出貢獻的回國留學人員，並獲得國務院頒發的政府特殊津貼；1992年被評為國家有突出貢獻的中青年專家；1993年和1994年兩度被評為山東省專業技術拔尖人才；1995年被評為山東省十大優秀教師；1998年被評為全國教育系統勞動模範，並被授予全國模範教師稱號和獎章。
目錄
第1章算法設計與分析概論1.1算法的定義和特徵
1.2算法的描述
1.3算法分析
1.4遞歸方程求解
1.4.1遞歸公式的展開
1.4.2常係數線性齊次遞歸方程的特徵方程求解方法
1.4.3常係數線性非齊次遞歸方程求解
1.5生成函式
1.6習題
2.1分治與遞歸算法的基本思路
2.2查找中的分治與遞歸算法
2.2.1二分查找算法
2.2.2二叉樹查找
2.2.3AVL樹
2.3排序問題的分治與遞歸算法
2.3.1合併排序
2.3.2快速排序
2.4矩陣乘法的strassen算法
2.5快速傅立葉變換
2.5.1離散傅立葉變換
2.5.2快速傅立葉變換算法
2.6減治與遞歸
2.7變治與遞歸
2.8習題
3.1散列算法
3.1.1散列查找算法
3.1.2桶排序算法
3.2矩陣乘法的凝聚算法
3.2.1非負整數矩陣乘法的凝聚算法
3.2.2矩陣乘法的凝聚算法的改進
3.2.3布爾矩陣乘法的凝聚算法
3.3非負整數向量卷積的凝聚算法
3.4習題
4.1背包問題的貪心算法
4.2求最小生成樹的kruskal算法
4.3求最小生成樹的Prim算法
4.4求單源最短路的Dijkstra算法
4.5哈夫曼編碼
4.6習題
5.1多段圖問題
5.2矩陣連乘積問題
5.30.1背包問題
5.4旅行售貨員問題
5.5最長公共子序列問題
5.6流水作業調度問題
5.7資源分配問題
5.8動態規劃小結
5.9習題
6.1回溯算法的基本思想
6.2旅行售貨員問題
6.3n後問題
6.4圖的m著色問題
6.50-1背包問題
6.6批處理作業調度問題
6.7哈密爾頓迴路問題
6.8子集和數問題
6.9回溯法效率分析
6.10習題
7.1基本思想
7.20-1背包問題
7.3旅行售貨員問題
7.4任務分配問題
7.5批處理作業調度問題
7.6重排九宮問題
7.7習題
8.1圖靈機--可計算性和計算複雜性的度量標準
8.1.1確定的圖靈機
8.1.2圖靈機用於計算整函式
8.1.3多帶圖靈機
8.1.4不確定的圖靈機
8.1.5圖靈機的停機問題與可計算性度量
8.1.6計算複雜性的度量
8.2P類和NP類問題
8.2.1P類問題的實例
8.2.2NP類問題的實例
8.3NP完全問題與Cook定理
8.3.1多項式規約與NP完全問題的基本理論
8.3.2Cook定理
8.3.3其他NP完全問題
8.3.4CO-NP問題與NPI問題
8.4NP困難問題的近似算法和機率算法
8.4.1近似算法
8.4.2機率算法
8.5習題
參考文獻
……
書摘
插圖1.1 算法的定義和特徵
通常的算法定義是：一個算法是求解某一類特定問題的一組有窮規則的集合。
首先，一個算法是一組規則，通常稱之為算法步驟，這組規則是有窮的，即能用有限的形式表示出來。其次，一個算法是針對一類問題而設計的。如果給出了求解某類問題的一個算法，那么對這類問題的任意一組（一個）初始數據，這個算法都有效的，也就是說，根據算法給出的求解步驟，都能求出這組初始數據所對應的計算結果。
