算法設計與分析

王秋芬，女，1978-，碩士研究生，副教授。
研究方向為計算機軟件理論、算法、大數據，主講《操作系統》、《數據結構》、《算法設計與分析》等課程。
從教以來，獲校級教學技能競賽一等獎、省級教學技能競賽二等獎；以第一作者發表論文20餘篇，出版《算法設計與分析》、《算法設計藝術》等3部著作；主持、參與省級項目6項，主持課程與教材建設項目5項；獲省部級以上獎勵5項；已獲授權國家發明專利4項。

目錄

第1章算法概述
1.1什麼是算法
1.2為什麼學習算法
1.3算法的描述方式
1.4算法設計的一般過程
1.5算法分析
1.5.1算法分析的概念
1.5.2時間複雜度和空間複雜度
1.5.3漸近複雜性態
1.5.4漸近意義下的記號
1.5.5算法的運行時間T(n)建立的依據
1.5.6算法所佔用的空間S(n)建立的依據
1.6遞推方程求解方法
1.6.1疊代法
1.6.2遞歸樹
1.6.3差消法
1.6.4主方法

第2章貪心算法——貪心不足
2.1概述
2.1.1貪心算法的本質
2.1.2貪心算法的基本要素
2.2活動安排問題
2.2.1問題分析——貪心策略
2.2.2算法設計
2.2.3實例構造
2.2.4算法分析
2.2.5Python實戰
2.3單源最短路徑問題
2.3.1問題分析——貪心策略
2.3.2算法設計
2.3.3實例構造
2.3.4算法分析
2.3.5Python實戰
2.4哈夫曼編碼
2.4.1問題分析——貪心策略
2.4.2算法設計
2.4.3實例構造
2.4.4算法分析
2.4.5Python實戰
2.5最小生成樹——Prim算法
2.5.1問題分析——貪心策略
2.5.2算法設計
2.5.3實例構造
2.5.4算法分析
2.5.5Python實戰
2.6最小生成樹——Kruskal算法
2.6.1問題分析——貪心策略
2.6.2算法設計
2.6.3實例構造
2.6.4算法分析
2.6.5Python實戰
2.7背包問題
2.7.1問題分析——貪心策略
2.7.2算法設計
2.7.3實例構造
2.7.4算法分析
2.7.5Python實戰

第3章分治算法——分而治之
3.1概述
3.1.1分治算法的本質
3.1.2分治算法的求解步驟
3.2二分查找
3.2.1問題分析——分與治的方法
3.2.2算法設計
3.2.3實例構造
3.2.4算法分析
3.2.5Python實戰
3.3選第二大元素
3.3.1問題分析——分與治的方法
3.3.2算法設計
3.3.3實例構造
3.3.4算法分析
3.3.5Python實戰
3.4循環賽日程表
3.4.1問題分析——分與治的方法
3.4.2算法設計
3.4.3實例構造
3.4.4算法分析
3.4.5Python實戰
3.5合併排序
3.5.1問題分析——分與治的方法
3.5.2算法設計
3.5.3實例構造
3.5.4算法分析
3.5.5Python實戰
3.6快速排序
3.6.1問題分析——分與治的方法
3.6.2算法設計
3.6.3實例構造
3.6.4算法分析
3.6.5Python實戰
3.7線性時間選擇——找第k小問題
3.7.1問題分析——分與治的方法
3.7.2算法設計
3.7.3實例構造
3.7.4算法分析
3.7.5Python實戰

第4章動態規劃
4.1概述
4.1.1動態規劃的基本思想
4.1.2動態規劃的求解步驟
4.1.3動態規劃的基本要素
4.2矩陣連乘問題
4.2.1問題分析——遞歸關係
4.2.2算法設計
4.2.3實例構造
4.2.4算法分析
4.2.5Python實戰
4.3凸多邊形最優三角剖分
4.3.1問題分析——遞歸關係
4.3.2算法設計
4.3.3實例構造
4.3.4算法分析
4.3.5Python實戰
4.4最長公共子序列問題
4.4.1問題分析——遞歸關係
4.4.2算法設計
4.4.3實例構造
4.4.4算法分析
4.4.5Python實戰
4.5加工順序問題
4.5.1問題分析——遞歸關係
4.5.2算法設計
4.5.3實例構造
4.5.4算法分析
4.5.5Python實戰
4.601背包問題
4.6.1問題分析——遞歸關係
4.6.2算法設計
4.6.3實例構造
4.6.4算法分析
4.6.5算法的改進
4.6.6Python實戰
4.7最優二叉查找樹
4.7.1問題分析——遞歸關係
4.7.2算法設計
4.7.3實例構造
4.7.4算法分析
4.7.5Python實戰

第5章回溯法——深度優先搜索
5.1概述
5.2典型的解空間結構
5.2.1子集樹
5.2.2排列樹
5.2.3滿m叉樹
5.301背包問題——子集樹
5.3.1問題分析——解空間及搜索條件
5.3.2算法設計
5.3.3實例構造
5.3.4算法的改進
5.3.5算法分析
5.3.6Python實戰
5.4最大團問題——子集樹
5.4.1問題分析——解空間及搜索條件
5.4.2算法設計
5.4.3實例構造
5.4.4算法分析
5.4.5Python實戰
5.5批處理作業調度問題——排列樹
5.5.1問題分析——解空間及搜索條件
5.5.2算法設計
5.5.3實例構造
5.5.4算法分析
5.5.5Python實戰
5.6旅行商問題——排列樹
5.6.1問題分析——解空間及搜索條件
5.6.2算法設計
5.6.3實例構造
5.6.4算法分析
5.6.5Python實戰
5.7圖的m著色問題——滿m叉樹
5.7.1問題分析——解空間及搜索條件
5.7.2算法設計
5.7.3實例構造
5.7.4算法分析
5.7.5Python實戰
5.8最小質量機器設計問題——滿m叉樹
5.8.1問題分析——解空間及搜索條件
5.8.2算法設計
5.8.3實例構造
5.8.4算法分析
5.8.5Python實戰

第6章分支限界法——寬度優先或最小耗費(最大效益)優先搜索
6.1分支限界法的基本思想
6.201背包問題
6.3旅行商問題
6.4佈線問題
6.4.1問題分析——解空間及搜索條件
6.4.2算法設計
6.4.3實例構造
6.4.4算法分析
6.4.5Python實戰
6.5分支限界法與回溯法的比較

第7章線性規劃問題與網絡流
7.1線性規劃問題
7.1.1一般線性規劃問題的描述
7.1.2標準型線性規劃問題的描述
7.1.3標準型線性規劃問題的單純形算法
7.2最大網絡流
7.2.1基本概念
7.2.2增廣路算法
7.2.3最大網絡流的變換與應用
7.3最小費用最大流
7.3.1基本概念
7.3.2消圈算法
7.3.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.4拉斯維加斯算法
8.4.1整數因子分解
8.4.2n皇後問題
8.5舍伍德算法
8.5.1隨機快速排序
8.5.2線性時間選擇

第9章NP完全理論
9.1易解問題和難解問題
9.2P類和NP類問題
9.2.1P類問題
9.2.2NP類問題
9.2.3P類問題和NP類問題的關係
9.3NP完全問題
9.3.1多項式變換技術
9.3.2典型的NP完全問題
9.4NP完全問題的近似算法
9.4.1頂點覆蓋問題
9.4.2裝箱問題
9.4.3旅行商問題TSP
9.4.4集合覆蓋問題

參考文獻