算法設計與分析（微課視頻版）

本書主要取材於算法設計與分析領域經典和發展潮流方面的內容，包括非常經典的算法設計技術，例如，遞歸、分治算法、動態規劃、貪心算法、圖算法、分支限界、回溯； 也包括一些高級的算法設計，例如，網絡流和匹配、線性規劃、啟發式搜索。在算法分析方面，本書介紹了概率分析、分攤分析和實驗分析方法。在算法理論方面，本書介紹了問題的下界、算法的正確性證明，以及NP完全理論等內容。 本書還包括大量的問題實例，給出了相應的設計與分析方法，並精選了一些習題，供讀者練習，以鞏固所學的算法。在工業應用領域，許多實際問題和疑難問題都需要有效的求解算法，因此，本書提供了設計有效算法的基礎，以及大量可供選擇的解決途徑。 本書可作為電腦科學與技術系、數學系、軟件學院等專業和學院的本科生及研究生的教材，也可作為有志參加程序設計競賽的學生進行學習和訓練的參考書。

目錄

教學大綱

教學課件

程序源碼

第1章概念入門

1．1問題模型

1．2算法的概念

1．3算法的正確性

1．4算法的效率

1．5問題的下界

1．6小結

習題

實驗題

第2章漸近符號

2．1Θ符號

2．2O符號

2．3Ω符號

2．4漸近符號的性質

2．5常用函數的直觀含義

2．6小結

習題

第3章算法分析方法

3．1概率分析

3．2分攤分析

3．2．1合計方法

3．2．2記賬方法

3．2．3勢能方法

3．3實驗分析

3．4小結

習題

第4章遞歸算法

4．1算法思想

4．1．1遞歸算法的應用

4．1．2遞歸與迭代

4．2遞歸方程的求解

4．2．1替換法

4．2．2遞歸樹法

4．2．3公式法

4．3多項式求值實驗

4．4小結

習題

實驗題

第5章分治算法

5．1算法思想

5．2合並排序

5．3快速排序

5．4大整數乘法

5．5矩陣乘法

5．6殘缺棋盤游戲

5．7快速傅里葉變換

5．8小結

習題

實驗題

第6章動態規劃算法

6．1算法思想

6．2裝配線調度問題

6．3矩陣鏈乘法問題

6．4最長公共子序列問題

6．50/1背包問題

6．6最優二叉搜索樹問題

6．7動態規劃的基本性質

6．8小結

習題

實驗題

第7章貪心算法

7．1算法思想

7．2任務選擇問題

7．3背包問題

7．4哈夫曼編碼問題

7．5緩存維護問題

7．6任務選擇問題實驗

7．7小結

習題

實驗題

第8章圖算法

8．1圖的搜索問題

8．1．1寬度優先搜索

8．1．2深度優先搜索

8．2最小生成樹問題

8．2．1Kruskal算法

8．2．2Prim算法

8．3最短路徑問題

8．3．1單個源點的最短路徑問題

8．3．2所有點對的最短路徑問題

8．4小結

習題

實驗題

第9章網絡流與匹配

9．1最大流問題

9．1．1FordFulkerson算法

9．1．2最短路徑增廣算法

9．1．3Dinic 算法

9．1．4MPM 算法

9．1．5最大流問題的變形

9．2最小費用流問題

9．2．1消除迴路算法

9．2．2最小費用路算法 

9．2．3最小費用路算法的改進

9．3匹配問題

9．3．1二分圖匹配

9．3．2一般圖的匹配

9．4小結

習題

實驗題

第10章線性規劃

10．1線性規劃問題

10．1．1線性規劃問題的標準形式

10．1．2線性規劃問題的鬆弛形式

10．2求解算法

10．2．1圖解法

10．2．2單純形算法

10．3對偶

10．4小結

習題

實驗題

第11章NP完全理論

11．1判定問題

11．2P和NP

11．3NPC

11．3．1NPC的定義

11．3．2電路可滿足性問題

11．4NPC的證明

11．4．1可滿足性問題

11．4．23CNF可滿足性問題

11．4．3團問題

11．4．4頂點覆蓋問題

11．5其他NP完全問題

11．6小結

習題

第12章回溯算法

12．1算法思想

12．2裝載問題

12．30/1背包問題

12．4著色問題

12．5n皇後問題

12．6旅行商問題

12．7流水作業調度問題

12．8零件切割問題

12．9小結

習題

實驗題

第13章分支限界算法

13．1算法思想

13．2裝載問題

13．30/1背包問題

13．4可滿足性問題

13．5旅行商問題

13．6流水作業調度問題

13．70/1背包問題實驗

13．8小結

習題

實驗題

第14章啟發式搜索

14．1算法思想

14．2A*搜索算法

14．2．1最短路徑問題

14．2．2八數字問題

14．3博弈搜索算法

14．3．1α和β剪支

14．3．2分硬幣游戲

14．3．3井字博弈

14．4小結

習題

實驗題

參考文獻