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