算法設(shè)計(jì)方法圖書目錄

算法設(shè)計(jì)方法第1章

算法設(shè)計(jì)與分析概論

1.1算法的定義和特征

1.2算法的描述

1.3算法分析

1.4遞歸方程求解

1.4.1遞歸公式的展開

1.4.2常系數(shù)線性齊次遞歸方程的特征方程求解方法

1.4.3常系數(shù)線性非齊次遞歸方程求解

1.5生成函數(shù)

1.6習(xí)題

算法設(shè)計(jì)方法第2章

分治與遞歸算法

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習(xí)題

算法設(shè)計(jì)方法第3章

散列與凝聚算法

3.1散列算法

3.1.1散列查找算法

3.1.2桶排序算法

3.2矩陣乘法的凝聚算法

3.2.1非負(fù)整數(shù)矩陣乘法的凝聚算法

3.2.2矩陣乘法的凝聚算法的改進(jìn)

3.2.3布爾矩陣乘法的凝聚算法

3.3非負(fù)整數(shù)向量卷積的凝聚算法

3.4習(xí)題

算法設(shè)計(jì)方法第4章

貪心算法

4.1背包問題的貪心算法

4.2求最小生成樹的Kruskal算法

4.3求最小生成樹的Prim算法

4.4求單源最短路的Dijkstra算法

4.5哈夫曼編碼

4.6習(xí)題

算法設(shè)計(jì)方法第5章

動(dòng)態(tài)規(guī)劃算法

5.1多段圖問題

5.2矩陣連乘積問題

5.30.1背包問題

5.4旅行售貨員問題

5.5最長公共子序列問題

5.6流水作業(yè)調(diào)度問題

5.7資源分配問題

5.8動(dòng)態(tài)規(guī)劃小結(jié)

5.9習(xí)題

算法設(shè)計(jì)方法第6章

回溯算法

6.1回溯算法的基本思想

6.2旅行售貨員問題

6.3n后問題

6.4圖的m著色問題

6.50-1背包問題

6.6批處理作業(yè)調(diào)度問題

6.7哈密爾頓回路問題

6.8子集和數(shù)問題

6.9回溯法效率分析

6.10習(xí)題

算法設(shè)計(jì)方法第7章

分支限界算法

7.1基本思想

7.20-1背包問題

7.3旅行售貨員問題

7.4任務(wù)分配問題

7.5批處理作業(yè)調(diào)度問題

7.6重排九宮問題

7.7習(xí)題

算法設(shè)計(jì)方法第8章

NP-完全問題

8.1圖靈機(jī)--可計(jì)算性和計(jì)算復(fù)雜性的度量標(biāo)準(zhǔn)

8.1.1確定的圖靈機(jī)

8.1.2圖靈機(jī)用于計(jì)算整函數(shù)

8.1.3多帶圖靈機(jī)

8.1.4不確定的圖靈機(jī)

8.1.5圖靈機(jī)的停機(jī)問題與可計(jì)算性度量

8.1.6計(jì)算復(fù)雜性的度量

8.2P類和NP類問題

8.2.1P類問題的實(shí)例

8.2.2NP類問題的實(shí)例

8.3NP完全問題與Cook定理

8.3.1多項(xiàng)式規(guī)約與NP完全問題的基本理論

8.3.2Cook定理

8.3.3其他NP完全問題

8.3.4CO-NP問題與NPI問題

8.4NP困難問題的近似算法和概率算法

8.4.1近似算法

8.4.2概率算法

8.5習(xí)題

2100433B

算法設(shè)計(jì)方法內(nèi)容簡介

《算法設(shè)計(jì)方法》共分為8章。第1章介紹了算法的基本概念以及算法描述和算法分析的基本知識。第2章至第7章分別論述了分治與遞歸算法、散列與凝聚算法、貪心算法、動(dòng)態(tài)規(guī)劃算法、回溯算法和分支限界算法。在每一章的開頭，都先對相應(yīng)的典型算法的基本思路進(jìn)行詳細(xì)、清晰的闡述，然后通過多種實(shí)際問題的求解，對該典型算法的設(shè)計(jì)方法作進(jìn)一步的剖析。第8章對NP完全問題的基本理論進(jìn)行討論，并介紹了求解NP困難問題的近似算法和概率算法。

算法設(shè)計(jì)方法作者簡介

吳哲輝，男，教授，博士生導(dǎo)師，中共黨員。1941年生于廣東省連縣（現(xiàn)連州市）。1965年畢業(yè)于中山大學(xué)數(shù)學(xué)專業(yè)，1981年12月到1983年12月在美國芝加哥伊利諾大學(xué)作訪問學(xué)者?，F(xiàn)任山東科技大學(xué)信息科學(xué)與工程學(xué)院教授、博士生導(dǎo)師，中國科學(xué)院計(jì)算技術(shù)研究所兼職博士生導(dǎo)師，中國計(jì)算機(jī)學(xué)會理事，中國計(jì)算機(jī)學(xué)會petri網(wǎng)專業(yè)委員會主任。

主要研究領(lǐng)域有：petri網(wǎng)理論與并行分時(shí)系統(tǒng)、算法設(shè)計(jì)與分析、形式語言與自動(dòng)機(jī)理論、密碼學(xué)等。先后主持承擔(dān)國家自然科學(xué)基金項(xiàng)目6項(xiàng)（從1987年到2004年，每3年1項(xiàng)）、山東省自然科學(xué)基金項(xiàng)目2項(xiàng)、煤炭科學(xué)基金項(xiàng)目2項(xiàng)；在《中國科學(xué)》、《科學(xué)通報(bào)》、《計(jì)算機(jī)學(xué)報(bào)》、《軟件學(xué)報(bào)》等國內(nèi)核心刊物，以及高校學(xué)報(bào)、國外刊物和國際學(xué)術(shù)會議發(fā)表學(xué)術(shù)論文90多篇，出版編、譯著3部；獲得過全國煤炭系統(tǒng)出國留學(xué)人員科研成果一等獎(jiǎng)1項(xiàng)（獨(dú)立）、國家教委科技進(jìn)步三等獎(jiǎng)1項(xiàng)（首位）、山東省科技進(jìn)步二等獎(jiǎng)1項(xiàng)（1項(xiàng)首位，1項(xiàng)第二位），山東省優(yōu)秀教學(xué)成果一等獎(jiǎng)1項(xiàng)（首位）、二等獎(jiǎng)2項(xiàng)（均首位）。

1989年被評為全國優(yōu)秀教師；1991年被評為全國有突出貢獻(xiàn)的回國留學(xué)人員，并獲得國務(wù)院頒發(fā)的政府特殊津貼；1992年被評為國家有突出貢獻(xiàn)的中青年專家；1993年和1994年兩度被評為山東省專業(yè)技術(shù)拔尖人才；1995年被評為山東省十大優(yōu)秀教師；1998年被評為全國教育系統(tǒng)勞動(dòng)模范，并被授予全國模范教師稱號和獎(jiǎng)?wù)隆?

本書簡要介紹了算法設(shè)計(jì)、分析和優(yōu)化的基礎(chǔ)知識，重點(diǎn)放在算法設(shè)計(jì)方法的學(xué)習(xí)上，通過大量的典型例題講解了常用算法設(shè)計(jì)方法（共10種）： 求值法、累加法、累乘法、遞推法、遞歸法、枚舉法、分治法、貪心法、回溯法和動(dòng)態(tài)規(guī)劃法，最后通過實(shí)例給出算法設(shè)計(jì)綜合應(yīng)用。每個(gè)例題從問題描述、問題分析、算法說明、算法設(shè)計(jì)、運(yùn)行結(jié)果和算法優(yōu)化6個(gè)方面進(jìn)行講解。

本書結(jié)合實(shí)例、內(nèi)容豐富、深入淺出、結(jié)構(gòu)清晰，可以作為高等院校計(jì)算機(jī)及其相關(guān)專業(yè)本科生和研究生算法設(shè)計(jì)課程的教材，也適合IT技術(shù)人員和計(jì)算機(jī)編程愛好者學(xué)習(xí)參考。

第1章算法概述1

1.1算法與問題求解1

1.1.1算法的定義1

1.1.2問題求解2

1.2算法的要素和特性3

1.2.1算法的要素3

1.2.2算法的基本特性4

1.3算法的描述5

1.3.1基本控制結(jié)構(gòu)的描述5

1.3.2C算法描述約定7

1.4算法分析9

1.4.1算法的評價(jià)標(biāo)準(zhǔn)9

1.4.2算法的時(shí)間復(fù)雜度10

1.4.3算法的空間復(fù)雜度11

1.5算法的優(yōu)化12

1.5.1全局優(yōu)化12

1.5.2局部優(yōu)化13

1.5.3算法優(yōu)化中的注意事項(xiàng)14第2章求值法17

2.1算法設(shè)計(jì)思想17

2.2典型例題17

2.2.1求最大值17

2.2.2求平均分19

2.2.3判斷閏年21

2.2.4素?cái)?shù)23

2.2.5孿生數(shù)25 算法設(shè)計(jì)方法與優(yōu)化 目錄 2.2.6巧排螺旋陣27

2.2.7百燈判熄31

2.3小結(jié)33

習(xí)題233第3章累加法35

3.1算法設(shè)計(jì)思想35

3.2典型例題35

3.2.1自然數(shù)求和35

3.2.2自然數(shù)倒數(shù)求和37

3.2.3統(tǒng)計(jì)及格人數(shù)38

3.2.4計(jì)算π值41

3.2.5統(tǒng)計(jì)對稱數(shù)42

3.2.6數(shù)列求和45

3.2.7判斷天數(shù)46

3.3小結(jié)48

習(xí)題349第4章累乘法51

4.1算法設(shè)計(jì)思想51

4.2典型例題51

4.2.1求n的階乘51

4.2.2計(jì)算偶數(shù)積52

4.2.3求階乘之和54

4.2.4大整數(shù)階乘56

4.2.5國王獎(jiǎng)賞問題58

4.2.6計(jì)算e值60

4.3小結(jié)62

習(xí)題462第5章遞推法65

5.1算法設(shè)計(jì)思想65

5.2典型例題66

5.2.1兔子繁殖問題66

5.2.2最大公約數(shù)問題68

5.2.3猴子吃桃問題70

5.2.4楊輝三角問題71

5.2.5穿越沙漠問題74

5.2.6分西瓜問題75

5.3小結(jié)77

習(xí)題577第6章遞歸法81

6.1算法設(shè)計(jì)思想81

6.2典型例題81

6.2.1母牛繁殖問題81

6.2.2輸出各位數(shù)字83

6.2.3最大值問題85

6.2.4計(jì)算x的n次冪87

6.2.5數(shù)組逆置89

6.2.6漢諾塔問題91

6.3小結(jié)93

習(xí)題693第7章枚舉法97

7.1算法設(shè)計(jì)思想97

7.2典型例題97

7.2.1百雞問題97

7.2.2水仙花數(shù)100

7.2.3完數(shù)102

7.2.4可逆素?cái)?shù)104

7.2.5串匹配問題107

7.2.6最小公倍數(shù)問題111

7.2.7獄吏問題113

7.3小結(jié)116

習(xí)題7116第8章分治法119

8.1算法設(shè)計(jì)思想119

8.2典型例題119

8.2.1折半查找119

8.2.2金塊問題121

8.2.3尋找第二的問題124

8.2.4歸并排序127

8.2.5大整數(shù)乘法131

8.2.6二叉樹遍歷133

8.3小結(jié)138

習(xí)題8138第9章貪心法141

9.1算法設(shè)計(jì)思想141

9.2典型例題142

9.2.1找零錢問題142

9.2.2最優(yōu)裝載145

9.2.3哈夫曼編碼149

9.2.4單源最短路徑155

9.2.5埃及分?jǐn)?shù)問題158

9.2.6多機(jī)調(diào)度問題162

9.3小結(jié)165

習(xí)題9166第10章回溯法169

10.1算法設(shè)計(jì)思想169

10.2典型例題170

10.2.1八皇后問題170

10.2.2圖著色問題174

10.2.3橋本分?jǐn)?shù)式176

10.2.4高逐位整除數(shù)180

10.2.5直尺刻度分布問題183

10.2.6素?cái)?shù)環(huán)問題186

10.2.7伯努利裝錯(cuò)信封問題190

10.3小結(jié)194

習(xí)題10195第11章動(dòng)態(tài)規(guī)劃197

11.1算法設(shè)計(jì)思想197

11.2典型例題198

11.2.1數(shù)塔問題198

11.2.2矩陣連乘問題202

11.2.3最長公共子序列問題207

11.2.4最長上升子序列問題211

11.2.5陪審團(tuán)問題215

11.3小結(jié)218

習(xí)題11218第12章綜合應(yīng)用223

12.1Fibonacci數(shù)列223

12.2π值求法227

12.3循環(huán)賽日程表230

12.4最大子段和問題239

12.5背包問題246

習(xí)題12256 2100433B

旋轉(zhuǎn)門算法除了平行四邊形算法之外，還能用三角形算法來表示。