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

第1章算法概述

1.1算法與程序
1.2算法復雜性分析
習題1

第2章遞歸與分治策略

2.1遞歸的概念
2.2分治法的基本思想
2.3二分搜索技術
2.4大整數(shù)的乘法
2.5Strassen矩陣乘法
2.6棋盤覆蓋
2.7合并排序
2.8快速排序
2.9線性時間選擇
2.10最接近點對問題
2.11循環(huán)賽日程表
習題2

第3章動態(tài)規(guī)劃

3.1矩陣連乘問題
3.2動態(tài)規(guī)劃算法的基本要素
3.3最長公共子序列
3.4最大子段和
3.5凸多邊形最優(yōu)三角剖分
3.6多邊形游戲
3.7圖像壓縮
3.8電路布線
3.9流水作業(yè)調度
3.100-1背包問題
3.11最優(yōu)二叉搜索樹
3.12動態(tài)規(guī)劃加速原理
習題3

第4章貪心算法

4.1活動安排問題
4.2貪心算法的基本要素
4.3最優(yōu)裝載
4.4哈夫曼編碼
4.5單源最短路徑
4.6最小生成樹
4.7多機調度問題
4.8貪心算法的理論基礎
習題4

第5章回溯法

5.1回溯法的算法框架
5.2裝載問題
5.3批處理作業(yè)調度
5.4符號三角形問題
5.5n后問題
5.60-1背包問題
5.7最大團問題
5.8圖的m著色問題
5.9旅行售貨員問題
5.10圓排列問題
5.11電路板排列問題
5.12連續(xù)郵資問題
5.13回溯法的效率分析
習題5

第6章分支限界法

6.1分支限界法的基本思想
6.2單源最短路徑問題
6.3裝載問題
6.4布線問題
6.50-1背包問題
6.6最大團問題
6.7旅行售貨員問題
6.8電路板排列問題
6.9批處理作業(yè)調度
習題6
第7章概率算法
7.1隨機數(shù)
7.2數(shù)值概率算法
7.2.1用隨機投點法計算值
7.2.2計算定積分
7.2.3解非線性方程組
7.3舍伍德(Sherwood)算法
7.3.1線性時間選擇算法
7.3.2搜索有序表
7.3.3跳躍表
7.4拉斯維加斯(LssVegas)算法
7.4.1n后問題
7.4.2整數(shù)因子分解
7.5蒙特卡羅(MonteCarlo)算法
7.5.1蒙特卡羅算法的基本思想
7.5.2主元素問題
7.5.3素數(shù)測試
習題7
第8章線性規(guī)劃與網(wǎng)絡流
8.1線性規(guī)劃問題和單純形算法
8.1.1線性規(guī)劃問題及其表示
8.1.2線性規(guī)劃基本定理
8.1.3約束標準型線性規(guī)劃問題的單純形算法
8.1.4將一般問題轉化為約束標準型
8.1.5一般線性規(guī)劃問題的2階段單純形算法
8.1.6單純形算法的描述和實現(xiàn)
8.1.7退化情形的處理
8.1.8應用舉例
8.2最大網(wǎng)絡流問題
8.2.1網(wǎng)絡與流
8.2.2增廣路算法
8.2.3預流推進算法
8.2.4最大流問題的變換與應用
8.3最小費用流問題
8.3.1最小費用流
8.3.2消圈算法
8.3.3最小費用路算法
8.3.4網(wǎng)絡單純形算法
8.3.5最小費用流問題的變換與應用
習題8
第9章NP完全性理論與近似算法
9.1計算模型
9.1.1隨機存取機RAM
9.1.2隨機存取存儲程序機RASP
9.1.3圖靈機
9.2P類與NP類問題
9.2.1非確定性圖靈機
9.2.2P類與NP類語言
9.2.3多項式時間驗證
9.3NP完全問題
9.3.1多項式時間變換
9.3.2一些典型的NP完全問題
9.4NP完全問題的近似算法
9.4.1近似算法的性能
9.4.2頂點覆蓋問題的近似算法
9.4.3旅行售貨員問題近似算法
9.4.4集合覆蓋問題的近似算法
9.4.5子集和問題的近似算法
習題9
附錄C++概要
1.變量.指針和引用
2.函數(shù)與參數(shù)傳遞
3.c++的類
4.類的對象
5.構造函數(shù)與析構函數(shù)
6.運算符重載
7.友元函數(shù)
8.內聯(lián)函數(shù)
9.結構
10.聯(lián)合
11.異常
12.模板
13.動態(tài)存儲分配
參考文獻