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

01
算法概述及復(fù)雜性理論
了解該課程要解決的問(wèn)題；了解算法的概念；掌握算法的正確性證明方法；了解問(wèn)題的下界的描述方法。

1 問(wèn)題
2 算法的概念
3 算法的正確性
4 算法的效率
5 問(wèn)題的下界
02
算法分析方法
掌握概率分析在算法復(fù)雜度分析中的應(yīng)用；掌握分?jǐn)偡治龇椒ǎ涣私鈱?shí)驗(yàn)分析方法。

1 概率分析
2 合計(jì)方法
3 記賬方法
4 勢(shì)能方法
5 實(shí)驗(yàn)分析
03
遞歸
了解遞歸的算法思想；根據(jù)選擇排序和全排列生成問(wèn)題掌握設(shè)計(jì)遞歸算法的一般步驟；求解遞歸方程。

1 遞歸的算法思想
2 選擇排序
3 生成排列
4 遞歸方程的求解
04
分治（上）
了解分治的算法思想；根據(jù)案例掌握分治算法設(shè)計(jì)的一般步驟；

1 算法思想
2 二分搜索
3 快速排序
4 歸并排序
05
分治（下）與動(dòng)態(tài)規(guī)劃（上）
根據(jù)殘缺棋盤游戲進(jìn)一步了解分治算法，難點(diǎn)在于理解分治算法“分”出的子問(wèn)題必須具有相似的結(jié)構(gòu)；初步了解動(dòng)態(tài)規(guī)劃算法，難點(diǎn)在于如何根據(jù)遞推關(guān)系式填表；

1 殘缺棋盤游戲
2 大整數(shù)乘法
3 矩陣乘法
4 動(dòng)態(tài)規(guī)劃引言
5 動(dòng)態(tài)規(guī)劃算法思想
6 矩陣鏈乘法問(wèn)題
06
動(dòng)態(tài)規(guī)劃（中）
根據(jù)多個(gè)案例進(jìn)一步了解掌握動(dòng)態(tài)規(guī)劃算法，難點(diǎn)在于遞推關(guān)系式的推導(dǎo)；根據(jù)裝配線調(diào)度問(wèn)題了解動(dòng)態(tài)規(guī)劃的另一種求解方法：備忘錄法； 掌握如何使用遞歸方法構(gòu)造優(yōu)解；

1 優(yōu)二叉搜索樹問(wèn)題
2 大字段和問(wèn)題
3 裝配線調(diào)度問(wèn)題
4 長(zhǎng)公共子序列問(wèn)題
07
動(dòng)態(tài)規(guī)劃（下）與貪心算法（上）
由背包問(wèn)題理解動(dòng)態(tài)規(guī)劃優(yōu)子結(jié)構(gòu)性質(zhì)；根據(jù)任務(wù)調(diào)度問(wèn)題理解貪心算法； 對(duì)比區(qū)分貪心算法與動(dòng)態(tài)規(guī)劃算法，難點(diǎn)在于貪心算法的證明；

1 0/1背包問(wèn)題
2 動(dòng)態(tài)規(guī)劃的基本性質(zhì)
3 貪心算法思想
4 任務(wù)選擇問(wèn)題（上）
08
貪心算法（下）
由任務(wù)選擇問(wèn)理解貪心算法；由背包問(wèn)題進(jìn)一步區(qū)分動(dòng)態(tài)規(guī)劃與貪心算法； 理解Huffman編碼中的貪心策略；

1 任務(wù)選擇問(wèn)題（下）
2 背包問(wèn)題
3 哈夫曼編碼問(wèn)題
4 任務(wù)選擇實(shí)驗(yàn)
09
圖算法（上）
了解圖的基本概念、表示方法、了解兩種存儲(chǔ)圖的方式（鄰接矩陣與鄰接表）及各自優(yōu)勢(shì)；掌握?qǐng)D的深度優(yōu)先搜索與廣度優(yōu)先搜索算法，難點(diǎn)在于DFS的遞歸與非遞歸實(shí)現(xiàn)； 掌握?qǐng)D的小生成樹問(wèn)題及其解法；

1 圖的表示
2 寬度優(yōu)先搜索
3 深度優(yōu)先搜索
4 小生成樹問(wèn)題--Kruskal算法
10
圖算法（下）
了解短路問(wèn)題的定義；掌握兩種基本短路問(wèn)題求解算法； 掌握、區(qū)分Prim算法與Kruskal算法；

1小生成樹問(wèn)題--Kruskal 與 Prim 比較
2 短路徑問(wèn)題
3 單源短路徑問(wèn)題
4 所有點(diǎn)對(duì)的短路徑問(wèn)題
11
網(wǎng)絡(luò)流與匹配
了解大流問(wèn)題的定義；掌握求解大流問(wèn)題的基本算法； 了解大費(fèi)用流問(wèn)題的定義；

1 大流問(wèn)題
2 大流問(wèn)題求解
3 小費(fèi)用流
12
回溯
了解回溯的定義；掌握0-1背包問(wèn)題、貨箱裝載問(wèn)題的基本解法；

1 算法思想
2 貨箱裝載問(wèn)題
3 0-1背包問(wèn)題
4 著色問(wèn)題
13
分支限界
了解分支限界算法；掌握0-1背包問(wèn)題、裝載問(wèn)題、旅行商問(wèn)題的基本解法；并與回溯算法進(jìn)行比較，加深理解；

1 算法思想
2 裝載問(wèn)題
3 0/1背包問(wèn)題
4 旅行商問(wèn)題
14
NP完全理論
初步了解算法復(fù)雜性理論，了解NP完全理論，以及P、NP和NPC問(wèn)題的定義和意義。

1 判定問(wèn)題
2 P和NP問(wèn)題
3 NPC的定義
4 電路可滿足性問(wèn)題
5 NPC的證明