《算法分析》課程教學(xué)大綱

1、算法分析課程教學(xué)大綱一、課程基本信息課程代碼：12130130課程英文名稱：Algorithms Analysis課程面向?qū)I(yè)：信息與計(jì)算科學(xué)專業(yè)課程類型：必修課先修課程：數(shù)據(jù)結(jié)構(gòu)學(xué)分： 4總學(xué)時(shí)：60(其中理論學(xué)時(shí)：44 ； 實(shí)驗(yàn)學(xué)時(shí)：16) 二、課程性質(zhì)與目的本課程是信息與計(jì)算專業(yè)的一門專業(yè)課，其內(nèi)容是研究算法的設(shè)計(jì)理論、分析方法和實(shí)現(xiàn)技術(shù)。算法設(shè)計(jì)的常用策略有：遞歸與分治策略、動(dòng)態(tài)規(guī)劃算法、貪心算法、回溯法和分支限界法。通過本課程的學(xué)習(xí)，使學(xué)生掌握算法設(shè)計(jì)的常用方法，以便運(yùn)用這些方法來設(shè)計(jì)解決一些常用的或較為復(fù)雜的實(shí)際問題的算法，并力爭做到快捷、有效，從而提高程序設(shè)計(jì)的質(zhì)量。除此，還要使

2、學(xué)生學(xué)會(huì)分析算法、估計(jì)算法的時(shí)空復(fù)雜性，以便理解并科學(xué)評估有關(guān)算法。三、課程教學(xué)內(nèi)容與要求第一章算法概述1、教學(xué)內(nèi)容與要求主要內(nèi)容：算法與程序、算法復(fù)雜性分析?；疽螅毫私馑惴ㄅc程序的聯(lián)系與區(qū)別；掌握算法基本概念，學(xué)會(huì)用算法復(fù)雜性分析算法。2、教學(xué)重點(diǎn)用算法復(fù)雜性分析算法。3、教學(xué)難點(diǎn)算法復(fù)雜性的學(xué)習(xí)。第二章遞歸與分治策略1、教學(xué)內(nèi)容與要求主要內(nèi)容：遞歸的概念、分治法的基本思想、分治算法的各種實(shí)例。基本要求: 理解遞歸的概念；掌握分治法的基本思想；掌握分治法的基本思想的具體實(shí)現(xiàn)及時(shí)間復(fù)雜度分析。2、教學(xué)重點(diǎn)分治法的基本思想的靈活運(yùn)用。3、教學(xué)難點(diǎn)對分治法的靈活運(yùn)用。第三章動(dòng)態(tài)規(guī)劃1、教學(xué)內(nèi)容

3、與要求主要內(nèi)容：動(dòng)態(tài)規(guī)劃算法的基本要素、動(dòng)態(tài)規(guī)劃法的基本思想及各種算法實(shí)例?；疽螅赫莆談?dòng)態(tài)規(guī)劃算法的基本要素；掌握用動(dòng)態(tài)規(guī)劃法設(shè)計(jì)算法。2、教學(xué)重點(diǎn)動(dòng)態(tài)規(guī)劃算法基本思想的具體實(shí)現(xiàn)及時(shí)間復(fù)雜度分析。3、教學(xué)難點(diǎn)動(dòng)態(tài)規(guī)劃算法基本思想的具體實(shí)現(xiàn)及時(shí)間復(fù)雜度分析。第四章貪心算法1、教學(xué)內(nèi)容與要求主要內(nèi)容：貪心算法的基本要素、貪心算法的基本思想及算法實(shí)例。基本要求：掌握貪心算法的基本要素；掌握貪心算法的基本思想以及用貪心算法設(shè)計(jì)算法。2、教學(xué)重點(diǎn)貪心算法基本思想的具體實(shí)現(xiàn)及時(shí)間復(fù)雜度分析。3、教學(xué)難點(diǎn)貪心算法基本思想的具體實(shí)現(xiàn)及時(shí)間復(fù)雜度分析。第五章回溯法1、教學(xué)內(nèi)容與要求主要內(nèi)容：回溯法的算法框架

4、、回溯法的各種算法實(shí)例?；疽螅赫莆栈厮莘ǖ乃惴蚣?；掌握用回溯法設(shè)計(jì)算法及時(shí)間復(fù)雜度分析。2、教學(xué)重點(diǎn)算法框架的具體應(yīng)用及算法設(shè)計(jì)。3、教學(xué)難點(diǎn)算法框架的具體應(yīng)用。第六章分支限界法1、教學(xué)內(nèi)容與要求主要內(nèi)容：分支限界法的基本思想、分支限界法的各種算法實(shí)例。基本要求：掌握分支限界法的基本思想；掌握用分支限界法設(shè)計(jì)算法及時(shí)間復(fù)雜度分析。2、教學(xué)重點(diǎn)算法框架的具體應(yīng)用及算法設(shè)計(jì)。3、教學(xué)難點(diǎn)算法框架的具體應(yīng)用。上機(jī)實(shí)驗(yàn)實(shí)驗(yàn)一：用遞歸算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題1、基本要求要求學(xué)生對上機(jī)實(shí)驗(yàn)的內(nèi)容用框圖描述算法步驟，寫出源程序，上機(jī)運(yùn)行求解，記錄和分析計(jì)算結(jié)果，并分析算法復(fù)雜性。寫出實(shí)驗(yàn)報(bào)告。

5、2、主要內(nèi)容用遞歸算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題，并分析算法復(fù)雜性3、操作要點(diǎn)首先寫出源程序，在C語言運(yùn)行環(huán)境下調(diào)試和運(yùn)行。4、主要儀器設(shè)備計(jì)算機(jī)實(shí)驗(yàn)二：用分治策略設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題1、基本要求要求學(xué)生對上機(jī)實(shí)驗(yàn)的內(nèi)容用框圖描述算法步驟，寫出源程序，上機(jī)運(yùn)行求解，記錄和分析計(jì)算結(jié)果，并分析算法復(fù)雜性。寫出實(shí)驗(yàn)報(bào)告。2、主要內(nèi)容用分治策略設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題，并分析算法復(fù)雜性3、操作要點(diǎn)首先寫出源程序，在C語言運(yùn)行環(huán)境下調(diào)試和運(yùn)行。4、主要儀器設(shè)備計(jì)算機(jī)實(shí)驗(yàn)三：用動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題1、基本要求要求學(xué)生對上機(jī)實(shí)驗(yàn)的內(nèi)容用框圖描述算法步驟，寫出源程序，上機(jī)運(yùn)

6、行求解，記錄和分析計(jì)算結(jié)果，并分析算法復(fù)雜性。寫出實(shí)驗(yàn)報(bào)告。2、主要內(nèi)容用動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題，并分析算法復(fù)雜性3、操作要點(diǎn)首先寫出源程序，在C語言運(yùn)行環(huán)境下調(diào)試和運(yùn)行。4、主要儀器設(shè)備計(jì)算機(jī)實(shí)驗(yàn)四：用貪心算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題1、基本要求要求學(xué)生對上機(jī)實(shí)驗(yàn)的內(nèi)容用框圖描述算法步驟，寫出源程序，上機(jī)運(yùn)行求解，記錄和分析計(jì)算結(jié)果，并分析算法復(fù)雜性。寫出實(shí)驗(yàn)報(bào)告。2、主要內(nèi)容用貪心算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題，并分析算法復(fù)雜性3、操作要點(diǎn)首先寫出源程序，在C語言運(yùn)行環(huán)境下調(diào)試和運(yùn)行。4、主要儀器設(shè)備計(jì)算機(jī)實(shí)驗(yàn)五：用回溯法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題1、基本要求要求

7、學(xué)生對上機(jī)實(shí)驗(yàn)的內(nèi)容用框圖描述算法步驟，寫出源程序，上機(jī)運(yùn)行求解，記錄和分析計(jì)算結(jié)果，并分析算法復(fù)雜性。寫出實(shí)驗(yàn)報(bào)告。2、主要內(nèi)容用回溯法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題，并分析算法復(fù)雜性3、操作要點(diǎn)首先寫出源程序，在C語言運(yùn)行環(huán)境下調(diào)試和運(yùn)行。4、主要儀器設(shè)備計(jì)算機(jī)實(shí)驗(yàn)六：用分支限界法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題1、基本要求要求學(xué)生對上機(jī)實(shí)驗(yàn)的內(nèi)容用框圖描述算法步驟，寫出源程序，上機(jī)運(yùn)行求解，記錄和分析計(jì)算結(jié)果，并分析算法復(fù)雜性。寫出實(shí)驗(yàn)報(bào)告。2、主要內(nèi)容用分支限界法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題，并分析算法復(fù)雜性3、操作要點(diǎn)首先寫出源程序，在C語言運(yùn)行環(huán)境下調(diào)試和運(yùn)行。4、主要儀器設(shè)備計(jì)算機(jī)四、

8、學(xué)時(shí)分配學(xué)時(shí)分配表序號(hào)教學(xué)內(nèi)容(按章填寫)學(xué)時(shí)課堂講授實(shí)驗(yàn)課習(xí)題課討論課其它1算法概述22遞歸與分治策略1043動(dòng)態(tài)規(guī)劃1044貪心算法845回溯法1046分支限界法4小計(jì)4416比例73%27%合計(jì)60實(shí)驗(yàn)學(xué)時(shí)分配表序號(hào)實(shí)驗(yàn)項(xiàng)目名稱實(shí)驗(yàn)學(xué)時(shí)實(shí)驗(yàn)類型每組實(shí)驗(yàn)人數(shù)說明驗(yàn)證性設(shè)計(jì)性綜 合性其它1用遞歸或分治策略設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題21人2用分治策略設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題21人3用動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題21人4用貪心算法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題21人5用回溯法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題41人6用分支限界法設(shè)計(jì)程序，解決課后的一個(gè)習(xí)題41人小計(jì)16五、教學(xué)環(huán)節(jié)與教學(xué)要求課堂講授的教學(xué)方法和手段主要采用以大量實(shí)例闡明算法的理論基礎(chǔ)，從而掌握各種算法的設(shè)計(jì)方法。實(shí)驗(yàn)環(huán)節(jié)要求學(xué)生靈活使用數(shù)學(xué)軟件完成各種算法的實(shí)現(xiàn)的目的。作業(yè)每堂課布置2到3題，以提高學(xué)生的計(jì)算技能為主。六、課程考核辦法1、作業(yè)等：20%2、實(shí)驗(yàn)成績：10%（檢查程序和計(jì)算結(jié)果）3、期末考試