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

李恆武,單位：山東財經大學
職務、職稱：教授 機器學習與財經數據挖掘重點實驗室主任 山東省教學信息化與教學方法創新指導委員會委員
性別：男 年齡：51
專業：計算機軟件與理論
學歷：博士
研究領域：生物計算、人工智能
研究成果：著有《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圖的轉化
本節思考題
本章習題

參考文獻