算法分析與設計

李恒武,博士，教授，山東省機器學習與財經數據挖掘重點實驗室主任，山東省教學信息化與教學方法創新指導委員會委員。著有《web技術》《web技術設計與開發》《雲計算機與大數據的應用》等，發表高水平論文40余篇，主講《算法分析與設計》被評為線上一流課程和在線開放精品課程

 

目錄

 

 

 

 

 

 

第1章算法與問題

 

1.1穩定匹配問題

 

1.1.1問題分析

 

1.1.2穩定匹配算法

 

1.1.3正確性證明

 

1.1.4算法實現

 

1.1.5算法總結

 

1.2算法概述

 

1.2.1算法的概念

 

1.2.2算法的性質

 

1.2.3算法與程序

 

1.2.4算法與問題

 

1.2.5問題求解

 

1.3問題變換

 

1.3.1大學入學申請

 

1.3.2問題變換

 

習題一

 

第2章算法分析

 

2.1算法分析概述

 

2.1.1算法選擇

 

2.1.2分析方法

 

2.1.3有效算法

 

2.1.4事後統計

 

2.1.5算法分析總結

 

2.2漸近復雜度

 

2.2.1上界

 

2.2.2下界

 

2.2.3緊界

 

2.2.4高階和低階

 

2.2.5性質

 

2.3復雜度比較

 

2.3.1階的高低

 

2.3.2比較方法

 

2.4實例分析

 

2.4.1非遞歸算法分析

 

2.4.2分析實例

 

2.5時空均衡

 

2.5.1空間復雜度

 

2.5.2預處理

 

2.5.3預構造

 

2.5.4圖的遍歷

 

習題二

 

 

 

 

 

第3章枚舉算法

 

3.1枚舉與優化

 

3.1.1蠻力算法

 

3.1.2枚舉算法概述

 

3.1.3枚舉優化

 

3.2組合與排列

 

3.2.1排列

 

3.2.2子集

 

習題三

 

第4章貪心算法

 

4.1概述

 

4.1.1部分背包問題

 

4.1.2貪心算法概述

 

4.2基本要素

 

4.2.1性質

 

4.2.2最優解證明

 

4.2.3預處理技巧

 

4.3區間問題

 

4.3.1區間調度問題

 

4.3.2區間劃分問題

 

4.3.3區間選點問題

 

4.3.4區間覆蓋問題

 

4.4MST問題

 

4.4.1MST特性

 

4.4.2Prim算法

 

4.4.3Kruskal算法

 

4.4.4逆刪除算法

 

4.4.5MST唯一性

 

4.5哈夫曼編碼

 

4.5.1哈夫曼算法

 

4.5.2木板問題

 

習題四

 

第5章遞推算法

 

5.1遞推算法概述

 

5.1.1遞推

 

5.1.2遞推與遞歸

 

5.1.3遞推與循環

 

5.1.4遞歸與非遞歸

 

5.1.5切分問題

 

5.1.6獄吏問題

 

5.2倒推算法

 

5.2.1倒推與應用

 

5.2.2約瑟夫問題

 

5.3遞推求解

 

5.3.1快速排序

 

5.3.2遞推方程求解

 

習題五

 

第6章分治算法

 

6.1分治算法概述

 

6.1.1設計思想

 

6.1.2合並排序 

 

6.1.3基本特點

 

6.2分治類型

 

6.2.1不相似分治

 

6.2.2不獨立分治

 

6.2.3三分法

 

6.2.4減治法

 

6.2.5排序算法

 

6.3減少子問題個數

 

6.3.1二分搜索

 

6.3.2大整數乘法

 

6.3.3Strassen矩陣乘法

 

6.4改進分治均衡度

 

6.4.1隨機快速排序

 

6.4.2線性時間選擇

 

6.5減少分解合並時間

 

6.5.1最接近點對問題

 

6.5.2計數逆序問題

 

習題六

 

第7章動態規劃算法

 

7.1動態規劃

 

7.1.1兔子序列

 

7.1.2賦權區間調度問題

 

7.1.3基本性質

 

7.1.4求解步驟

 

7.2決策與遞推關系

 

7.2.1數字三角形 

 

7.2.2多階段決策與遞推關系

 

7.3背包問題

 

7.3.101背包問題

 

7.3.2恰好裝滿背包

 

7.3.3完全背包

 

7.3.4多重背包

 

7.3.5混合背包

 

7.4區間動態規劃

 

7.4.1矩陣相乘

 

7.4.2矩陣連乘

 

7.5DAG動態規劃

 

7.5.1拓撲排序

 

7.5.2嵌套矩形

 

7.5.3最長不降子序列

 

7.5.4硬幣問題

 

7.6樹圖動態規劃

 

7.6.1最短路徑問題

 

7.6.2FloydWarshall算法

 

7.6.3樹狀動態規劃

 

7.7序列相似度

 

7.7.1LCS問題

 

7.7.2序列比對

 

7.7.3動態規劃復雜度

 

習題七

 

第8章回溯算法

 

8.1裝載問題 

 

8.1.1裝載問題分析

 

8.1.2裝載問題的回溯算法

 

8.2旅行商問題 

 

8.2.1旅行商問題分析

 

8.2.2旅行商問題的回溯算法

 

8.3基本特征

 

8.3.1解題步驟

 

8.3.2回溯方式

 

8.3.3解空間結構

 

8.3.4算法效率

 

8.401背包問題

 

8.4.101背包問題的回溯算法

 

8.4.2改進上界函數

 

8.5n皇後問題

 

8.5.1n皇後問題分析

 

8.5.2n皇後問題的回溯算法

 

8.6效率改進與估計

 

8.6.1效率估計

 

8.6.2效率改進

 

8.6.3適用條件

 

習題八

 

第9章分支限界

 

9.101背包問題

 

9.1.101背包問題的隊列式分支限界

 

9.1.201背包問題的優先隊列式分支限界

 

9.1.301背包問題的優先級改進

 

9.2旅行商問題

 

9.2.1旅行商問題的優先隊列式分支限界

 

9.2.2旅行商問題的優先級改進

 

9.3分支限界算法

 

9.3.1分支限界方式

 

9.3.2分支限界與回溯算法

 

9.3.3剪枝函數

 

9.3.4雙向廣度搜索

 

9.4算法總結

 

習題九

 

第10章網絡流算法

 

10.1最大流和最小割

 

10.1.1最大流

 

10.1.2最小割

 

10.1.3最大流算法

 

10.2最大流算法改進

 

10.2.1容量縮放算法

 

10.2.2最短增廣路算法

 

10.3預流推進算法

 

10.4最大流算法推廣

 

10.4.1多源點多匯點問題

 

10.4.2無向圖的最大流問題

 

10.4.3頂點容量限制問題

 

10.4.4帶需求的流通問題

 

10.4.5帶需求和下界的流通

 

10.4.6調查設計

 

10.5最小費用流

 

10.5.1最小費用路算法

 

10.5.2最小逃逸問題

 

10.6二分測試與二分匹配

 

10.6.1二分測試

 

10.6.2二分匹配

 

10.6.3網絡流算法

 

10.6.4匈牙利算法

 

10.7應用實例

 

10.7.1二分匹配公式

 

10.7.2二分匹配應用

 

10.8二分圖最佳匹配

 

習題十

 

第11章隨機算法

 

11.1隨機算法概述

 

11.1.1確定性算法和隨機算法

 

11.1.2隨機算法分類

 

11.1.3偽隨機數

 

11.1.4模運算

 

11.2數值隨機算法

 

11.2.1計算π值

 

11.2.2計算定積分

 

11.3舍伍德算法

 

11.3.1隨機快速排序算法

 

11.3.2隨機選擇算法

 

11.3.3隨機洗牌算法

 

11.3.4搜索有序表

 

11.4拉斯維加斯算法

 

11.5蒙特卡洛算法

 

11.5.1主元素問題

 

11.5.2素數檢測

 

習題十一

 

第12章計算復雜性

 

12.1P與NP

 

12.1.1易解與難解問題

 

12.1.2判定與優化問題

 

12.1.3計算模型

 

12.1.4P類

 

12.1.5NP類

 

12.1.6COOK歸約與KARP歸約

 

12.1.7多項式時間變換

 

12.2NP完全問題

 

12.2.1NP完全

 

12.2.2COOK定理

 

12.3NP完全問題證明

 

12.3.1局部替換技術

 

12.3.2分支設計技術

 

12.3.3限制技術

 

12.4NP完全問題求解

 

12.4.1求解策略

 

12.4.2子問題求解

 

12.4.3參數化算法

 

12.4.4圖著色問題

 

12.5coNP和PSPACE

 

12.5.1coNP

 

12.5.2PSPACE

 

習題十二

 

第13章近似算法

 

13.1絕對近似算法

 

13.2相對近似算法

 

13.2.1相對近似算法概述

 

13.2.2貪心

 

13.2.3組合技術

 

13.2.4定價法

 

13.2.5線性規劃和舍入

 

13.3多項式時間近似方案

 

13.3.101背包問題的近似算法

 

13.3.201背包問題的多項式時間近似方案 

 

13.3.301背包問題的完全多項式時間近似方案

 

習題十三

 

第14章圖算法

 

14.1基本概念

 

14.1.1無向圖與有向圖

 

14.1.2握手定理

 

14.1.3圖的表示

 

14.1.4路徑

 

14.1.5賦權圖

 

14.2可圖性

 

14.2.1可圖性概述

 

14.2.2圖的同構

 

14.3圖的遍歷

 

14.3.1深度優先搜索

 

14.3.2廣度優先搜索

 

14.4無向連通圖

 

14.4.1無向連通圖概述

 

14.4.2生成樹

 

14.4.3圖的連通度

 

14.4.4割點與橋

 

14.4.5雙連通分量

 

14.4.6點連通度

 

14.4.7邊連通度

 

14.5有向連通圖

 

14.5.1有向連通圖概述

 

14.5.2強連通分量

 

14.5.3拓撲排序

 

14.5.4傳遞閉包

 

14.6可行遍性

 

14.6.1無向歐拉圖

 

14.6.2有向歐拉圖

 

14.6.3歐拉圖判定

 

14.6.4歐拉回路

 

14.6.5哈密頓圖

 

14.7平面圖

 

14.7.1平面圖概述

 

14.7.2圖著色問題

 

14.7.3圖著色算法

 

14.7.4圖的轉化

 

習題十四

 

第15章字符串匹配算法

 

15.1單模式串匹配算法

 

15.1.1字符串

 

15.1.2KMP算法

 

15.1.3RK算法

 

15.1.4BM算法

 

15.1.5Sunday算法

 

15.2多模式串匹配算法

 

15.2.1Trie樹

 

15.2.2後綴Trie的模式匹配算法  

 

15.2.3AC自動機

 

習題十五

 

 

參考文獻