計(jì)算機(jī)算法設(shè)計(jì)與分析（第2版）

第1章算法概述

1.1算法與程序
1.2算法復(fù)雜性分析
習(xí)題1

第2章遞歸與分治策略

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

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

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

第4章貪心算法

4.1活動(dòng)安排問(wèn)題
4.2貪心算法的基本要素
4.3最優(yōu)裝載
4.4哈夫曼編碼
4.5單源最短路徑
4.6最小生成樹(shù)
4.7多機(jī)調(diào)度問(wèn)題
4.8貪心算法的理論基礎(chǔ)
習(xí)題4

第5章回溯法

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

第6章分支限界法

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