《算法設計與分析習題解答》是清華大學出版社出版圖書，該書介紹對《算法設計與分析（第2版）》的較深入的擴展，許多在主教材中無法講述的、較深入的主題通過習題的形式展現出來。
基本介紹
- 書名：算法設計與分析習題解答
- 作者：王曉東
- ISBN：9787302167198
- 頁數：420頁
- 出版社：清華大學出版社
- 出版時間：2008年2月2日
- 開本： 16
- 正文語種：簡體中文
- 版次：第2版
作者簡介,內容簡介,目錄,
作者簡介
王曉東，男，1957年3月出生，福州大學計算機系教授，福建省計算機學會理事長。研究領域是算法設計與算法評價，基於計算機網路和信息安全的大規模問題求解算法與數據結構，信息可視化技術，幾何計算，並行和分散式算法設計，計算複雜性理論。先後主持了與算法設計與分析有關的國家自然科學基金項目、國家優秀留學回國人員基金項目、福建省傑出人才基金項目和省自然科學基金項目等7個研究課題；獲得國家科技進步二等獎1項，省科技進步二等獎3項。主持國家精品課程算法與數據結構和算法設計與分析的課程建設，獲福建省教學成果一等獎。在國內外重要學術刊物上發表有創見性的論文50餘篇；出版《算法設計與分析》等學術著作7部，在算法複雜性研究方面取得了一系列理論研究和套用成果。例如，在對著名的凸殼問題的計算複雜性研究成果中推廣了關於判定樹模型下問題的計算複雜性下界著名的Ben-Or定理，並套用於分析凸殼問題的計算複雜性，在較一般的情況下改進和完善了國際算法界知名學者Aggarwal，Steele和Yao等提出的關於凸殼問題計算複雜性下界的結果。研究成果得到國內外同行專家的好評並被國內權威刊物所引用。
內容簡介
為了加強學生靈活運用算法設計策略解決實際問題的能力，《算法設計與分析習題解答(第2版)》將主教材中的許多習題改造成算法實現題，要求學生不僅設計出解決具體問題的算法，而且能夠上機實現。作者的教學實踐反映出這類算法實現題的教學效果非常好。作者還結合國家精品課程建設，進行了教材的立體化開發，包括主教材、輔助教材、實驗與設計、電子課件和教學網站建設。
目錄
習題1-1 實參交換1
習題1-2 方法頭簽名1
習題1-3 數組排序判定1
習題1-4 函式的漸近表達式2
習題1-5 ?O(1)?和?O(2)?的區別2
習題1-7 按漸近階排列表達式2
習題1-8 算法效率2
習題1-9 硬體效率3
習題1-10 函式漸近階3
習題1-11 ?n?!的階4
習題1-12 平均情況下的計算時間複雜性4
算法實現題1-1 統計數字問題4
算法實現題1-2 字典序問題5
算法實現題1-3 最多約數問題6
算法實現題1-4 金幣陣列問題8
算法實現題1-5 最大間隙問題11第2章 遞歸與分治策略14
習題2-1 Hanoi 塔問題的非遞歸算法14
算法實現題2-1 輸油管道問題（習題2-30) 49
習題3-1 最長單調遞增子序列76
習題3-2 最長單調遞增子序列的?O(n?log?n)?算法77
習題3-7 漂亮列印78
習題3-11 整數線性規劃問題79
習題3-12 二維背包問題80
習題3-14 Ackermann函式81
習題3-17 最短行駛路線83
習題3-19 最優旅行路線83
算法實現題3-1 獨立任務最優調度問題（習題3-3) 83
算法實現題3-2 最少硬幣問題（習題3-4) 85
算法實現題3-3 序關係計數問題（習題3-5) 86
算法實現題3-4 多重冪計數問題（習題3-6) 87
習題4-2 活動安排問題的貪心選擇123
算法實現題4-1 會場安排問題（習題4-1) 128
習題5\|1 裝載問題改進回溯法（一）153
習題5\|2 裝載問題改進回溯法（二）154
習題5\|4 0-1背包問題的最優解155
習題5\|5 最大團問題的疊代回溯法156
習題5\|7 旅行售貨員問題的費用上界157
習題5\|8 旅行售貨員問題的上界函式158
算法實現題5-1 子集和問題（習題5-3) 159
習題6-1 0-1背包問題的棧式分支限界法229
習題6-2 用最大堆存儲活結點的優先佇列式分支限界法231
習題6-3 團頂點數的上界234
習題6-4 團頂點數改進的上界235
習題6-5 修改解旅行售貨員問題的分支限界法235
習題6-6 解旅行售貨員問題的分支限界法中保存已產生的排列樹237
習題6-7 電路板排列問題的佇列式分支限界法239
算法實現題6-1 最小長度電路板排列問題一（習題6-8) 241
習題7-1 模擬常態分配隨機變數296
算法實現題7-1 模平方根問題（習題7-10) 307
習題8-1 RAM和RASP程式322
習題9-1 平面圖著色問題的絕對近似算法336
算法實現題9-1 旅行售貨員問題的近似算法（習題9-9) 346
習題10-1 算法obst的正確性365
習題10-2 矩陣連乘問題的?O(n?2)?時間算法365
習題10-6 貨物儲運問題的費用371
習題10-7 Garsia算法371
第11章 線上算法設計410
習題11-1 線上算法LFU的競爭性410
習題11-4 多讀寫頭磁碟問題的線上算法410
習題11-6 帶權頁調度問題410
算法實現題11-1 最優頁調度問題（習題11-2) 411
算法實現題11-2 線上LRU頁調度（習題11-3) 414
算法實現題11-3 ?k?服務問題（習題11-5) 416
參考文獻422
