課程大綱：算法設計與分析培訓
01
算法概述及復雜性理論
了解該課程要解決的問題；了解算法的概念；掌握算法的正確性證明方法；了解問題的下界的描述方法。
1 問題
2 算法的概念
3 算法的正確性
4 算法的效率
5 問題的下界
02
算法分析方法
掌握概率分析在算法復雜度分析中的應用；掌握分攤分析方法；了解實驗分析方法。
1 概率分析
2 合計方法
3 記賬方法
4 勢能方法
5 實驗分析
03
遞歸
了解遞歸的算法思想；根據選擇排序和全排列生成問題掌握設計遞歸算法的一般步驟；求解遞歸方程。
1 遞歸的算法思想
2 選擇排序
3 生成排列
4 遞歸方程的求解
04
分治（上）
了解分治的算法思想；根據案例掌握分治算法設計的一般步驟；
1 算法思想
2 二分搜索
3 快速排序
4 歸并排序
05
分治（下）與動態規劃（上）
根據殘缺棋盤游戲進一步了解分治算法，難點在于理解分治算法“分”出的子問題必須具有相似的結構；初步了解動態規劃算法，難點在于如何根據遞推關系式填表；
1 殘缺棋盤游戲
2 大整數乘法
3 矩陣乘法
4 動態規劃引言
5 動態規劃算法思想
6 矩陣鏈乘法問題
06
動態規劃（中）
根據多個案例進一步了解掌握動態規劃算法，難點在于遞推關系式的推導；根據裝配線調度問題了解動態規劃的另一種求解方法：備忘錄法； 掌握如何使用遞歸方法構造優解；
1 優二叉搜索樹問題
2 大字段和問題
3 裝配線調度問題
4 長公共子序列問題
07
動態規劃（下）與貪心算法（上）
由背包問題理解動態規劃優子結構性質；根據任務調度問題理解貪心算法； 對比區分貪心算法與動態規劃算法，難點在于貪心算法的證明；
1 0/1背包問題
2 動態規劃的基本性質
3 貪心算法思想
4 任務選擇問題（上）
08
貪心算法（下）
由任務選擇問理解貪心算法；由背包問題進一步區分動態規劃與貪心算法； 理解Huffman編碼中的貪心策略；
1 任務選擇問題（下）
2 背包問題
3 哈夫曼編碼問題
4 任務選擇實驗
09
圖算法（上）
了解圖的基本概念、表示方法、了解兩種存儲圖的方式（鄰接矩陣與鄰接表）及各自優勢；掌握圖的深度優先搜索與廣度優先搜索算法，難點在于DFS的遞歸與非遞歸實現； 掌握圖的小生成樹問題及其解法；
1 圖的表示
2 寬度優先搜索
3 深度優先搜索
4 小生成樹問題--Kruskal算法
10
圖算法（下）
了解短路問題的定義；掌握兩種基本短路問題求解算法； 掌握、區分Prim算法與Kruskal算法；
1小生成樹問題--Kruskal 與 Prim 比較
2 短路徑問題
3 單源短路徑問題
4 所有點對的短路徑問題
11
網絡流與匹配
了解大流問題的定義；掌握求解大流問題的基本算法； 了解大費用流問題的定義；
1 大流問題
2 大流問題求解
3 小費用流
12
回溯
了解回溯的定義；掌握0-1背包問題、貨箱裝載問題的基本解法；
1 算法思想
2 貨箱裝載問題
3 0-1背包問題
4 著色問題
13
分支限界
了解分支限界算法；掌握0-1背包問題、裝載問題、旅行商問題的基本解法；并與回溯算法進行比較，加深理解；
1 算法思想
2 裝載問題
3 0/1背包問題
4 旅行商問題
14
NP完全理論
初步了解算法復雜性理論，了解NP完全理論，以及P、NP和NPC問題的定義和意義。
1 判定問題
2 P和NP問題
3 NPC的定義
4 電路可滿足性問題
5 NPC的證明
加入高級會員獲得助教答疑
