該教材有配套教材——《算法設(shè)計(jì)與分析習(xí)題解答(第3版)》,書中對(duì)主教材的全部習(xí)題做了解答。
書名 |
書號(hào) |
出版社 |
出版時(shí)間 |
作者 |
---|---|---|---|---|
《算法設(shè)計(jì)與分析習(xí)題解答(第3版)》 |
9787302348634 |
清華大學(xué)出版社 |
2014.02.01 |
王曉東 |
第1章算法引論11.1算法與程序1 1.2表達(dá)算法的抽象機(jī)制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線性時(shí)間選擇33 2.10最接近點(diǎn)對(duì)問題36 2.11循環(huán)賽日程表43 小結(jié)44 習(xí)題45 第3章動(dòng)態(tài)規(guī)劃50 3.1矩陣連乘問題50 3.2動(dòng)態(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活動(dòng)安排問題85 4.2貪心算法的基本要素88 4.2.1貪心選擇性質(zhì)88 4.2.2最優(yōu)子結(jié)構(gòu)性質(zhì)88 4.2.3貪心算法與動(dòng)態(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算法的正確性和計(jì)算復(fù)雜性99 4.6最小生成樹100 4.6.1最小生成樹性質(zhì)100 4.6.2Prim算法100 4.6.3Kruskal算法102 4.7多機(jī)調(diào)度問題104 4.8貪心算法的理論基礎(chǔ)106 4.8.1擬陣107 4.8.2帶權(quán)擬陣的貪心算法108 4.8.3任務(wù)時(shí)間表問題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符號(hào)三角形問題128 5.5n后問題130 5.60-1背包問題133 5.7最大團(tuán)問題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最大團(tuán)問題175 6.7旅行售貨員問題178 6.8電路板排列問題182 6.9批處理作業(yè)調(diào)度184 小結(jié)189 習(xí)題189 第7章概率算法190 7.1隨機(jī)數(shù)191 |
7.2數(shù)值概率算法193 7.2.1用隨機(jī)投點(diǎn)法計(jì)算π值193 7.2.2計(jì)算定積分194 7.2.3解非線性方程組196 7.3舍伍德算法198 7.3.1線性時(shí)間選擇算法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素?cái)?shù)測(cè)試214 小結(jié)217 習(xí)題217 第8章NP完全性理論221 8.1計(jì)算模型221 8.1.1隨機(jī)存取機(jī)RAM222 8.1.2隨機(jī)存取存儲(chǔ)程序機(jī)RASP228 8.1.3RAM模型的變形與簡化231 8.1.4圖靈機(jī)235 8.1.5圖靈機(jī)模型與RAM模型的關(guān)系236 8.1.6問題變換與計(jì)算復(fù)雜性歸約238 8.2P類與NP類問題239 8.2.1非確定性圖靈機(jī)239 8.2.2P類與NP類語言240 8.2.3多項(xiàng)式時(shí)間驗(yàn)證241 8.3NP完全問題243 8.3.1多項(xiàng)式時(shí)間變換243 8.3.2Cook定理244 8.4一些典型的NP完全問題247 8.4.1合取范式的可滿足性問題247 8.4.23元合取范式的可滿足性問題248 8.4.3團(tuán)問題249 8.4.4頂點(diǎn)覆蓋問題250 8.4.5子集和問題251 8.4.6哈密頓回路問題252 8.4.7旅行售貨員問題256 小結(jié)256 習(xí)題257 第9章近似算法259 9.1近似算法的性能259 9.2頂點(diǎn)覆蓋問題的近似算法260 9.3旅行售貨員問題近似算法262 9.3.1具有三角不等式性質(zhì)的旅行售貨員問題262 9.3.2一般的旅行售貨員問題263 9.4集合覆蓋問題的近似算法264 9.5子集和問題的近似算法267 9.5.1子集和問題的指數(shù)時(shí)間算法267 9.5.2子集和問題的完全多項(xiàng)式時(shí)間近似格式268 小結(jié)270 習(xí)題270 第10章算法優(yōu)化策略273 10.1算法設(shè)計(jì)策略的比較與選擇273 10.1.1最大子段和問題的簡單算法273 10.1.2最大子段和問題的分治算法274 10.1.3最大子段和問題的動(dòng)態(tài)規(guī)劃算法275 10.1.4最大子段和問題與動(dòng)態(tài)規(guī)劃算法的推廣276 10.2動(dòng)態(tài)規(guī)劃加速原理279 10.2.1貨物儲(chǔ)運(yùn)問題279 10.2.2算法及其優(yōu)化279 10.3問題的算法特征283 10.3.1貪心策略283 10.3.2對(duì)貪心策略的改進(jìn)283 10.3.3算法三部曲285 10.3.4算法實(shí)現(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è)計(jì)思想291 10.4.3算法實(shí)現(xiàn)方案293 10.4.4并查集296 10.4.5可并優(yōu)先隊(duì)列298 10.5優(yōu)化搜索策略302 小結(jié)308 習(xí)題309 第11章在線算法設(shè)計(jì)310 11.1在線算法設(shè)計(jì)的基本概念310 11.2頁調(diào)度問題312 11.3勢(shì)函數(shù)分析314 11.4k服務(wù)問題315 11.4.1競爭比的下界315 11.4.2平衡算法316 11.4.3對(duì)稱移動(dòng)算法317 11.5Steiner樹問題320 11.6在線任務(wù)調(diào)度321 11.7負(fù)載平衡322 小結(jié)323 習(xí)題324 詞匯索引325 參考文獻(xiàn)330 |
(注:目錄排版順序?yàn)閺淖罅兄劣伊?/i>)
該教材以算法設(shè)計(jì)策略為知識(shí)單元,介紹了計(jì)算機(jī)算法的設(shè)計(jì)方法與分析技巧。
全書共分11章。
在第1章中首先介紹算法的基本概念,接著簡要闡述算法的計(jì)算復(fù)雜性和算法的描述,然后圍繞設(shè)計(jì)算法常用的基本設(shè)計(jì)策略組織第2章至第10章的內(nèi)容。
第2章介紹遞歸與分治策略,這是設(shè)計(jì)有效算法最常用的策略。
第3章是動(dòng)態(tài)規(guī)劃算法,以具體實(shí)例詳述動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想、適用性以及算法的設(shè)計(jì)要點(diǎn)。
第4章介紹貪心算法,這也是一種重要的算法設(shè)計(jì)策略,它與動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想有一定的聯(lián)系,但其效率更高。按貪心算法設(shè)計(jì)出的許多算法能導(dǎo)致最優(yōu)解。
第5章和第6章分別介紹回溯法和分支限界法。這兩章所介紹的算法適合于處理難解問題。
第7章介紹概率算法,對(duì)許多難解問題提供高效的解決途徑,是有較高實(shí)用價(jià)值的算法設(shè)計(jì)策略。
第8章介紹NP完全性理論。首先介紹計(jì)算模型、確定性和非確定性圖靈機(jī),然后進(jìn)一步介紹NP完全性理論。
第9章介紹了解NP難問題的近似算法,這是計(jì)算機(jī)算法領(lǐng)域的熱門研究課題,具有較高的實(shí)用價(jià)值。
第10章通過實(shí)例介紹算法設(shè)計(jì)中常用的算法優(yōu)化策略。
最后,在第11章介紹算法設(shè)計(jì)中較新的研究領(lǐng)域——在線算法設(shè)計(jì)。
系統(tǒng)設(shè)計(jì)與分析都應(yīng)該遵循哪些原則?
易用性原則方便上網(wǎng)客戶瀏覽和操作,最大限度地減輕后臺(tái)管理人員的負(fù)擔(dān),做到部分業(yè)務(wù)的自動(dòng)化處理。安全性原則系統(tǒng)采取全面的安全保護(hù)措施,具有防病毒感染、防黑客攻擊措施,同時(shí)在防雷擊、過載、斷電和人為破壞方...
系統(tǒng)設(shè)計(jì)與分析都應(yīng)該遵循哪些原則?
易用性原則 方便上網(wǎng)客戶瀏覽和操作,最大限度地減輕后臺(tái)管理人員的負(fù)擔(dān),做到部分業(yè)務(wù)的自動(dòng)化處理。 安全性原則 系統(tǒng)采取全面的安全保護(hù)措施,具有防病毒感染、防黑客攻擊措施,同時(shí)在防雷擊、過載、斷電...
我們河南定額模板工程量一般情況與現(xiàn)澆混凝土構(gòu)件工程量是相同的,不是按面積計(jì)算的,大多數(shù)是按混凝土體積計(jì)算的,但樓梯是按投影面積計(jì)算的。
該教材是為了適應(yīng)培養(yǎng)中國21世紀(jì)計(jì)算機(jī)各類人才的需要,結(jié)合中國高等學(xué)校教育工作的現(xiàn)狀,立足培養(yǎng)學(xué)生能跟上國際計(jì)算機(jī)科學(xué)技術(shù)的發(fā)展水平,更新教學(xué)內(nèi)容和教學(xué)方法,提高教學(xué)質(zhì)量的基礎(chǔ)上編寫而成。
該教材由王曉東編著。在編寫過程中,得到教育部高等學(xué)校計(jì)算機(jī)類專業(yè)教學(xué)指導(dǎo)委員會(huì)的支持。福州大學(xué)“211工程”計(jì)算機(jī)與信息工程重點(diǎn)學(xué)科實(shí)驗(yàn)室為該教材的寫作提供了設(shè)備與工作環(huán)境。南京大學(xué)宋方敏教授和福州大學(xué)傅清祥教授審閱了全書,提出了改進(jìn)意見。
2014年1月1日,該教材由清華大學(xué)出版社出版。
責(zé)任編輯 |
封面設(shè)計(jì) |
責(zé)任校對(duì) |
責(zé)任印制 |
---|---|---|---|
張瑞慶 |
傅瑞學(xué) |
時(shí)翠蘭 |
何芊 |
在該教材各章的論述中,首先介紹一種算法設(shè)計(jì)策略的基本思想,然后從解決計(jì)算機(jī)科學(xué)與應(yīng)用中出現(xiàn)的實(shí)際問題入手,由簡到繁地描述幾個(gè)經(jīng)典的精巧算法,同時(shí)對(duì)每個(gè)算法所需要的時(shí)間和空間進(jìn)行分析。
在為各種算法設(shè)計(jì)策略選擇用于展示其設(shè)計(jì)思想與技巧的具體應(yīng)用問題時(shí),該教材有意重復(fù)選擇某些經(jīng)典問題,使讀者能體會(huì)到一個(gè)問題可以用多種設(shè)計(jì)策略求解。同時(shí),通過對(duì)解同一問題的不同算法的比較,更容易體會(huì)到每一個(gè)具體算法的設(shè)計(jì)要點(diǎn)。隨著該教材內(nèi)容的逐步展開,讀者也將進(jìn)一步感受到綜合應(yīng)用多種設(shè)計(jì)策略可以更有效地解決問題。
該教材采用面向?qū)ο蟮腏ava語言作為表述手段,在保持Java優(yōu)點(diǎn)的同時(shí),盡量使算法的描述簡明。為了加深對(duì)知識(shí)的理解,各章配有難易適當(dāng)?shù)牧?xí)題,以適應(yīng)不同程度讀者練習(xí)的需要。
王曉東,男,1957年出生,山東人,中共黨員,現(xiàn)任福建工程學(xué)院副院長、教授、博士生導(dǎo)師。先后擔(dān)任福州大學(xué)計(jì)算機(jī)系主任、數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院院長,2007年8月起擔(dān)任泉州師范學(xué)院副院長,2014年8月起任現(xiàn)職。 2100433B
格式:pdf
大小:210KB
頁數(shù): 9頁
評(píng)分: 4.8
實(shí) 驗(yàn) 報(bào) 告 (2016/2017 學(xué)年 第一學(xué)期) 學(xué)生姓名 周文超 班級(jí)學(xué)號(hào) B14041527 學(xué)院 (系) 計(jì)算機(jī)學(xué)院、 軟件學(xué)院 專 業(yè) 軟件工程 課程名稱 算法分析與設(shè)計(jì) 實(shí)驗(yàn)名稱 分治策略 實(shí)驗(yàn)時(shí)間 2016 年 10 月 18 日 指導(dǎo)單位 計(jì)算機(jī)學(xué)院軟件教學(xué)中心 指導(dǎo)教師 季一木 2 實(shí) 驗(yàn) 報(bào) 告 實(shí)驗(yàn)名稱 分治策略 指導(dǎo)教師 季一木 實(shí)驗(yàn)類型 驗(yàn)證 實(shí)驗(yàn)學(xué)時(shí) 2 實(shí)驗(yàn)時(shí)間 2016.10.18 一、 實(shí)驗(yàn)?zāi)康暮腿蝿?wù) 1.理解分治法的算法思想, 閱讀實(shí)現(xiàn)書上已有的部分程序代碼并完善程 序,加深對(duì)分治法的算法原理及實(shí)現(xiàn)過程的理解。 2. 用分治法實(shí)現(xiàn)一組無序序列的兩路合并排序和快速排序。要求清楚 合并排序及快速排序的基本原理, 編程實(shí)現(xiàn)分別用這兩種方法將輸入的一組 無序序列排序?yàn)橛行蛐蛄泻筝敵觥?3 二、 實(shí)驗(yàn)環(huán)境 (實(shí)驗(yàn)設(shè)備 ) 算法設(shè)計(jì)與分析課本 筆記本
格式:pdf
大?。?span id="vjrhhiy" class="single-tag-height">210KB
頁數(shù): 4頁
評(píng)分: 4.5
研討式教學(xué)是本科教育中一種先進(jìn)的教學(xué)方法。在《通信網(wǎng)設(shè)計(jì)與分析》課程教學(xué)中,結(jié)合課程內(nèi)容和學(xué)生特點(diǎn),引入并靈活應(yīng)用研討式教學(xué)法,旨在培養(yǎng)學(xué)生多方面的能力,提高學(xué)生的綜合素質(zhì)。
配套教材
《計(jì)算機(jī)算法設(shè)計(jì)與分析(第5版)》有配套教材——《計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答(第5版)》 。
書名 |
ISNB |
出版社 |
出版時(shí)間 |
作者 |
---|---|---|---|---|
《計(jì)算機(jī)算法設(shè)計(jì)與分析習(xí)題解答(第5版)》 |
9787121344381 |
電子工業(yè)出版社 |
2018年10月 |
王曉東 |
《計(jì)算機(jī)算法設(shè)計(jì)與分析(第5版)》修正了第4版中發(fā)現(xiàn)的一些錯(cuò)誤,并將各章的習(xí)題分為算法分析題和算法實(shí)現(xiàn)題兩部分,增加了算法實(shí)踐性內(nèi)容,增加了有關(guān)串和序列的算法內(nèi)容。
該教材各章的論述中,首先介紹一種算法設(shè)計(jì)策略的基本思想,然后從解決計(jì)算機(jī)科學(xué)和應(yīng)用中的實(shí)際問題入手,描述幾個(gè)算法。同時(shí)對(duì)每個(gè)算法所需的時(shí)間和空間進(jìn)行分析,使讀者既能學(xué)到一些常用的算法,也能通過對(duì)算法設(shè)計(jì)策略的反復(fù)應(yīng)用,牢固掌握這些算法設(shè)計(jì)的基本策略。該教材選擇某些問題,通過對(duì)解同一問題的不同算法的比較,使讀者體會(huì)到每種算法的設(shè)計(jì)要點(diǎn)。
該教材采用面向?qū)ο蟮腃 語言作為算法描述手段,在保持C 優(yōu)點(diǎn)的同時(shí),盡量使算法描述簡明、清晰。每章的章首為學(xué)習(xí)要點(diǎn)提示,章末配有難易適度的習(xí)題,分為算法分析題和算法實(shí)現(xiàn)題兩部分,以強(qiáng)化實(shí)踐環(huán)節(jié) 。
《計(jì)算機(jī)算法設(shè)計(jì)與分析(第5版)》共9章,具體如下:
第1章介紹算法的基本概念,并對(duì)算法的計(jì)算復(fù)雜性和算法的描述做了闡述。然后圍繞算法設(shè)計(jì)常用的基本設(shè)計(jì)策略組織了第2~9章的內(nèi)容。
第2章介紹遞歸與分治策略。
第3章介紹動(dòng)態(tài)規(guī)劃算法,以具體實(shí)例講述動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想、適用性及算法的設(shè)計(jì)要點(diǎn)。
第4章介紹貪心算法,它也是一種算法設(shè)計(jì)策略,它與動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想有一定的聯(lián)系。
第5章和第6章分別介紹回溯法和分支限界法。這兩章所介紹的算法適合處理難解問題。
第7章介紹隨機(jī)化算法,對(duì)難解問題提供了解決途徑。
第8章介紹線性規(guī)劃與網(wǎng)絡(luò)流算法。許多實(shí)際應(yīng)用問題可以轉(zhuǎn)化為線性規(guī)劃和網(wǎng)絡(luò)流問題,并可用第8章中的算法有效求解。
第9章介紹在大數(shù)據(jù)和人工智能中有應(yīng)用的串和序列的算法 。