算法設(shè)計與分析

1、算法設(shè)計與分析算法設(shè)計與分析黃如兵目錄目錄章節(jié)復(fù)習(xí) 第一章 算法概述 第二章 遞歸與分治策略 第三章 動態(tài)規(guī)劃 第四章 貪心算法 第五章 回溯法 第六章 分支限界法 第八章 NP完全性理論 第九章 近似算法考試題型（選擇題10，簡答題20，計算題20，設(shè)計題50）第第1 1章章 算法概述算法概述一、算法與程序 算法的概念(性質(zhì)) 算法與程序 算法的描述方法二、算法復(fù)雜性分析 算法復(fù)雜性的意義 漸進(jìn)性態(tài)及漸進(jìn)意義下的有關(guān)記號注意： 、o、的求解方法及性質(zhì)證明第二章第二章 遞歸與分治策略遞歸與分治策略一、遞歸 基本概念 幾種典型的遞歸二、分治策略的基本思想三、分治范例 二分搜索 大數(shù)相乘 Stra

2、ssen矩陣乘法 棋盤覆蓋 最接近點對 循環(huán)賽日程表第三章第三章 動態(tài)規(guī)劃動態(tài)規(guī)劃 一、動態(tài)規(guī)劃的基本步驟 找出最優(yōu)解的性質(zhì)，刻畫其結(jié)構(gòu)特征 遞歸定義最優(yōu)值 以自底向上的方式計算最優(yōu)值 根據(jù)計算最優(yōu)值所獲得的有關(guān)信息構(gòu)造最優(yōu)解 二、常見動態(tài)規(guī)劃范例 矩陣連乘 最長公共子序列 流水作業(yè)調(diào)度 背包問題 三、動態(tài)規(guī)劃與備忘錄方法及動態(tài)規(guī)劃加速原理第四章第四章 貪心算法貪心算法一、貪心算法的基本思想最優(yōu)子結(jié)構(gòu)性質(zhì)貪心選擇性質(zhì)貪心算法與動態(tài)規(guī)劃算法的差異二、范例活動安排最優(yōu)裝載哈夫曼編碼單源最短路徑多機(jī)調(diào)度注意：貪心算法正確性證明(構(gòu)造方法)第五章第五章 回溯法回溯法 一、回溯法的基本思想 基本步驟 針

3、對所給問題，定義問題的解空間； 確定易于搜索的解空間結(jié)構(gòu)； 以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)避免無效搜索。 常用剪枝函數(shù)： 用約束函數(shù)在擴(kuò)展結(jié)點處剪去不滿足約束的子樹； 用限界函數(shù)剪去得不到最優(yōu)解的子樹。 遞歸回溯與迭代回溯 子集樹與排列樹 二、回溯法范例 裝載問題；批處理作業(yè)調(diào)度；n后問題； 0-1背包問題； 圖的m著色問題 旅行售貨員問題第六章第六章 分支限界法分支限界法 掌握分支限界法的算法框架 隊列式(FIFO)分支限界法 優(yōu)先隊列式分支限界法 與回溯法的差異 范例 裝載問題； 0-1背包問題； 最大團(tuán)問題； 旅行售貨員問題 批處理作業(yè)調(diào)度問題第第9章章 NP完全性理

4、論與近似算法完全性理論與近似算法關(guān)于NP完全性理論： 了解RAM，RASP和圖靈機(jī)計算模型 理解非確定性圖靈機(jī)的概念 理解P類與NP類語言的概念 理解NP完全問題的概念關(guān)于近似算法： 了解近似算法的性能比及多項式時間近似格式的概念 通過范例學(xué)習(xí)NP完全問題的近似算法的設(shè)計思想 頂點覆蓋問題； 旅行售貨員問題； 集合覆蓋問題； 子集和問題。1. 漸進(jìn)意義下四種記號的涵義？時間復(fù)雜性？空間復(fù)雜性？漸進(jìn)表達(dá)式求解。2什么是遞歸算法？什么是遞歸函數(shù)？3遞歸函數(shù)的二要素是什么？4分治法的設(shè)計思想是什么？分治法所能解決的問題一般具有的特征是什么？5什么叫問題的最優(yōu)子結(jié)構(gòu)性質(zhì)？6動態(tài)規(guī)劃基本步驟是什么？7動

5、態(tài)規(guī)劃算法的基本要素是什么？舉例說明一些可以用動態(tài)規(guī)劃算法解決的問題。8說明分治法與動態(tài)規(guī)劃法的相同點和不同之處？9貪心算法的兩個重要要素是什么？舉例說明一些可以用貪心算法解決的問題。10貪心算法與動態(tài)規(guī)劃算法的的相同點和不同之處？11.排列樹和子集算法框架。12背包問題與01背包問題有何區(qū)別？13回溯法與分支限界法之間的相同點是什么？不同之處在哪些方面？14分支限界法基本思想是什么？15約束函數(shù)的功能是什么？16限界函數(shù)的功能是什么？17. 常見的兩種分支限界法是什么？18什么是P類問題(語言)和NP類問題（語言）？19哪些問題是NP完全問題。ABCD6684751、下圖為帶權(quán)圖，求最小費用

6、回路。要求：給出優(yōu)先隊列式分優(yōu)先隊列式分支限界法支限界法求解時的搜索樹及求解過程。（起始點從A開始）ABCDEFGHIJKLMNO10考慮如下0-1背包問題的實例：n=3, c=30, w=16,15,15, p=45,25,25 隊列式分支限界搜索過程：A B, C = B, CB, C D, E = EC, E F, G = F, GE, F, G J, K = K(45) 1,0,0F, G L, M =L(50) 0, 1, 1 M(25)G N, 0 =N(25), O(0) 結(jié)果解：最大價值=50解向量=（0，1，1）搜索過程剪去不可行結(jié)點為根的子樹搜索樹2、流水作業(yè)調(diào)度問題。研究

7、一組實例： A=(11,3,5,7,8,12,14) B=(21,8,9,15,2,9,10)用Johnson算法給出最優(yōu)調(diào)度過程及完工時間。3、字符A到G出現(xiàn)的頻率分布恰好滿足下列關(guān)系：F（0）=1，F(xiàn)（1）=1;F（n）=F（n-1）+F（n-2）（n1）;求它們的Huffman編碼是什么？1、遞歸 某人寫了n封信和n個信封，如果所有的信都裝錯了信封，求共有多少種不同的情況。要求寫出遞歸方程；寫出算法，分析算法時間復(fù)雜度。2、分治法設(shè)2個含n個元素的有序數(shù)組，設(shè)計一O(log2n)算法，查找給定值k所落在的數(shù)組（要求給出算法思想、說明其復(fù)雜度）。3、 貪心法設(shè)有n個顧客等待一項服務(wù)。顧客i需要服務(wù)的時間為ti。應(yīng)如何安排n個顧客的服務(wù)次序才能使總的等待時間達(dá)到最小？設(shè)計此問題的有效算法(算法步驟)并證明其正確性。（總的等待時間是每個顧客等待時間總和）。4、動態(tài)規(guī)劃0-1背包問題。以表格形式推導(dǎo)出最優(yōu)解并說明解向量的構(gòu)造過程。5、回溯法 (1) 給出解向量的形式，指出搜索樹的類型； (2) 描述剪枝操作； (3) 畫出找到一個解所生成的部分搜