算法教案第4章貪心算法

PAGE天津城市建設(shè)學(xué)院教案編號：6課時安排：6學(xué)時教學(xué)課型：理論課√實驗課□習(xí)題課□實踐課□其它□題目（教學(xué)章、節(jié)或主題）：第4章貪心算法4.1活動安排問題4.2貪心算法的基本要素4.3最優(yōu)裝載4.4哈夫曼編碼4.5單源最短路經(jīng)4.6最小生成樹4.7多機調(diào)度問題教學(xué)目的要求（分掌握、熟悉、了解三個層次）：1、理解貪心算法的概念。2、掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)3、理解貪心算法與動態(tài)規(guī)劃算法的差異4、理解貪心算法的一般理論5、通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計策略。（1）活動安排問題；（2）最優(yōu)裝載問題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹；（6）多機調(diào)度問題。教學(xué)內(nèi)容（注明：重點*#難點？疑點）：首先介紹最優(yōu)化問題的求解（例：最小代價通訊網(wǎng)絡(luò)），然后用例找零錢描述如何用貪心算法求解最優(yōu)化問題。介紹貪心算法的基本思想和貪心準(zhǔn)則的基本概念。*4.1活動安排問題1、介紹活動安排問題，相容活動的概念。2、貪心準(zhǔn)則：使剩余的可安排時間段極大化，，以便安排盡可能多的相容活動。3、貪心算法求解。4、舉例介紹求解過程。5、具體算法講解。6、時間復(fù)雜度分析。7、附加：習(xí)題4-1機器調(diào)度問題4.7多機調(diào)度問題1、介紹多機調(diào)度問題。2、貪心準(zhǔn)則：長作業(yè)先分配。3、算法描述。4、具體算法講解。5、時間復(fù)雜度分析。4.2貪心算法的基本要素1、貪心選擇性質(zhì)不滿足此性質(zhì)，也可以用貪心算法，但只能求解最優(yōu)解的近似解；只有滿足此性質(zhì)，用貪心算法才能求得最優(yōu)解。2、最優(yōu)子結(jié)構(gòu)性質(zhì)3、貪心算法與動態(tài)規(guī)劃算法的差異0-1背包問題：不能用貪心算法求得最優(yōu)解，但可用與動態(tài)規(guī)劃算法求得最優(yōu)解。背包問題：能用貪心算法求得最優(yōu)解。（具體算法講解）附加刪數(shù)問題數(shù)列級差問題4.3最優(yōu)裝載1、介紹最優(yōu)裝載問題。2、貪心準(zhǔn)則：重量最輕者先裝。3、算法描述。4、具體算法講解。5、時間復(fù)雜度分析。*#4.4哈夫曼編碼1、前綴碼和最優(yōu)前綴碼的概念。2、詳細講解構(gòu)造哈夫曼樹的過程，并舉例。3、構(gòu)造哈夫曼編碼的算法。1）簡介用堆排序?qū)崿F(xiàn)優(yōu)先隊列及構(gòu)建哈夫曼樹的算法。2）演示哈夫曼樹的構(gòu)造過程。3）詳細講解數(shù)據(jù)結(jié)構(gòu)中曾講過的構(gòu)造哈夫曼編碼的算法。4、證明哈夫曼算法的正確性。1）貪心選擇性質(zhì)2）最優(yōu)子結(jié)構(gòu)性質(zhì)4.5單源最短路經(jīng)1、算法的基本思想2、通過例子講解算法的執(zhí)行過程。3、補充求最短路經(jīng)的程序4.6最小生成樹1、最小生成樹的概念2、prim算法1）基本思路2）具體算法講解3）舉例4）時間復(fù)雜度分析。3、kruskal算法1）基本思路2）具體算法講解（修改書上算法，能直接實現(xiàn)）3）舉例4）時間復(fù)雜度分析。教學(xué)方式、手段：講授媒介：多媒體+板書討論、思考題、作業(yè)：4-14-54-114-244-254-26（6選3）參考書目：1、蘇德富等編著。計算機算法設(shè)計與分析，電子工業(yè)出版社，200