算法教案第4章貪心算法

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