計算機算法設計與分析(第4版)（簡體書）

《計算機算法設計與分析(第4版)》是普通高等教育“十一五”國家級規劃教材和國家精品課程教材。全書以算法設計策略為知識單元，系統介紹計算機算法的設計方法與分析技巧。主要內容包括：算法概述、遞歸與分治策略、動態規劃、貪心算法、回溯法、分支限界法、隨機化算法、線性規劃與網絡流等。書中既涉及經典與實用算法及實例分析，又包括算法熱點領域追蹤。
為突出教材的可讀性和可用性，章首增加了學習要點提示，章末配有難易適度的算法分析題和算法實現題；配套出版了《計算機算法設計與分析習題解答（第2版）》；并免費提供電子課件和教學網站服務。

《計算機算法設計與分析(第4版)》是普通高等教育“十一五”國家級規劃教材高等學校規劃教材之一。

第1章 算法概述
1.1 算法與程序
1.2 算法復雜性分析
1.3 NP完全性理論
算法分析題1
算法實現題1

第2章 遞歸與分治策略
2.1 遞歸的概念
2.2 分治法的基本思想
2.3 二分搜索技術
2.4 大整數的乘法
2.5 Strassen矩陣乘法
2.6 棋盤覆蓋
2.7 合并排序
2.8 快速排序
2.9 線性時間選擇
2.1 0最接近點對問題
2.1 1循環賽日程表
算法分析題2
算法實現題2

第3章 動態規劃
3.1 矩陣連乘問題
3.2 動態規劃算法的基本要素
3.3 最長公共子序列
3.4 最大子段和
3.5 凸多邊形最優三角剖分
3.6 多邊形游戲
3.7 圖像壓縮
3.8 電路布線
3.9 流水作業調度
3.1 00-1背包問題
3.1 1最優二叉搜索樹
算法分析題3
算法實現題3

第4章 貪心算法
4.1 活動安排問題
4.2 貪心算法的基本要素
4.3 最優裝載
4.4 哈夫曼編碼
4.5 單源最短路徑
4.6 最小生成樹
4.7 多機調度問題
算法分析題4
算法實現題4

第5章 回溯法
5.1 回溯法的算法框架
5.2 裝載問題
5.3 批處理作業調度
5.4 符號三角形問題
5.5 n後問題
5.6 0-1背包問題
5.7 最大團問題
5.8 圖的m著色問題
5.9 旅行售貨員問題
5.1 0圓排列問題
5.1 1電路板排列問題
5.1 2連續郵資問題
5.1 3回溯法的效率分析
算法分析題5
算法實現題5

第6章 分支限界法
6.1 分支限界法的基本思想
6.2 單源最短路徑問題
6.3 裝載問題
6.4 布線問題
6.5 0-1背包問題
6.6 最大團問題
6.7 旅行售貨員問題
6.8 電路板排列問題
6.9 批處理作業調度
算法分析題6
算法實現題6

第7章 隨機化算法
7.1 隨機數
7.2 數值隨機化算法
7.2.1 用隨機投點法計算π值
7.2.2 計算定積分
7.2.3 解非線性方程組
7.3 舍伍德(Sherwood)算法
7.3.1 線性時間選擇算法
7.3.2 搜索有序表
7.3.3 跳躍表
7.4 拉斯維加斯(Las Vegas)算法
7.4.1 n後問題
7.4.2 整數因子分解
7.5 蒙特卡羅(Monte Carlo)算法
7.5.1 蒙特卡羅算法的基本思想
7.5.2 主元素問題
7.5.3 素數測試
算法分析題7
算法實現題7

第8章 線性規劃與網絡流
8.1 線性規劃問題和單純形算法
8.1.1 線性規劃問題及其表示
8.1.2 線性規劃基本定理
8.1.3 約束標準型線性規劃問題的單純形算法
8.1.4 將一般問題轉化為約束標準型
8.1.5 一般線性規劃問題的兩階段單純形算法
8.1.6 單純形算法的描述和實現
8.1.7 退化情形的處理
8.1.8 應用舉例
8.2 最大網絡流問題
8.2.1 網絡與流
8.2.2 增廣路算法
8.2.3 預流推進算法
8.2.4 最大流問題的變換與應用
8.3 最小費用流問題
8.3.1 最小費用流
8.3.2 消圈算法
8.3.3 最小費用路算法
8.3.4 網絡單純形算法
8.3.5 最小費用流問題的變換與應用
算法分析題8
算法實現題8
附錄AC++概要
1.變量、指針和引用
2.函數與參數傳遞
3.C++的類
4.類的對象
5.構造函數與析構函數
6.運算符重載
7.友元函數
8.內聯函數
9.結構
10.聯合
11.異常
12.模板
13.動態存儲分配
參考文獻

問題的計算復雜性可以通過解決該問題所需計算量的多少來度量。如何區分一個問題是“易”還是“難”呢？人們通常將可在多項式時間內解決的問題看作是“易”解問題，而將需要指數函數時間解決的問題看作是“難”問題。這里所說的多項式時間和指數函數時間是針對問題的規模而言的，即解決問題所需的時間是問題規模的多項式函數或指數函數。對于實際遇到的許多問題，人們至今無法確切了解其內在的計算復雜性。因此只能用分類的方法將計算復雜性大致相同的問題歸類進行研究。而對于能夠進行較徹底分析的問題則盡可能準確地確定其計算復雜性，從而獲得對它的深刻理解。
本書中的許多算法都是多項式時間算法，即對規模為n的輸入，算法在最壞情況下的計算時間為，k為一個常數。是否所有的問題都在多項式時間內可解呢？回答是否定的。例如，存在一些不可解問題，如著名的“圖靈停機問題”。任何計算機不論耗費多少時間也不能解該問題。此外，還有一些問題，雖然可以用計算機求解，但是對任意常數k，它們都不能在的時間內得到解答。
一般地說，將可由多項式時間算法求解的問題看作是易解的問題，而將需要超多項式時間才能求解的問題看作是難解的問題。有許多問題，從表面上看似乎并不比排序或圖的搜索等問題更困難，然而至今人們還沒有找到解決這些問題的多項式時間算法，也沒有人能夠證明這些問題需要超多項式時間下界。也就是說，這類問題的計算復雜性至今未知。為了研究這類問題的計算復雜性，人們提出了非確定性圖靈機計算模型。在該計算模型下，許多問題就可以在多項式時間內求解。
本書中討論的許多問題是以最優化問題形式出現的，如旅行售貨員問題、0-1背包問題和最大團問題等。然而對每一個最優化問題，都有一個與之對應的判定問題。第5章中要討論的旅行售貨員問題是一個典型的最優化問題。