理論課程教學(xué)大綱

1、理論課程教學(xué)大綱課程名稱算法設(shè)計(jì)與分析基礎(chǔ)算法設(shè)計(jì)與分析基礎(chǔ)英文名稱TheFundationofDesignAnalysisofAlgithms課程編號(hào)不填總學(xué)時(shí)60學(xué)分不填預(yù)修課程數(shù)據(jù)結(jié)構(gòu)開課學(xué)期不填大綱撰寫人顧乃杰一、教學(xué)目標(biāo)和基本要求?目標(biāo)：目標(biāo)：本課程是高等學(xué)校計(jì)算機(jī)系各專業(yè)的基礎(chǔ)課其要求是使學(xué)生了解和掌握算法基礎(chǔ)這門課程的基本內(nèi)容知道算法設(shè)計(jì)的基本方法和技術(shù)學(xué)會(huì)算法性能分析中的具體方法和技巧為計(jì)算機(jī)應(yīng)用和科學(xué)研究工作中有效求解

2、問題以及為今后進(jìn)一步學(xué)習(xí)打下基礎(chǔ)。?基本要求：基本要求：使學(xué)生能夠從的運(yùn)算三個(gè)方面去掌握各種數(shù)據(jù)結(jié)構(gòu)的特性對(duì)算法的時(shí)、空復(fù)雜性有一定的分析能力，使之能夠針對(duì)具體的應(yīng)用問題，選擇合適的數(shù)據(jù)結(jié)構(gòu)及設(shè)計(jì)結(jié)構(gòu)清晰、正確有效的算法解決之。二、課程簡(jiǎn)介本課程系統(tǒng)而全面地介紹了算法設(shè)計(jì)的基本策略和方法如:分治法、貪心法、動(dòng)態(tài)規(guī)劃、回溯法、分枝限界等等并從解決大量計(jì)算機(jī)科學(xué)和應(yīng)用中出現(xiàn)的問題出發(fā)描述了應(yīng)用這些策略和方法而設(shè)計(jì)有效算法的過程并且給出了若于

3、精典算法同時(shí)對(duì)通過對(duì)這些典型算法的時(shí)間和空間復(fù)雜度的分析逐步介紹了算法分析的方法和步驟以及提高算法性能的技巧著重強(qiáng)調(diào)了算法優(yōu)化的思想。三、教學(xué)重點(diǎn)、難點(diǎn)重點(diǎn)重點(diǎn):算法設(shè)計(jì)的基本思想和策略算法優(yōu)化的技巧算法性能分析的方法難點(diǎn)難點(diǎn):將算法優(yōu)化的思想貫穿在設(shè)計(jì)過程中算法平均性能的分析技巧。四、教材名稱及主要參考書教材:《算法設(shè)計(jì)和分析基礎(chǔ)》中國(guó)科大計(jì)算機(jī)系教材參考書參考書:《計(jì)算機(jī)算法基礎(chǔ)》鄒海明余祥宣華中理工大學(xué)出版社《計(jì)算機(jī)算法導(dǎo)引》盧開

4、澄編著清華大學(xué)出版社“IntroductiontoAlgithms”T.H.CmenothersTheMITPress1990.五、課程章節(jié)主要內(nèi)容及學(xué)時(shí)分配第一章第一章緒論(2學(xué)時(shí))第一節(jié)基本概念第二節(jié)算法的設(shè)計(jì)和性能度量第三節(jié)標(biāo)準(zhǔn)記號(hào)與常用函數(shù)和公式第二章第二章分治與遞歸策略分治與遞歸策略(5學(xué)時(shí))第一節(jié)二分檢索第二節(jié)矩陣的快速乘法第三節(jié)快速傅里葉變換（FFT）第四節(jié)廣義表及遞歸算法第三章第三章排序與選擇排序與選擇（5學(xué)時(shí)）第一節(jié)簡(jiǎn)

5、單排序和SHELL排序第二節(jié)選擇排序和堆排序第三節(jié)快速排序和歸并排序第四節(jié)選擇問題第五節(jié)桶排序和基數(shù)排序第四章第四章貪心策略貪心策略（4學(xué)時(shí)）第一節(jié)文件存儲(chǔ)第二節(jié)背包問題第三節(jié)有限期的作業(yè)調(diào)度問題第五章第五章串匹配串匹配（4學(xué)時(shí)）第一節(jié)一般算法第二節(jié)RabinKarp算法第三節(jié)KnuthMrisPratt算法第四節(jié)BoyerMoe算法第六章第六章動(dòng)態(tài)規(guī)劃動(dòng)態(tài)規(guī)劃（8學(xué)時(shí)）第一節(jié)多段圖第二節(jié)最佳二分檢索第三節(jié)資源分配問題第五節(jié)01背包問題

6、第六節(jié)貨郎擔(dān)問題第七節(jié)最長(zhǎng)公共子序列第八節(jié)作業(yè)調(diào)度問題第七章第七章回溯法回溯法（5學(xué)時(shí)）第一節(jié)一般算法第二節(jié)皇后問題第三節(jié)子集和數(shù)問題第四節(jié)圖的著色第五節(jié)哈密頓環(huán)第六節(jié)背包問題第八章第八章檢索、遍歷與分枝限界法檢索、遍歷與分枝限界法（5學(xué)時(shí)）第一節(jié)代碼最優(yōu)化第二節(jié)對(duì)策樹第三節(jié)資源分配問題第四節(jié)01背包問題第五節(jié)貨郎擔(dān)問題第九章第九章數(shù)組壓縮存貯與數(shù)值計(jì)算數(shù)組壓縮存貯與數(shù)值計(jì)算（8學(xué)時(shí)）第一節(jié)數(shù)據(jù)的壓縮存貯技術(shù)第二節(jié)壓縮存貯時(shí)的矩陣運(yùn)算第