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