課程大綱： 算法設計與分析培訓
一 基礎知識（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 連續郵資問題
加入高級會員獲得助教答疑
