算法分析與設計

黎遠松編著的《算法分析與設計》將計算機經典問題和算法設計技術結合起來，系統深入地介紹了算法設計技術及其在經典問題中的應用。全書共8章，第l章介紹了算法分析與設計的基本概念和基本方法，第2— 8章分別介紹分治法、動態規劃法、貪心法、回溯法、分支限界法、概率算法和近似算法等算法沒計技術，每章均附有一篇閲讀材料，介紹了算法領域的一些*研究成果。書中所有算法均給出了c十+描述，書中所有問題均給出了若干應用實例。

《算法分析與設計》內容豐富，深入淺出，結合應用，圖例豐富，可作為高等院校計算機專業本科生學習算法設計與分析的教材，也可供工程技術人員和自學讀者學習參考。 ^[1] 

第1章　緒論

1．1　算法的基本概念

1．1．1　為什麼要學習算法

1．1．2　算法及其重要特性

1．1．3　算法的描述方法

1．1．4　算法設計的一般過程

1．2　算法分析

1．2．1　漸近符號

1．2．2　非遞歸算法的分析

1．2．3　遞歸算法的分析

1．2．4　算法的後驗分析

實驗1——求最大公約數

閲讀材料1——海量數據處理方法：Bloom filter

習題1．

第2章　分治法

2．1　概述

2．1．1　分治法簡介

2．1．2　分治法的基本步驟

2．2　最大子段和問題

2．3　棋盤覆蓋問題

2．4　輸油管道問題

2．5　凸包問題

實驗2一最近對問題

閲讀材料2——分治法在中值濾波快速算法中的應用研究

習題2

第3章　動態規劃

3．1　動態規劃問題的數學描述

3．2　動態規劃問題的最優化原理

3．3　動態規劃應用舉例

3．3．1　數字三角形問題

實驗3數字三角形問題

閲讀材料3——深入探討動態規劃中的幾個問題

習題3

第4章　貪心法

4．1　概　述

4．1．1　貪心法的設計思想

4．1．2　貪心法的求解過程

4．2　刪數問題

4．2．1　問題的提出

4．2．2　貪心選擇策略

4．2．3　最優子結構性質

4．2．4　貪心選擇性質

4．2．5　算法實現

4．3　圖問題中的貪心法

4．3．1　TSP問題

4．3．2　圖着色問題

4．4　FatMouse Trade

實驗4——圖着色問題

閲讀材料4——用貪心算法求解刪數問題

習題4

第5章　回溯法

5．1　概　述

5．1．1　問題的解空間

5．1．2　解空間樹的動態搜索

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　解空間樹的動態搜索

6．1．2　分支限界法的設計思想

6．1．3　分支限界法的時間性能

6．2　TSP問題

6．3　電路佈線問題

實驗6—電路佈線問題

閲讀材料6——分支限界法在遊戲地圖尋徑中的應用

習題6

第7章　概率算法

7．1　概　述

7．1．1　概率算法的設計思想

7．1．2　隨機數發生器

7．2　舍伍德(Sherwood)型概率算法l

7．2．1　選擇問題

7．3　拉斯維加斯(LasVegas)型概率算法

7．3．1　八皇后問題

7．3．2　整數因子分解問題

7．4　蒙特卡羅(Monte Carlo)型概率算法

7．4．1　主元素問題

實驗7——隨機數發生器

閲讀材料7隨機數生成原理

習題7

第8章　近似算法

8．1　概　述

8．1．1　近似算法的設計思想

8．1．2　近似算法的性能

8．2　頂點覆蓋問題

8．3　平方根問題

8．4　TSP問題

實驗8一TsP問題的近似算法

閲讀材料8　若干NP困難的組合最優化問題的近似算法

習題8

國際大學生程序設計競賽試題——The Triangle

模擬試題

參考文獻