掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
全國計算機等級考試最新真考題庫模擬考場及詳解·二級MSOffice高級應用
-
>
決戰行測5000題(言語理解與表達)
-
>
軟件性能測試.分析與調優實踐之路
-
>
第一行代碼Android
-
>
JAVA持續交付
-
>
EXCEL最強教科書(完全版)(全彩印刷)
-
>
深度學習
買過本商品的人還買了
算法設計與分析(第3版) 版權信息
- ISBN：9787302612391
- 條形碼：9787302612391 ; 978-7-302-61239-1
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
算法設計與分析(第3版) 本書特色
本書由北京大學優秀教學團隊編寫，凝聚了教學團隊多年教學經驗和科研成果。 計算機科學技術發展迅猛，各種新的技術和算法層出不窮。然而萬變不離其宗，各種新的算法依然是建立在各種經典算法技術的基礎上，*新的算法技術往往是對各種已有算法技術的組合和改進。在掌握了本書所介紹的各種經典算法技術之后，再學習理解新的算法技術時，或者再學習掌握各領域內的專門算法時，往往可以事半功倍。 本書以算法設計技術為主線組織素材，以偽碼描述算法，深入分析了各種設計技術的使用范圍、設計步驟、算法正確性證明與時間復雜度估計方法，以及改進算法的途徑、局限性等，為實際問題的建模與算法設計在理論上提供清晰的思路。從對具體算法的設計與分析，自然過渡到對問題難度的分析和界定，系統地介紹了一些關于問題復雜度的分析方法。力求用清晰易懂的語言介紹NP完全性理論的核心內容和難解問題的處理策略，希望為求解實際中的復雜問題提供幫助。除了傳統的算法外，本書還介紹了隨機算法、模擬退火算法、基于統計物理的消息傳遞算法、量子算法等，給有興趣的讀者提供進一步學習和研究的入門知識。本書的主要素材來自多年的教學積淀，也有一些研究的心得。既注意理論上嚴謹性，又精選了大量實例，并配有難度適當的練習，適合教學使用。 北京大學優秀教學團隊力作！凝聚多年教學積淀和科研成果。根據教育部“高等學校計算機科學與技術專業規范”編寫，與美國ACM和IEEE CS Computing Curricula*新進展同步。
算法設計與分析(第3版) 內容簡介
本書為高等學校計算機類專業核心課程“算法設計與分析”教材. 全書以算法設計技術和分析方法為主線來組織各知識單元. 主要內容包括基礎知識、分治策略、動態規劃、貪心法、回溯與分支限界、線性規劃、網絡流算法、算法分析與問題的計算復雜度、NP接近性、近似算法、隨機算法、處理難解問題的策略等. 力求突出對問題本身的分析和求解方法的闡述，從問題建模、算法設計與分析、改進措施等方面給出適當的建議，同時也簡要介紹了計算復雜性理論的核心內容和處理難解問題的一些新技術. 與本書配套的有習題解答與學習指導用書、PPT電子教案以及MOOC視頻教學資源等. 本書適合作為高等學校計算機科學與技術、軟件工程、信息安全、信息與計算科學等專業本科生和研究生的教學用書，也可以作為從事實際問題求解的算法設計與分析工作的科技人員的參考書.
算法設計與分析(第3版) 目錄
第1章基礎知識1
1.1有關算法的基本概念1
1.2算法的偽碼描述5
1.3算法的數學基礎6
1.3.1函數的漸近的界6
1.3.2求和的方法10
1.3.3遞推方程求解方法12
習題121
第2章分治策略26
2.1分治策略的基本思想26
2.1.1兩個熟悉的例子26
2.1.2分治算法的一般性描述27
2.2分治算法的分析技術27
2.3改進分治算法的途徑31
2.3.1通過代數變換減少子問題個數31
2.3.2利用預處理減少遞歸內部的計算量34
2.4典型實例37
2.4.1快速排序算法37
2.4.2選擇問題40
2.4.3n-1次多項式在全體2n次方根上的求值44
習題247
第3章動態規劃52
3.1動態規劃的設計思想52
3.1.1多起點、多終點的*短路徑問題53
3.1.2使用動態規劃技術的必要條件54
3.2動態規劃算法的設計要素55目錄算法設計與分析（第3版）3.2.1子問題的劃分和遞推方程56
3.2.2動態規劃算法的遞歸實現57
3.2.3動態規劃算法的迭代實現58
3.2.4一個簡單實例的計算過程59
3.3動態規劃算法的典型應用60
3.3.1投資問題60
3.3.2背包問題63
3.3.3*長公共子序列LCS65
3.3.4圖像壓縮68
3.3.5*大子段和72
3.3.6*優二分檢索樹76
3.3.7生物信息學中的動態規劃算法80
習題383
第4章貪心法87
4.1貪心法的設計思想87
4.2關于貪心法的正確性證明90
4.3對貪心法得不到*優解情況的處理94
4.4貪心法的典型應用98
4.4.1*優前綴碼98
4.4.2*小生成樹103
4.4.3單源*短路徑108
習題4110
第5章回溯與分支限界114
5.1回溯算法的基本思想和適用條件114
5.1.1幾個典型的例子114
5.1.2回溯算法的適用條件118
5.2回溯算法的設計步驟119
5.2.1回溯算法的遞歸實現和迭代實現119
5.2.2幾個典型的例子120
5.3回溯算法的效率估計和改進途徑122
5.4分支限界124
5.4.1背包問題125
5.4.2*大團問題127
5.4.3貨郎問題128
5.4.4圓排列問題129
5.4.5連續郵資問題131
習題5132
第6章線性規劃134
6.1線性規劃模型134
6.1.1模型134
6.1.2二維線性規劃的圖解法137
6.2標準形139
6.2.1標準形的基本概念139
6.2.2標準形的可行解的性質140
6.3單純形法143
6.3.1確定初始基本可行解143
6.3.2*優性檢驗143
6.3.3基變換144
6.3.4單純形表146
6.3.5人工變量和兩階段法148
6.3.6單純形法的有限終止154
6.4對偶性155
6.4.1對偶線性規劃155
6.4.2對偶單純形法159
6.5整數線性規劃的分支限界算法160
習題6165
第7章網絡流算法171
7.1*大流問題171
7.1.1網絡流及其性質171
7.1.2FordFulkerson算法173
7.1.3Dinic有效算法176
7.2*小費用流184
7.2.1Floyd算法184
7.2.2*小費用流的負回路算法186
7.2.3*小費用流的*短路徑算法188
7.3運輸問題189
7.3.1確定初始調運方案191
7.3.2改進調運方案191
7.3.3表上作業法193
7.4二部圖匹配194
7.4.1二部圖的*大匹配194
7.4.2賦權二部圖的匹配197
習題7203
第8章算法分析與問題的計算復雜度208
8.1平凡下界209
8.2直接計數求解該問題所需要的*少運算210
8.3決策樹211
8.4檢索算法的時間復雜度分析212
8.5排序算法的時間復雜度分析214
8.5.1冒泡排序算法214
8.5.2堆排序算法215
8.5.3排序算法的決策樹與算法類時間復雜度的下界220
8.6選擇算法的時間復雜度分析222
8.6.1找*大和*小問題223
8.6.2找第二大問題224
8.6.3找中位數的問題226
8.7通過歸約確認問題計算復雜度的下界228
習題8229
第9章NP完全性231
9.1P類與NP類231
9.1.1易解的問題與難解的問題231
9.1.2判定問題233
9.1.3NP類235
9.2多項式時間變換與NP完全性236
9.2.1多項式時間變換236
9.2.2NP完全性及其性質238
9.2.3CookLevin定理——**個NP完全問題239
9.3幾個NP完全問題239
9.3.1*大可滿足性與三元可滿足性239
9.3.2頂點覆蓋、團與獨立集241
9.3.3哈密頓回路與貨郎問題243
9.3.4恰好覆蓋245
9.3.5子集和、背包、裝箱與雙機調度247
9.3.6整數線性規劃249
習題9252
第10章近似算法255
10.1近似算法及其近似比255
10.2多機調度問題256
10.2.1貪心的近似算法256
10.2.2改進的貪心近似算法257
10.3貨郎問題258
10.3.1*鄰近法258
10.3.2*小生成樹法259
10.3.3*小權匹配法259
10.4背包問題261
10.4.1一個簡單的貪心算法261
10.4.2多項式時間近似方案261
10.4.3偽多項式時間算法與完全多項式時間近似方案262
習題10264
第11章隨機算法266
11.1概率論預備知識266
11.2對隨機快速排序算法的分析268
11.3隨機算法的分類及其局限性270
11.3.1拉斯維加斯型隨機算法270
11.3.2蒙特卡洛型隨機算法270
11.3.3隨機算法的局限性271
11.4素數檢驗和多項式恒等檢驗271
11.4.1素數檢驗272
11.4.2多項式恒等檢驗273
11.5隨機游動算法274
11.5.1有限馬爾可夫鏈及其表示274
11.5.2求解二元布爾可滿足性問題的隨機游動算法275
11.6姚的極小極大原理276
習題11278
第12章處理難解問題的策略279
12.1對問題施加限制279
12.1.1二元可滿足性問題280
12.1.2霍恩公式可滿足性問題280
12.2固定參數算法282
12.3改進指數時間算法284
12.4啟發式方法286
12.5平均情形的復雜性287
12.6難解算例生成289
12.6.1相變現象與難解性289
12.6.2隱藏解的難解算例291
12.7基于統計物理的消息傳遞算法292
12.7.1消息傳遞算法與回溯法、局部搜索算法的比較292
12.7.2用消息傳遞算法求解3SAT問題293
12.8量子算法簡介294
12.8.1量子比特294
12.8.2正交測量295
12.8.3量子門296
12.8.4一個量子算法297
習題12299
參考文獻300
展開全部
算法設計與分析(第3版) 作者簡介
王捍貧，博士，北京大學信息科學技術學院教授，博士生導師，軟件研究所副所長，中國人工智能學會離散智能計算專委會主任。長期從事離散數學、形式化方法及算法設計與分析的教學和研究工作。主持完成多項 研究課題，撰寫和翻譯多部離散數學和計算理論教材，曾獲得北京市教學成果獎一等獎，系 精品課“離散數學”課程主講教師， 精品資源共享課“離散數學”課程主持人，“算法設計與分析”課程主講教師。
書友推薦
- >
【精裝繪本】畫給孩子的中國神話
- >
李白與唐代文化
- >
回憶愛瑪儂
- >
我從未如此眷戀人間
- >
羅曼·羅蘭讀書隨筆-精裝
- >
煙與鏡
- >
隨園食單
- >
伯納黛特,你要去哪(2021新版)
本類暢銷
