演演算法設計與分析

為了適應培養我國21世紀計算機各類人才的需要，結合我國高等學校教育工作的現狀，立足培養學生能跟上國際計算機科學技術的發展水平，更新教學內容和教學方法，提高教學質量，本書以演演算法設計策略為知識單元，系統地介紹計算機演演算法的設計方法與分析技巧，以期為計算機科學與技術學科的學生提供廣泛而堅實的計算機演演算法基礎知識。

另有配套的《演演算法設計與分析習題解答（第2版）》，對本書的全部習題做了詳盡的解答。

本書封面貼有清華大學出版社防偽標籤，無標籤者不得銷售。

國家精品課程配套教材，根據教育部高教司主持評審的《中國計算機科學與技術學科教程2002》組織編寫，與美國ACM和IEEE/CSComputingCurricula2005同步。

王曉東，男，1957年3月出生，福州大學計算機系教授，福建省計算機學會理事長。研究領域是演演算法設計與演演算法評價，基於計算機網路和信息安全的大規模問題求解演演算法與數據結構，信息可視化技術。幾何計算，并行和分散式演演算法設計，計算複雜性理論。先後主持了與演演算法設計與分析有關的國家自一然科學基金項目、國家優秀留學回國人一員基金項目、福建省傑出人才基金項目和省自然科學基金項目等7個研究課題；獲得國家科技進步二等獎1項，省科技進步二等獎3項。主持國家精品課程“演演算法與數據結構”，和福建省優質碩士學位課程“演演算法設計與分析”的課程建設，獲2005年福建省教學成果一等獎。在國內外重要學術刊物上發表有創見性的論文50餘篇；正式出版《演演算法設計與分析》等學術著作7部，在演演算法複雜性研究方面取得了一系列理論研究成果和應用成果。例如，在對著名的凸殼問題的計算複雜性研究成果中推廣了關於判定樹模型下問題的計算複雜性下界的著名的Ben-Or，並應用於分析凸殼問題的計算複雜性，在較_般的情況下改進和完善了國際演演算法界知名學者Aggarwal、Steele和Yao等提出的關於凸殼問題計算複雜性下界的結果。研究成果得到同行專家的好評並被國內權威刊物所引用。

第1章演演算法引論

1.1演演算法與程序

1.2表達演演算法的抽象機制

1.3描述演演算法

1.4演演算法複雜性分析

小結

習題

第2章遞歸與分治策略

2.1遞歸的概念

2.2分治法的基本思想

2.3二分搜索技術

2.4大整數的乘法

2.5Strassen矩陣乘法

2.6棋盤覆蓋

2.7合併排序

2.8快速排序

2.9線性時間選擇

2.10最接近點對問題

2.11循環賽日程表

小結

習題

第3章動態規劃

3.1矩陣連乘問題

3.2動態規劃演演算法的基本要素

3.3最長公共子序列

3.4凸多邊形最優三角剖分

3.5多邊形遊戲

3.6圖像壓縮

3.7電路布線

3.8流水作業調度

3.90-1背包問題

3.10最優二叉搜索樹

小結

習題

第4章貪心演演算法

4.1活動安排問題

4.2貪心演演算法的基本要素

4.2.1貪心選擇性質

4.2.2最優子結構性質

4.2.3貪心演演算法與動態規劃演演算法的差異

4.3最優裝載

4.4哈夫曼編碼

4.4.1前綴碼

4.4.2構造哈夫曼編碼

4.4.3哈夫曼演演算法的正確性

4.5單源最短路徑

4.5.1演演算法基本思想

4.5.2演演算法的正確性和計算複雜性

4.6最小生成樹

4.6.1最小生成樹性質

4.6.2Prim演演算法

4.6.3Kruskal演演算法

4.7多機調度問題

4.8貪心演演算法的理論基礎

4.8.1擬陣

4.8.2帶權擬陣的貪心演演算法

4.8.3任務時間表問題

小結

習題

第5章回溯法

第6章分支限界法

第7章概率演演算法

第8章NP完全性理論

第9章近似演演算法

第10章演演算法優化策略

第11章在線演演算法設計

辭彙索引

參考文獻