算法導(dǎo)論第三版教學(xué)大綱課程信息課程名稱：算法導(dǎo)論課程編號：CS161學(xué)分：3授課對象：計算機科學(xué)、計算機工程等院系的本科生先修課程：數(shù)據(jù)結(jié)構(gòu)、離散數(shù)學(xué)、計算機程序設(shè)計等教學(xué)目的本門課程主要介紹基本的算法思想以及算法在計算機科學(xué)中的應(yīng)用。通過本門課程，學(xué)生將會：熟練掌握各種數(shù)據(jù)結(jié)構(gòu)和算法；掌握算法設(shè)計和分析的基本方法；對算法問題有深入的了解；培養(yǎng)算法設(shè)計和實現(xiàn)的編程能力。教學(xué)內(nèi)容第一章：算法在計算中心地位算法的概念和基本概念；算法設(shè)計的重要性；算法復(fù)雜度分析；算法的實現(xiàn)和測試。第二章：插入排序插入排序的概念和方法；插入排序的復(fù)雜度分析；插入排序在實際應(yīng)用中的效果；插入排序的變體。第三章：算法增長率與復(fù)雜度漸進(jìn)符號和漸進(jìn)分析；大O記號的定義和應(yīng)用；Omega記號和Theta記號；漸進(jìn)分析的注意事項。第四章：分治策略分治策略的概念和方法；分治策略的三個階段；分治策略的復(fù)雜度分析；分治策略在現(xiàn)實生活中的應(yīng)用。第五章：最大子數(shù)組問題最大子數(shù)組問題的定義和方法；暴力求解和分治求解；最大子數(shù)組問題的時間復(fù)雜度和空間復(fù)雜度。第六章：堆排序堆的定義和性質(zhì)；堆排序的基本思路；堆排序的時間復(fù)雜度分析；堆排序在實際應(yīng)用中的效果。第七章：快速排序快速排序的基本思路；快速排序的實現(xiàn)和算法分析；快速排序在實際應(yīng)用中的效果；快速排序的修改和變體。第八章：圖算法圖的基礎(chǔ)知識和性質(zhì)；圖算法的分類和應(yīng)用；廣度優(yōu)先搜索算法；深度優(yōu)先搜索算法。第九章：動態(tài)規(guī)劃動態(tài)規(guī)劃的概念和方法；動態(tài)規(guī)劃的步驟和分類；動態(tài)規(guī)劃的復(fù)雜度計算；動態(tài)規(guī)劃的應(yīng)用和實現(xiàn)。第十章：貪心算法貪心算法的概念和思路；貪心算法的步驟和分類；貪心算法的應(yīng)用和實現(xiàn)；貪心算法的正確性證明和復(fù)雜度分析。教學(xué)方法講課配合實例說明，突出算法的思想和方法；強調(diào)算法的分析思路和技巧；指導(dǎo)學(xué)生進(jìn)行作業(yè)和實驗，提高學(xué)生算法編程能力；小組討論和課堂互動，加強學(xué)生的理解和記憶。教材《算法導(dǎo)論》(第3版)，作者：ThomasH.Cormen、CharlesE.Leiserson、RonaldL.Rivest、CliffordStein，出版社：機械工業(yè)出版社。作業(yè)和考核作業(yè)：每個單元可以布置1次作業(yè)，作業(yè)內(nèi)容包括算法設(shè)計、程序?qū)崿F(xiàn)、分析和說明，占總成績10%；課堂實驗：每個單元可以布置1次課堂實驗，實驗內(nèi)容包括算法實現(xiàn)和時間復(fù)雜度分析，占總成績10%；期末考試：以閉卷方式考試，包括理論和實踐部分，占總成績80%。參考資料《算法導(dǎo)論》(第3版)，作者：ThomasH.Cormen、CharlesE.Leiserson、RonaldL.Rivest、CliffordStein，出版社：機械工業(yè)出版社；《數(shù)據(jù)結(jié)構(gòu)與算法分析》(第3版)，作者：Mark