算法設計與應用

林海，現任武漢大學-國家網絡安全學院副教授，先後畢業於法國巴黎第六大學(碩士)和法國國立高等通信學校(博士)，並取得了計算機網絡博士學位，是武漢大學作為人才引進的優秀青年學術骨幹。在加入武漢大學之前，曾經先後在法國電信 Orange 研究院從事博士後研究和在中興通訊歐洲研究所(巴黎)從事系統工程師工作。本書作者一直從事算法方面的教學和研究，有著多年本科生《算法設計與分析》和研究生《高級算法》教學經驗。

前言
第1章 算法概念和基礎
1.1 基本概念
1.1.1 搜索
1.1.2 排序
1.2 算法覆雜度
1.2.1 時間覆雜度
1.2.2 算法的時間覆雜度
1.2.3 空間覆雜度
1.3 數據結構
1.3.1 堆
1.3.2 不相交集
1.4 本章小結
1.5 習題
第2章 排序
2.1 比較排序
2.1.1 冒泡排序
2.1.2 堆排序
2.1.3 插入排序
2.1.4 歸並排序
2.2 線性排序
2.2.1 桶排序
2.2.2 計數排序
2.2.3 基數排序
2.3 本章小結
2.4 習題
第3章 遞歸
3.1 基本概念
3.2 遞歸例子
3.2.1 生成排列
3.2.2 整數劃分
3.3 覆雜度的遞歸方法求解
3.3.1 展開法
3.3.2 代入法
3.3.3 遞歸樹方法
3.3.4 主方法
3.3.5 幾種遞歸形式的覆雜度分析
3.4 本章小結
3.5 習題
第4章 分治
4.1 基本概念
4.2 快速排序
4.3 最大子數組問題
4.4 最近點對問題
4.5 棋盤覆蓋問題
4.6 尋找第k小元素
4.7 分治在傅里葉變換中的應用*
4.8 本章小結
4.9 習題
第5章 動態規劃
5.1 基本概念和步驟
5.2 最大子數組問題
5.3 0-1背包問題
5.4 旅行商問題
5.5 最長公共子序列
5.6 斯坦納最小樹*
5.7 狀態壓縮動態規劃
5.7.1 集合狀態壓縮
5.7.2 空間狀態壓縮
5.8 動態規劃和貝爾曼方程*
5.9 本章小結
5.10 習題
第6章 貪心
6.1 基本概念
6.2 小數背包和0-1背包
6.2.1 小數背包貪心算法的正確性證明
6.2.2 0-1背包貪心算法
6.3 最小生成樹
6.3.1 Kruskal算法
6.3.2 Prim算法
6.4 霍夫曼編碼
6.5 貪心算法在穩定匹配中的應用*
6.6 本章小結
6.7 習題
第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 Dijkstra算法
7.3.2 Bellman-Ford算法
7.3.3 SPFA算法
7.3.4 差分約束系統
7.4 多源最短路徑
7.4.1 Floyd算法（弗洛伊德算法）
7.4.2 Johnson算法
7.5 最短路徑在網絡路由中的應用*
7.6 本章小結
7.7 習題
第8章 回溯和分支限界
8.1 回溯的基本方法
8.1.1 回溯法的基本步驟
8.1.2 回溯法的通用框架
8.2 騎士巡遊問題
8.3 0-1背包問題
8.4 最大團問題
8.4.1 最大團的回溯算法
8.4.2 Bron-Kerbosch算法
8.5 分支限界法
8.5.1 基本方法
8.5.2 旅行商問題
8.5.3 任務指派問題
8.6 分支限界在流水線作業調度中的應用*
8.7 本章小結
8.8 習題
第9章 匹配與指派
9.1 基本概念
9.2 基於圖的匈牙利算法
9.2.1 匹配問題
9.2.2 指派問題
9.3 基於矩陣的匈牙利算法
9.3.1 算法流程
9.3.2 最大化指派
9.4 匹配算法在多目標跟蹤中的應用*
9.5 本章小結
9.6 習題
參考文獻