算法設(shè)計(jì)方法圖書簡(jiǎn)介

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

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

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

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

主要研究領(lǐng)域有：petri網(wǎng)理論與并行分時(shí)系統(tǒng)、算法設(shè)計(jì)與分析、形式語(yǔ)言與自動(dòng)機(jī)理論、密碼學(xué)等。先后主持承擔(dān)國(guó)家自然科學(xué)基金項(xiàng)目6項(xiàng)（從1987年到2004年，每3年1項(xiàng)）、山東省自然科學(xué)基金項(xiàng)目2項(xiàng)、煤炭科學(xué)基金項(xiàng)目2項(xiàng)；在《中國(guó)科學(xué)》、《科學(xué)通報(bào)》、《計(jì)算機(jī)學(xué)報(bào)》、《軟件學(xué)報(bào)》等國(guó)內(nèi)核心刊物，以及高校學(xué)報(bào)、國(guó)外刊物和國(guó)際學(xué)術(shù)會(huì)議發(fā)表學(xué)術(shù)論文90多篇，出版編、譯著3部；獲得過(guò)全國(guó)煤炭系統(tǒng)出國(guó)留學(xué)人員科研成果一等獎(jiǎng)1項(xiàng)（獨(dú)立）、國(guó)家教委科技進(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年被評(píng)為全國(guó)優(yōu)秀教師；1991年被評(píng)為全國(guó)有突出貢獻(xiàn)的回國(guó)留學(xué)人員，并獲得國(guó)務(wù)院頒發(fā)的政府特殊津貼；1992年被評(píng)為國(guó)家有突出貢獻(xiàn)的中青年專家；1993年和1994年兩度被評(píng)為山東省專業(yè)技術(shù)拔尖人才；1995年被評(píng)為山東省十大優(yōu)秀教師；1998年被評(píng)為全國(guó)教育系統(tǒng)勞動(dòng)模范，并被授予全國(guó)模范教師稱號(hào)和獎(jiǎng)?wù)隆?

算法設(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排序問(wèn)題的分治與遞歸算法

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背包問(wèn)題的貪心算法

4.2求最小生成樹的Kruskal算法

4.3求最小生成樹的Prim算法

4.4求單源最短路的Dijkstra算法

4.5哈夫曼編碼

4.6習(xí)題

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

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

5.1多段圖問(wèn)題

5.2矩陣連乘積問(wèn)題

5.30.1背包問(wèn)題

5.4旅行售貨員問(wèn)題

5.5最長(zhǎng)公共子序列問(wèn)題

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

5.7資源分配問(wèn)題

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

5.9習(xí)題

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

回溯算法

6.1回溯算法的基本思想

6.2旅行售貨員問(wèn)題

6.3n后問(wèn)題

6.4圖的m著色問(wèn)題

6.50-1背包問(wèn)題

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

6.7哈密爾頓回路問(wèn)題

6.8子集和數(shù)問(wèn)題

6.9回溯法效率分析

6.10習(xí)題

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

分支限界算法

7.1基本思想

7.20-1背包問(wèn)題

7.3旅行售貨員問(wèn)題

7.4任務(wù)分配問(wèn)題

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

7.6重排九宮問(wèn)題

7.7習(xí)題

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

NP-完全問(wèn)題

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ī)問(wèn)題與可計(jì)算性度量

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

8.2P類和NP類問(wèn)題

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

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

8.3NP完全問(wèn)題與Cook定理

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

8.3.2Cook定理

8.3.3其他NP完全問(wèn)題

8.3.4CO-NP問(wèn)題與NPI問(wèn)題

8.4NP困難問(wèn)題的近似算法和概率算法

8.4.1近似算法

8.4.2概率算法

8.5習(xí)題

2100433B

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

第1章算法概述1

1.1算法與問(wèn)題求解1

1.1.1算法的定義1

1.1.2問(wèn)題求解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算法的評(píng)價(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局部?jī)?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ì)對(duì)稱數(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國(guó)王獎(jiǎng)賞問(wèn)題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兔子繁殖問(wèn)題66

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

5.2.3猴子吃桃問(wèn)題70

5.2.4楊輝三角問(wèn)題71

5.2.5穿越沙漠問(wèn)題74

5.2.6分西瓜問(wèn)題75

5.3小結(jié)77

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

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

6.2典型例題81

6.2.1母牛繁殖問(wèn)題81

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

6.2.3最大值問(wèn)題85

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

6.2.5數(shù)組逆置89

6.2.6漢諾塔問(wèn)題91

6.3小結(jié)93

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

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

7.2典型例題97

7.2.1百雞問(wèn)題97

7.2.2水仙花數(shù)100

7.2.3完數(shù)102

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

7.2.5串匹配問(wèn)題107

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

7.2.7獄吏問(wèn)題113

7.3小結(jié)116

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

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

8.2典型例題119

8.2.1折半查找119

8.2.2金塊問(wèn)題121

8.2.3尋找第二的問(wèn)題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找零錢問(wèn)題142

9.2.2最優(yōu)裝載145

9.2.3哈夫曼編碼149

9.2.4單源最短路徑155

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

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

9.3小結(jié)165

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

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

10.2典型例題170

10.2.1八皇后問(wèn)題170

10.2.2圖著色問(wèn)題174

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

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

10.2.5直尺刻度分布問(wèn)題183

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

10.2.7伯努利裝錯(cuò)信封問(wèn)題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ù)塔問(wèn)題198

11.2.2矩陣連乘問(wèn)題202

11.2.3最長(zhǎng)公共子序列問(wèn)題207

11.2.4最長(zhǎng)上升子序列問(wèn)題211

11.2.5陪審團(tuán)問(wè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最大子段和問(wèn)題239

12.5背包問(wèn)題246

習(xí)題12256 2100433B

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