          算法設(shè)計與分析培訓(xùn)

一 基礎(chǔ)知識（1）：算法的基本概念及偽碼描述，函數(shù)的漸近的界

1.1 本教學(xué)內(nèi)容簡介

1.2 算法設(shè)計的兩個例子

1.3 問題的計算復(fù)雜度：排序問題

1.4 貨郎問題與計算復(fù)雜性

1.5 算法及其時間復(fù)雜度

1.6 算法的偽碼表示

1.7 函數(shù)的漸近的界

1.8 有關(guān)函數(shù)漸近的界的定理

1.9 幾類重要函數(shù)

二 基礎(chǔ)知識（2）：序列求和方法，遞推方程求解

2.1 本教學(xué)內(nèi)容簡介

2.2 序列求和的方法

2.3 遞推方程與算法分析

2.4 迭代法求解遞推方程

2.5 差消法化簡遞推方程

2.6 遞歸樹

2.7 主定理及其證明

2.8 主定理的應(yīng)用

三 分治策略（1）

3.1 本教學(xué)內(nèi)容簡介

3.2 分治策略的設(shè)計思想

3.3 分治策略的一般描述和分析方法

3.4 芯片測試

3.5 快速排序

3.6 冪乘算法及應(yīng)用

3.7 改進(jìn)分治算法的途徑1：減少子問題數(shù)

3.8 改進(jìn)分治算法的途徑2：增加預(yù)處理

四 分治策略（2）

4.1 本內(nèi)容簡介

4.2 選大與小

4.3 選二大

4.4 一般選擇問題的算法設(shè)計

4.5.選擇問題的算法分析

4.6 卷積及應(yīng)用

4.7 卷積計算

4.8 快速傅立葉變換FFT算法

4.9 平面點集的凸包

五 動態(tài)規(guī)劃（1）

5.1 本教學(xué)內(nèi)容簡介

5.2 動態(tài)規(guī)劃算法的例子

5.3 動態(tài)規(guī)劃算法設(shè)計

5.4 動態(tài)規(guī)劃算法的遞歸實現(xiàn)

5.5 動態(tài)規(guī)劃算法的迭代實現(xiàn)

5.6 投資問題

5.7 背包問題

5.8 長公共子序列

六 動態(tài)規(guī)劃（2）

6.1 本教學(xué)內(nèi)容簡介

6.2 圖像壓縮

6.3 大子段和

6.4 優(yōu)二叉檢索樹的概念

6.5 優(yōu)二叉檢索樹的算法

6.6 RNA二級結(jié)構(gòu)預(yù)測

6.7 序列比對

七 貪心法（1）

7.1 本教學(xué)內(nèi)容簡介

7.2 貪心法的例子

7.3 貪心法的正確性證明

7.4 優(yōu)裝載問題

7.5 小延遲調(diào)度

7.6 得不到優(yōu)解的處理方法

八 貪心法（2）

8.1 本教學(xué)內(nèi)容簡介

8.2 優(yōu)前綴碼及哈夫曼算法

8.3 哈夫曼算法的正確性證明

8.4 小生成樹

8.5 Prim算法

8.6 Kruskal算法

8.7 單源短路徑問題及算法

8.8 Dijkstra算法的證明

單元作業(yè)

九 回溯與分支限界（1）

9.1 本教學(xué)內(nèi)容簡介

9.2 幾個回溯算法的例子

9.3 回溯算法的設(shè)計思想和適用條件

9.4 回溯算法實現(xiàn)及實例

9.5 圖的著色

9.6 搜索樹結(jié)點數(shù)的估計

作業(yè)測試

十 回溯與分支限界

10.1 本教學(xué)內(nèi)容簡介

10.2 分支限界

10.3 大團問題

10.4 貨郎問題

10.5 圓排列問題

10.6 連續(xù)郵資問題