書????名 | 算法設(shè)計與分析(第3版) | 作????者 | 王曉東 |
---|---|---|---|
類????別 | 普通高等教育“十一五”國家級規(guī)劃教材 | 出版社 | 清華大學(xué)出版社 |
出版時間 | 2014年1月1日 | 頁????數(shù) | 330 頁 |
開????本 | 16 開 | 裝????幀 | 平裝 |
ISBN | 9787302348641 | 字????數(shù) | 524千字 |
CIP核字號 | 2013310958 |
第1章算法引論11.1算法與程序1 1.2表達算法的抽象機制1 1.3描述算法3 1.4算法復(fù)雜性分析11 小結(jié)14 習(xí)題14 第2章遞歸與分治策略16 2.1遞歸的概念16 2.2分治法的基本思想22 2.3二分搜索技術(shù)23 2.4大整數(shù)的乘法24 2.5Strassen矩陣乘法25 2.6棋盤覆蓋26 2.7合并排序28 2.8快速排序30 2.9線性時間選擇33 2.10最接近點對問題36 2.11循環(huán)賽日程表43 小結(jié)44 習(xí)題45 第3章動態(tài)規(guī)劃50 3.1矩陣連乘問題50 3.2動態(tài)規(guī)劃算法的基本要素55 3.3最長公共子序列58 3.4凸多邊形最優(yōu)三角剖分61 3.5多邊形游戲64 3.6圖像壓縮67 3.7電路布線70 3.8流水作業(yè)調(diào)度72 3.90-1背包問題75 3.10最優(yōu)二叉搜索樹80 小結(jié)83 習(xí)題84 第4章貪心算法85 4.1活動安排問題85 4.2貪心算法的基本要素88 4.2.1貪心選擇性質(zhì)88 4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)88 4.2.3貪心算法與動態(tài)規(guī)劃算法的差異89 4.3最優(yōu)裝載91 4.4哈夫曼編碼92 4.4.1前綴碼93 4.4.2構(gòu)造哈夫曼編碼93 4.4.3哈夫曼算法的正確性95 4.5單源最短路徑97 4.5.1算法基本思想97 4.5.2算法的正確性和計算復(fù)雜性99 4.6最小生成樹100 4.6.1最小生成樹性質(zhì)100 4.6.2Prim算法100 4.6.3Kruskal算法102 4.7多機調(diào)度問題104 4.8貪心算法的理論基礎(chǔ)106 4.8.1擬陣107 4.8.2帶權(quán)擬陣的貪心算法108 4.8.3任務(wù)時間表問題110 小結(jié)113 習(xí)題113 第5章回溯法115 5.1回溯法的算法框架115 5.1.1問題的解空間115 5.1.2回溯法的基本思想116 5.1.3遞歸回溯117 5.1.4迭代回溯118 5.1.5子集樹與排列樹119 5.2裝載問題120 5.3批處理作業(yè)調(diào)度126 5.4符號三角形問題128 5.5n后問題130 5.60-1背包問題133 5.7最大團問題136 5.8圖的m著色問題138 5.9旅行售貨員問題140 5.10圓排列問題142 5.11電路板排列問題144 5.12連續(xù)郵資問題147 5.13回溯法的效率分析149 小結(jié)152 習(xí)題152 第6章分支限界法153 6.1分支限界法的基本思想153 6.2單源最短路徑問題156 6.3裝載問題158 6.4布線問題167 6.50-1背包問題171 6.6最大團問題175 6.7旅行售貨員問題178 6.8電路板排列問題182 6.9批處理作業(yè)調(diào)度184 小結(jié)189 習(xí)題189 第7章概率算法190 7.1隨機數(shù)191 |
7.2數(shù)值概率算法193 7.2.1用隨機投點法計算π值193 7.2.2計算定積分194 7.2.3解非線性方程組196 7.3舍伍德算法198 7.3.1線性時間選擇算法198 7.3.2跳躍表200 7.4拉斯維加斯算法205 7.4.1n后問題206 7.4.2整數(shù)因子分解209 7.5蒙特卡羅算法211 7.5.1蒙特卡羅算法的基本思想211 7.5.2主元素問題213 7.5.3素數(shù)測試214 小結(jié)217 習(xí)題217 第8章NP完全性理論221 8.1計算模型221 8.1.1隨機存取機RAM222 8.1.2隨機存取存儲程序機RASP228 8.1.3RAM模型的變形與簡化231 8.1.4圖靈機235 8.1.5圖靈機模型與RAM模型的關(guān)系236 8.1.6問題變換與計算復(fù)雜性歸約238 8.2P類與NP類問題239 8.2.1非確定性圖靈機239 8.2.2P類與NP類語言240 8.2.3多項式時間驗證241 8.3NP完全問題243 8.3.1多項式時間變換243 8.3.2Cook定理244 8.4一些典型的NP完全問題247 8.4.1合取范式的可滿足性問題247 8.4.23元合取范式的可滿足性問題248 8.4.3團問題249 8.4.4頂點覆蓋問題250 8.4.5子集和問題251 8.4.6哈密頓回路問題252 8.4.7旅行售貨員問題256 小結(jié)256 習(xí)題257 第9章近似算法259 9.1近似算法的性能259 9.2頂點覆蓋問題的近似算法260 9.3旅行售貨員問題近似算法262 9.3.1具有三角不等式性質(zhì)的旅行售貨員問題262 9.3.2一般的旅行售貨員問題263 9.4集合覆蓋問題的近似算法264 9.5子集和問題的近似算法267 9.5.1子集和問題的指數(shù)時間算法267 9.5.2子集和問題的完全多項式時間近似格式268 小結(jié)270 習(xí)題270 第10章算法優(yōu)化策略273 10.1算法設(shè)計策略的比較與選擇273 10.1.1最大子段和問題的簡單算法273 10.1.2最大子段和問題的分治算法274 10.1.3最大子段和問題的動態(tài)規(guī)劃算法275 10.1.4最大子段和問題與動態(tài)規(guī)劃算法的推廣276 10.2動態(tài)規(guī)劃加速原理279 10.2.1貨物儲運問題279 10.2.2算法及其優(yōu)化279 10.3問題的算法特征283 10.3.1貪心策略283 10.3.2對貪心策略的改進283 10.3.3算法三部曲285 10.3.4算法實現(xiàn)285 10.3.5算法復(fù)雜性290 10.4優(yōu)化數(shù)據(jù)結(jié)構(gòu)291 10.4.1帶權(quán)區(qū)間最短路問題291 10.4.2算法設(shè)計思想291 10.4.3算法實現(xiàn)方案293 10.4.4并查集296 10.4.5可并優(yōu)先隊列298 10.5優(yōu)化搜索策略302 小結(jié)308 習(xí)題309 第11章在線算法設(shè)計310 11.1在線算法設(shè)計的基本概念310 11.2頁調(diào)度問題312 11.3勢函數(shù)分析314 11.4k服務(wù)問題315 11.4.1競爭比的下界315 11.4.2平衡算法316 11.4.3對稱移動算法317 11.5Steiner樹問題320 11.6在線任務(wù)調(diào)度321 11.7負載平衡322 小結(jié)323 習(xí)題324 詞匯索引325 參考文獻330 |
(注:目錄排版順序為從左列至右列)
該教材有配套教材——《算法設(shè)計與分析習(xí)題解答(第3版)》,書中對主教材的全部習(xí)題做了解答。
書名 |
書號 |
出版社 |
出版時間 |
作者 |
---|---|---|---|---|
《算法設(shè)計與分析習(xí)題解答(第3版)》 |
9787302348634 |
清華大學(xué)出版社 |
2014.02.01 |
王曉東 |
該教材是為了適應(yīng)培養(yǎng)中國21世紀計算機各類人才的需要,結(jié)合中國高等學(xué)校教育工作的現(xiàn)狀,立足培養(yǎng)學(xué)生能跟上國際計算機科學(xué)技術(shù)的發(fā)展水平,更新教學(xué)內(nèi)容和教學(xué)方法,提高教學(xué)質(zhì)量的基礎(chǔ)上編寫而成。
該教材由王曉東編著。在編寫過程中,得到教育部高等學(xué)校計算機類專業(yè)教學(xué)指導(dǎo)委員會的支持。福州大學(xué)“211工程”計算機與信息工程重點學(xué)科實驗室為該教材的寫作提供了設(shè)備與工作環(huán)境。南京大學(xué)宋方敏教授和福州大學(xué)傅清祥教授審閱了全書,提出了改進意見。
2014年1月1日,該教材由清華大學(xué)出版社出版。
責(zé)任編輯 |
封面設(shè)計 |
責(zé)任校對 |
責(zé)任印制 |
---|---|---|---|
張瑞慶 |
傅瑞學(xué) |
時翠蘭 |
何芊 |
系統(tǒng)設(shè)計與分析都應(yīng)該遵循哪些原則?
易用性原則方便上網(wǎng)客戶瀏覽和操作,最大限度地減輕后臺管理人員的負擔(dān),做到部分業(yè)務(wù)的自動化處理。安全性原則系統(tǒng)采取全面的安全保護措施,具有防病毒感染、防黑客攻擊措施,同時在防雷擊、過載、斷電和人為破壞方...
系統(tǒng)設(shè)計與分析都應(yīng)該遵循哪些原則?
易用性原則 方便上網(wǎng)客戶瀏覽和操作,最大限度地減輕后臺管理人員的負擔(dān),做到部分業(yè)務(wù)的自動化處理。 安全性原則 系統(tǒng)采取全面的安全保護措施,具有防病毒感染、防黑客攻擊措施,同時在防雷擊、過載、斷電...
我們河南定額模板工程量一般情況與現(xiàn)澆混凝土構(gòu)件工程量是相同的,不是按面積計算的,大多數(shù)是按混凝土體積計算的,但樓梯是按投影面積計算的。
該教材以算法設(shè)計策略為知識單元,介紹了計算機算法的設(shè)計方法與分析技巧。
全書共分11章。
在第1章中首先介紹算法的基本概念,接著簡要闡述算法的計算復(fù)雜性和算法的描述,然后圍繞設(shè)計算法常用的基本設(shè)計策略組織第2章至第10章的內(nèi)容。
第2章介紹遞歸與分治策略,這是設(shè)計有效算法最常用的策略。
第3章是動態(tài)規(guī)劃算法,以具體實例詳述動態(tài)規(guī)劃算法的設(shè)計思想、適用性以及算法的設(shè)計要點。
第4章介紹貪心算法,這也是一種重要的算法設(shè)計策略,它與動態(tài)規(guī)劃算法的設(shè)計思想有一定的聯(lián)系,但其效率更高。按貪心算法設(shè)計出的許多算法能導(dǎo)致最優(yōu)解。
第5章和第6章分別介紹回溯法和分支限界法。這兩章所介紹的算法適合于處理難解問題。
第7章介紹概率算法,對許多難解問題提供高效的解決途徑,是有較高實用價值的算法設(shè)計策略。
第8章介紹NP完全性理論。首先介紹計算模型、確定性和非確定性圖靈機,然后進一步介紹NP完全性理論。
第9章介紹了解NP難問題的近似算法,這是計算機算法領(lǐng)域的熱門研究課題,具有較高的實用價值。
第10章通過實例介紹算法設(shè)計中常用的算法優(yōu)化策略。
最后,在第11章介紹算法設(shè)計中較新的研究領(lǐng)域——在線算法設(shè)計。
在該教材各章的論述中,首先介紹一種算法設(shè)計策略的基本思想,然后從解決計算機科學(xué)與應(yīng)用中出現(xiàn)的實際問題入手,由簡到繁地描述幾個經(jīng)典的精巧算法,同時對每個算法所需要的時間和空間進行分析。
在為各種算法設(shè)計策略選擇用于展示其設(shè)計思想與技巧的具體應(yīng)用問題時,該教材有意重復(fù)選擇某些經(jīng)典問題,使讀者能體會到一個問題可以用多種設(shè)計策略求解。同時,通過對解同一問題的不同算法的比較,更容易體會到每一個具體算法的設(shè)計要點。隨著該教材內(nèi)容的逐步展開,讀者也將進一步感受到綜合應(yīng)用多種設(shè)計策略可以更有效地解決問題。
該教材采用面向?qū)ο蟮腏ava語言作為表述手段,在保持Java優(yōu)點的同時,盡量使算法的描述簡明。為了加深對知識的理解,各章配有難易適當(dāng)?shù)牧?xí)題,以適應(yīng)不同程度讀者練習(xí)的需要。
王曉東,男,1957年出生,山東人,中共黨員,現(xiàn)任福建工程學(xué)院副院長、教授、博士生導(dǎo)師。先后擔(dān)任福州大學(xué)計算機系主任、數(shù)學(xué)與計算機科學(xué)學(xué)院院長,2007年8月起擔(dān)任泉州師范學(xué)院副院長,2014年8月起任現(xiàn)職。 2100433B
格式:pdf
大?。?span id="xjcgbyc" class="single-tag-height">210KB
頁數(shù): 9頁
評分: 4.8
實 驗 報 告 (2016/2017 學(xué)年 第一學(xué)期) 學(xué)生姓名 周文超 班級學(xué)號 B14041527 學(xué)院 (系) 計算機學(xué)院、 軟件學(xué)院 專 業(yè) 軟件工程 課程名稱 算法分析與設(shè)計 實驗名稱 分治策略 實驗時間 2016 年 10 月 18 日 指導(dǎo)單位 計算機學(xué)院軟件教學(xué)中心 指導(dǎo)教師 季一木 2 實 驗 報 告 實驗名稱 分治策略 指導(dǎo)教師 季一木 實驗類型 驗證 實驗學(xué)時 2 實驗時間 2016.10.18 一、 實驗?zāi)康暮腿蝿?wù) 1.理解分治法的算法思想, 閱讀實現(xiàn)書上已有的部分程序代碼并完善程 序,加深對分治法的算法原理及實現(xiàn)過程的理解。 2. 用分治法實現(xiàn)一組無序序列的兩路合并排序和快速排序。要求清楚 合并排序及快速排序的基本原理, 編程實現(xiàn)分別用這兩種方法將輸入的一組 無序序列排序為有序序列后輸出。 3 二、 實驗環(huán)境 (實驗設(shè)備 ) 算法設(shè)計與分析課本 筆記本
格式:pdf
大?。?span id="141y2fy" class="single-tag-height">210KB
頁數(shù): 未知
評分: 4.7
隨著信息科技的飛速發(fā)展,項目管理系統(tǒng)在各類項目管理中占據(jù)了重要地位,越來越多的自動化管理代替了傳統(tǒng)的人工項目管理。大多項目管理系統(tǒng)均采用了關(guān)鍵鏈方法,在關(guān)鍵鏈方法中緩沖區(qū)的設(shè)置是關(guān)鍵因素之一。因此關(guān)鍵鏈方法的緩沖區(qū)設(shè)置成為一個新的應(yīng)用課題。本文在深入研究并對比現(xiàn)有的緩沖區(qū)計算方法的基礎(chǔ)上,提出了綜合考慮項目管理者的風(fēng)險偏好、工序的復(fù)雜程度以及資源約束等幾個因素,再利用時間差的方法,設(shè)計并模擬實現(xiàn)一種緩沖區(qū)設(shè)置的算法,具有相當(dāng)大的實用價值。
配套教材
《計算機算法設(shè)計與分析(第5版)》有配套教材——《計算機算法設(shè)計與分析習(xí)題解答(第5版)》 。
書名 |
ISNB |
出版社 |
出版時間 |
作者 |
---|---|---|---|---|
《計算機算法設(shè)計與分析習(xí)題解答(第5版)》 |
9787121344381 |
電子工業(yè)出版社 |
2018年10月 |
王曉東 |
《計算機算法設(shè)計與分析(第5版)》修正了第4版中發(fā)現(xiàn)的一些錯誤,并將各章的習(xí)題分為算法分析題和算法實現(xiàn)題兩部分,增加了算法實踐性內(nèi)容,增加了有關(guān)串和序列的算法內(nèi)容。
該教材各章的論述中,首先介紹一種算法設(shè)計策略的基本思想,然后從解決計算機科學(xué)和應(yīng)用中的實際問題入手,描述幾個算法。同時對每個算法所需的時間和空間進行分析,使讀者既能學(xué)到一些常用的算法,也能通過對算法設(shè)計策略的反復(fù)應(yīng)用,牢固掌握這些算法設(shè)計的基本策略。該教材選擇某些問題,通過對解同一問題的不同算法的比較,使讀者體會到每種算法的設(shè)計要點。
該教材采用面向?qū)ο蟮腃 語言作為算法描述手段,在保持C 優(yōu)點的同時,盡量使算法描述簡明、清晰。每章的章首為學(xué)習(xí)要點提示,章末配有難易適度的習(xí)題,分為算法分析題和算法實現(xiàn)題兩部分,以強化實踐環(huán)節(jié) 。
《計算機算法設(shè)計與分析(第5版)》共9章,具體如下:
第1章介紹算法的基本概念,并對算法的計算復(fù)雜性和算法的描述做了闡述。然后圍繞算法設(shè)計常用的基本設(shè)計策略組織了第2~9章的內(nèi)容。
第2章介紹遞歸與分治策略。
第3章介紹動態(tài)規(guī)劃算法,以具體實例講述動態(tài)規(guī)劃算法的設(shè)計思想、適用性及算法的設(shè)計要點。
第4章介紹貪心算法,它也是一種算法設(shè)計策略,它與動態(tài)規(guī)劃算法的設(shè)計思想有一定的聯(lián)系。
第5章和第6章分別介紹回溯法和分支限界法。這兩章所介紹的算法適合處理難解問題。
第7章介紹隨機化算法,對難解問題提供了解決途徑。
第8章介紹線性規(guī)劃與網(wǎng)絡(luò)流算法。許多實際應(yīng)用問題可以轉(zhuǎn)化為線性規(guī)劃和網(wǎng)絡(luò)流問題,并可用第8章中的算法有效求解。
第9章介紹在大數(shù)據(jù)和人工智能中有應(yīng)用的串和序列的算法 。