《21世紀高等學校規劃教材·計算機科學與技術：算法設計與分析》是普通本科高校計算機專業核心課程“算法設計與分析”的教材。本著“易理解，重實用”的指導思想，結合多年的教學經驗，以算法設計策略為主線，沿著“算法思想—算法設計—構造實例—算法描述—算法分析”的思路來組織教材內，系統介紹了算法的設計方法和分析技巧。主要內容包括：算法及基礎知識、貪心法、分治法、動態規劃、搜索法、隨機化算法、線性規劃問題與網絡流、數論算法及計算幾何算法和NP完全理論。為突出教材的可讀性、可用性及前沿性，每章增設了教學目標、閱讀材料及習題解析。
《21世紀高等學校規劃教材·計算機科學與技術：算法設計與分析》內容豐富、思路清晰、實例講解詳細、圖例直觀形象，適合作為計算機及其相關專業的本科生教材，也可供工程技術人員和自學讀者學習參考。此外，也適合作為參加ACM程序設計大賽的愛好者的參考書或培訓教材。
《21世紀高等學校規劃教材·計算機科學與技術：算法設計與分析》側重于算法步驟的設計及實例構造，注重算法與數據結構的結合、算法時間效率分析。其特色在于針對每一種算法設計策略，按照算法思想設計了詳細的算法步驟，構造了具體實例以展現算法的詳細演示過程，最后給出算法描述。《21世紀高等學校規劃教材·計算機科學與技術：算法設計與分析》內容精練，算法設計步驟清晰，實例構造詳盡，算法描述的注釋清楚，閱讀材料豐富，易教、易學。
一、 關于本書
本書是在結合作者多年教學經驗及實踐的基礎上編寫而成的。它充分考慮了學生的接受能力，本著“易理解，重實用”的指導思想，以掌握算法設計與分析的基本概念和方法、拓展學生專業知識結構為宗旨，按照“算法思想→算法設計→構造實例→算法描述→算法分析”的思路來組織本書內容，詳細講述了多種經典算法設計策略。縱觀全書，這里并沒有創造出任何新的算法，因為作者僅僅是希望通過對經典算法的講解，把算法設計與分析中基礎且重要的內容用更清晰的思路、更直觀的形式展現給讀者。
二、 本書結構
本書以算法策略為知識單元，共9章內容，其中第1章介紹基礎知識，第2~8章介紹經典的算法設計策略，第9章簡單介紹了NP完全理論。具體結構安排如下：
第1章： 算法及基礎知識。主要介紹算法設計與分析的基礎知識、遞歸、常用的數據結構及數學公式等。
第2~5章介紹經典的算法設計策略： 貪心法、分治法、動態規劃、搜索法等。每一種算法設計策略均按照算法思想、算法設計、構造實例、算法描述、算法分析的思路詳細講解。
第6章： 隨機化算法。講述了4種類型的隨機化算法，并結合實例講述了每種類型隨機化算法的特點。
第7章： 線性規劃問題與網絡流。著重講述線性規劃問題的標準化及單純形算法、網絡流的基本概念及理論、求最大流的增廣路算法、求最小費用流的消圈算法。
第8章： 數論算法及計算幾何算法。數論算法中介紹了一些簡單的數論理論知識及最大公約數、一次同余方程和同余方程組的算法； 計算幾何算法中主要介紹叉積的概念和幾何意義，進而利用它判斷點與線段、線段與線段之間的關系； 解決凸包問題及最接近點對問題的兩種算法的實現與比較。
第9章： NP完全理論。簡單介紹了NP理論和近似算法，以引起讀者進一步學習和研究的興趣。
其中，第5、6、8章由南陽理工學院王秋芬編寫，第1、2、3、7章由南陽理工學院呂聰穎編寫，第4、9章由南陽理工學院徐艷群編寫，習題解析的第1~4章由呂聰穎編寫，第5~9章由王秋芬編寫,吉林大學周春光教授負責全書的審閱工作。
三、 本書特點
本書側重于算法步驟的設計及實例構造，注重算法與數據結構的結合、算法時間效率分析。其特色在于針對每一種算法設計策略，按照算法思想設計了詳細的算法步驟，構造了具體實例以展現算法的詳細演示過程，最后給出算法描述。
本書內容精練，算法設計步驟清晰，實例構造詳盡，算法描述的注釋清楚，閱讀材料豐富，易教、易學。通過本書，讀者一方面可以學習到基本的算法設計策略和分析方法； 另一方面，還可以對當今流行算法和算法界的大師有所了解。
在此，謹向清華大學出版社負責本書編輯出版工作的全體同仁和每一位曾經關心和支持本書編寫工作的各方面專家表示衷心感謝。
由于編者水平有限，書稿雖幾經修改，仍難免有疏漏或不妥之處，歡迎廣大讀者和專家批評指正。
編者
2011年6月
第1章 算法及基礎知識
1.1 算法的基本概念
1.1.1 學習算法的重要性
1.1.2 算法的定義及特性
1.1.3 算法的描述方式
1.1.4 算法與程序的區別
1.2 算法設計的一般過程
1.3 算法分析
1.3.1 算法分析的概念
1.3.2 時間復雜性
1.3.3 空間復雜性
1.3.4 漸進復雜性態
1.3.5 算法復雜性的權衡考慮
1.4 遞歸
1.4.1 認知遞歸
1.4.2 n的階乘
1.4.3 排列問題
1.4.4 遞歸算法的復雜性分析
1.5 基本的數據結構
1.5.1 順序表與鏈表
1.5.2 棧與隊列
1.5.3 樹與圖
1.5.4 集合
1.6常用數學公式
1.6.1 對數公式
1.6.2 組合公式
1.6.3 求和公式
1.6.4 向下取整和向上取整公式
閱讀材料1--算法界十大名師簡介
習題1
第2章 貪心法
2.1 概述
2.1.1 貪心法的基本思想
2.1.2 貪心法的基本要素
2.1.3 貪心法的解題步驟及算法設計模式
2.2 會場安排問題
2.3 單源最短路徑問題
2.4 哈夫曼編碼
2.5 最小生成樹
2.5.1 Prim算法
2.5.2 Kruskal算法
2.5.3 兩種算法的比較
閱讀材料2--遺傳算法
習題2
第3章 分治法
3.1 概述
3.1.1 分治法的基本思想
3.1.2 分治法的求解步驟
3.2 二分查找
3.3 循環賽日程表
3.4 合并排序
3.5 快速排序
閱讀材料3--禁忌搜索算法
習題3
第4章 動態規劃
4.1 概述
4.1.1 動態規劃的基本思想
4.1.2 動態規劃的求解步驟
4.1.3 動態規劃的基本要素
4.2 矩陣連乘問題
4.3 凸多邊形最優三角剖分
4.4 最長公共子序列問題
4.5 加工順序問題
4.6 0-1背包問題
4.7最優二叉查找樹
閱讀材料4--模擬退火算法
習題4
第5章 搜索法
5.1 窮舉搜索
5.2 深度優先搜索
5.3 回溯法
5.3.1 回溯法的算法框架及思想
5.3.2 子集樹
5.3.3 排列樹
5.3.4 滿m叉樹
5.4 寬度優先搜索
5.5 分支限界法
5.5.1 分支限界法的基本思想
5.5.2 0-1背包問題
5.5.3 旅行商問題
5.5.4 布線問題
5.5.5 分支限界法與回溯法的比較
閱讀材料5--蟻群算法
習題5
第6章 隨機化算法
6.1 概述
6.1.1 隨機化算法的類型及特點
6.1.2 隨機數發生器
6.2 數值隨機化算法
6.2.1 計算π的值
6.2.2 計算定積分
6.3 蒙特卡羅算法
6.3.1 主元素問題
6.3.2 素數測試
6.4 拉斯維加斯算法
6.4.1 整數因子分解
6.4.2 n皇后問題
6.5 舍伍德算法
6.5.1 隨機快速排序
6.5.2 線性時間選擇
閱讀材料6--粒子群優化算法
習題6
第7章 線性規劃問題與網絡流
7.1 概述
7.1.1 一般線性規劃問題的描述
7.1.2 標準型線性規劃問題的描述
7.1.3 標準型線性規劃問題的單純形算法
7.2 最大網絡流
7.2.1 基本概念
7.2.2 增廣路算法
7.2.3 最大網絡流的變換與應用
7.3 最小費用最大流
7.3.1 基本概念
7.3.2 消圈算法
7.3.3 最小費用最大流的變換與應用
閱讀材料7--捕食搜索算法
習題7
第8章 數論算法及計算幾何算法
8.1 最大公約數
8.1.1 歐幾里得算法
8.1.2 Stein算法
8.2 同余方程
8.3 同余方程組
8.4 線段相交
8.5 凸包問題
8.5.1 凸包問題的窮舉搜索法
8.5.2 凸包問題的分治法
8.6 最接近點對問題
8.6.1 最接近點對問題的窮舉搜索法
8.6.2 最接近點對問題的分治法
閱讀材料8--動態進化算法
習題8
第9章 NP完全理論
9.1 易解問題和難解問題
9.2 P類和NP類問題
9.2.1 P類問題
9.2.2 NP類問題
9.2.3 P類問題和NP類問題的關系
9.3 NP完全問題
9.3.1 多項式變換技術
9.3.2 典型的NP完全問題
9.4 NP完全問題的近似算法
9.4.1 頂點覆蓋問題
9.4.2 裝箱問題
9.4.3 旅行商問題TSP
9.4.4 集合覆蓋問題
閱讀材料9--DNA計算
習題9
附錄A 習題解析
第1章
第2章
第3章
第4章
第5章
第6章
第7章
第8章
第9章
參考文獻
新書資訊