          算法設計與分析培訓

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

1.1 本教學內容簡介

1.2 算法設計的兩個例子

1.3 問題的計算復雜度：排序問題

1.4 貨郎問題與計算復雜性

1.5 算法及其時間復雜度

1.6 算法的偽碼表示

1.7 函數的漸近的界

1.8 有關函數漸近的界的定理

1.9 幾類重要函數

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

2.1 本教學內容簡介

2.2 序列求和的方法

2.3 遞推方程與算法分析

2.4 迭代法求解遞推方程

2.5 差消法化簡遞推方程

2.6 遞歸樹

2.7 主定理及其證明

2.8 主定理的應用

三 分治策略（1）

3.1 本教學內容簡介

3.2 分治策略的設計思想

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

3.4 芯片測試

3.5 快速排序

3.6 冪乘算法及應用

3.7 改進分治算法的途徑1：減少子問題數

3.8 改進分治算法的途徑2：增加預處理

四 分治策略（2）

4.1 本內容簡介

4.2 選大與小

4.3 選二大

4.4 一般選擇問題的算法設計

4.5.選擇問題的算法分析

4.6 卷積及應用

4.7 卷積計算

4.8 快速傅立葉變換FFT算法

4.9 平面點集的凸包

五 動態規劃（1）

5.1 本教學內容簡介

5.2 動態規劃算法的例子

5.3 動態規劃算法設計

5.4 動態規劃算法的遞歸實現

5.5 動態規劃算法的迭代實現

5.6 投資問題

5.7 背包問題

5.8 長公共子序列

六 動態規劃（2）

6.1 本教學內容簡介

6.2 圖像壓縮

6.3 大子段和

6.4 優二叉檢索樹的概念

6.5 優二叉檢索樹的算法

6.6 RNA二級結構預測

6.7 序列比對

七 貪心法（1）

7.1 本教學內容簡介

7.2 貪心法的例子

7.3 貪心法的正確性證明

7.4 優裝載問題

7.5 小延遲調度

7.6 得不到優解的處理方法

八 貪心法（2）

8.1 本教學內容簡介

8.2 優前綴碼及哈夫曼算法

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

8.4 小生成樹

8.5 Prim算法

8.6 Kruskal算法

8.7 單源短路徑問題及算法

8.8 Dijkstra算法的證明

單元作業

九 回溯與分支限界（1）

9.1 本教學內容簡介

9.2 幾個回溯算法的例子

9.3 回溯算法的設計思想和適用條件

9.4 回溯算法實現及實例

9.5 圖的著色

9.6 搜索樹結點數的估計

作業測試

十 回溯與分支限界

10.1 本教學內容簡介

10.2 分支限界

10.3 大團問題

10.4 貨郎問題

10.5 圓排列問題

10.6 連續郵資問題