算法分析與設(shè)計

第1章 緒論
1.1 算法的基本概念
1.1.1 為什么要學習算法
1.1.2 算法及其重要特性
1.1.3 算法的描述方法
1.1.4 算法設(shè)計的一般過程
1.2 算法分析
1.2.1 漸近符號
1.2.2 非遞歸算法的分析
1.2.3 遞歸算法的分析
1.2.4 算法的后驗分析
實驗1——求最大公約數(shù)
閱讀材料1——海量數(shù)據(jù)處理方法：Bloom filter
習題1
第2章 分治法
2.1 概述
2.1.1 分治法簡介
2.1.2 分治法的基本步驟
2.2 最大子段和問題
2.3 棋盤覆蓋問題
2.4 輸油管道問題
2.5 凸包問題
實驗2——最近對問題
閱讀材料2——分治法在中值濾波快速算法中的應(yīng)用研究
習題2
第3章 動態(tài)規(guī)劃
3.1 動態(tài)規(guī)劃問題的數(shù)學描述
3.2 動態(tài)規(guī)劃問題的最優(yōu)化原理
3.3 動態(tài)規(guī)劃應(yīng)用舉例
3.3.1 數(shù)字三角形問題
實驗3數(shù)字三角形問題
閱讀材料3——深入探討動態(tài)規(guī)劃中的幾個問題
習題3
第4章 貪心法
4.1 概 述
4.1.1 貪心法的設(shè)計思想
4.1.2 貪心法的求解過程
4.2 刪數(shù)問題
4.2.1 問題的提出
4.2.2 貪心選擇策略
4.2.3 最優(yōu)子結(jié)構(gòu)性質(zhì)
4.2.4 貪心選擇性質(zhì)
4.2.5 算法實現(xiàn)
4.3 圖問題中的貪心法
4.3.1 TSP問題
4.3.2 圖著色問題
4.4 FatMouse Trade
實驗4——圖著色問題
閱讀材料4——用貪心算法求解刪數(shù)問題
習題4
第5章 回溯法
5.1 概 述
5.1.1 問題的解空間
5.1.2 解空間樹的動態(tài)搜索
5.1.3 回溯法的求解過程
5.1.4 回溯法的時間性能
5.2 裝載問題
5.3 圖著色問題
5.4 Fire Net
實驗5——O／I背包問題
閱讀材料5——基于回溯法油管傳輸射孔排炮算法研究
習題5
第6章 分支限界法
6.1 概 述
6.1.1 解空間樹的動態(tài)搜索
6.1.2 分支限界法的設(shè)計思想
6.1.3 分支限界法的時間性能
6.2 TSP問題
6.3 電路布線問題
實驗6-電路布線問題
閱讀材料6——分支限界法在游戲地圖尋徑中的應(yīng)用
習題6
第7章 概率算法
7.1 概 述
7.1.1 概率算法的設(shè)計思想
7.1.2 隨機數(shù)發(fā)生器
7.2 舍伍德（Sherwood）型概率算法l
7.2.1 選擇問題
7.3 拉斯維加斯（LasVegas）型概率算法
7.3.1 八皇后問題
7.3.2 整數(shù)因子分解問題
7.4 蒙特卡羅（Monte Carlo）型概率算法
7.4.1 主元素問題
實驗7——隨機數(shù)發(fā)生器
閱讀材料7隨機數(shù)生成原理
習題7
第8章 近似算法
8.1 概述
8.1.1 近似算法的設(shè)計思想
8.1.2 近似算法的性能
8.2 頂點覆蓋問題
8.3 平方根問題
8.4 TSP問題
實驗8——TsP問題的近似算法
閱讀材料8 若干NP困難的組合最優(yōu)化問題的近似算法
習題8
國際大學生程序設(shè)計競賽試題——The Triangle
模擬試題
參考文獻