計算機算法設計與分析（第6版）

目 錄
第1章 算法概述 001
1.1 算法與程序 001
1.2 算法復雜性分析 001
1.3 NP完全性理論 004
算法分析題1 006
算法實現題1 007
第2章 遞歸與分治策略 010
2.1 遞歸的概念 010
2.2 分治法的基本思想 014
2.3 二分搜索技術 015
2.4 大整數的乘法 016
2.5 斯特拉森矩陣乘法 017
2.6 棋盤覆蓋 018
2.7 合並排序 020
2.8 快速排序 022
2.9 線性時間選擇 024
2.10 最接近點對問題 026
2.11 循環賽日程表 032
算法分析題2 033
算法實現題2 037
第3章 動態規劃 042
3.1 矩陣連乘問題 042
3.2 動態規劃算法的基本要素 046
3.3 最長公共子序列 049
3.4 最大子段和 052
3.5 凸多邊形最優三角剖分 057
3.6 多邊形遊戲 059
3.7 圖像壓縮 062
3.8 電路布線 064
3.9 流水作業調度 065
3.10 0-1背包問題 068
3.11 最優二叉搜索樹 072
算法分析題3 074
算法實現題3 074
第4章 貪心算法 086
4.1 活動安排問題 086
4.2 貪心算法的基本要素 088
4.3 最優裝載 091
4.4 哈夫曼編碼 092
4.5 單源最短路徑 095
4.6 最小生成樹 097
4.7 多機調度問題 100
算法分析題4 102
算法實現題4 102
第5章 回溯法 108
5.1 回溯法的算法框架 108
5.2 裝載問題 112
5.3 批處理作業調度 118
5.4 符號三角形問題 120
5.5 n後問題 122
5.6 0-1背包問題 124
5.7 最大團問題 127
5.8 圖的m著色問題 128
5.9 旅行售貨員問題 131
5.10 圓排列問題 132
5.11 電路板排列問題 134
5.12 連續郵資問題 137
5.13 回溯法的效率分析 139
算法分析題5 141
算法實現題5 141
第6章 分支限界法 151
6.1 分支限界法的基本思想 151
6.2 單源最短路徑問題 153
6.3 裝載問題 155
6.4 布線問題 161
6.5 0-1背包問題 163
6.6 最大團問題 167
6.7 旅行售貨員問題 169
6.8 電路板排列問題 171
6.9 批處理作業調度 174
算法分析題6 177
算法實現題6 178
第7章 隨機化算法 187
7.1 隨機數 187
7.2 數值隨機化算法 189
7.3 舍伍德算法 191
7.4 拉斯維加斯算法 196
7.5 蒙特卡羅算法 202
算法分析題7 204
算法實現題7 207
第8章 線性規劃與網絡流 210
8.1 線性規劃問題和單純形算法 210
8.2 最大網絡流問題 222
8.3 最小費用流問題 239
算法分析題8 256
算法實現題8 257
第9章 串與序列的算法 268
9.1 子串搜索算法 268
9.2 後綴數組與最長公共字串 279
9.3 序列比較算法 288
算法分析題9 294
算法實現題9 296
第10章 數論算法 300
10.1 數論基本概念 300
10.2 最大公約數算法 303
10.3 不定方程算法 312
10.4 同余與模運算 316
10.5 模線性方程 319
10.6 素數算法 325
10.7 原根與離散對數 337
算法分析題10 344
算法實現題10 345
參考文獻 350