算法分析與設(shè)計(jì)(一)課程教學(xué)大綱

1、 算法分析與設(shè)計(jì)教學(xué)大綱課程性質(zhì)專業(yè)限選課課程編號(hào)xx882040課程名稱算法分析與設(shè)計(jì)適用專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)，軟件工程，物聯(lián)網(wǎng)工程，網(wǎng)絡(luò)工程先修課程C語言程序設(shè)計(jì)、C+程序設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)總學(xué)時(shí) 48 其中理論 36 學(xué)時(shí)，實(shí)驗(yàn) 12 學(xué)時(shí)學(xué)分?jǐn)?shù)3一、課程簡介 算法分析與設(shè)計(jì)是一門理論性與實(shí)踐性兼顧的課程，是面向設(shè)計(jì)，且處于計(jì)算機(jī)科學(xué)與技術(shù)學(xué)科核心地位的教育課程。本課程系統(tǒng)介紹了軟件設(shè)計(jì)中常用的算法設(shè)計(jì)與分析方法，通過對(duì)算法設(shè)計(jì)策略的系統(tǒng)學(xué)習(xí)與研究，理解和掌握算法設(shè)計(jì)的主要方法，鍛煉學(xué)生獨(dú)立分析問題和解決問題的能力，為開發(fā)高效的軟件系統(tǒng)及相關(guān)領(lǐng)域的研究工作奠定堅(jiān)實(shí)的基礎(chǔ)。課程是“編譯原理”和

2、“軟件工程”等專業(yè)核心課程的基礎(chǔ)課，為學(xué)習(xí)專業(yè)課程及提高軟件設(shè)計(jì)水平打下良好的基礎(chǔ)。二、課程教學(xué)目標(biāo)通過本課程的學(xué)習(xí)，學(xué)生應(yīng)實(shí)現(xiàn)如下目標(biāo)：1、知識(shí)目標(biāo)：了解：算法的概念，程序與算法的區(qū)別；遞歸、分治策略的基本原理和效率分析動(dòng)態(tài)規(guī)劃算法的概念；貪心算法的基本思想、適用條件；理解回溯法的基本思想及效率估計(jì)，限界函數(shù)；分支限界法的基本思想及效率估計(jì)。掌握：算法時(shí)間復(fù)雜性的估計(jì)與表示；遞歸、分治的概念，設(shè)計(jì)有效算法的分治策略；動(dòng)態(tài)規(guī)劃算法的基本要素、設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟以及典型問題的應(yīng)用與分析。貪心算法的設(shè)計(jì)策略、基本思想、適用條件，貪心算法的典型問題的解決方法與分析；回溯法在典型問題的應(yīng)用及分析及

3、解決方法；分支限界法的算法框架及在典型問題的應(yīng)用。2、能力目標(biāo)：（1）對(duì)C+程序設(shè)計(jì)有進(jìn)一步的認(rèn)識(shí)和了解，提高程序調(diào)試能力；（2）掌握算法設(shè)計(jì)的基本策略，達(dá)到融會(huì)貫通之效；三、課程教學(xué)基本要求本課程的基本要求是讓學(xué)生理解計(jì)算機(jī)算法效率分析與設(shè)計(jì)所涉及的基本概念和基礎(chǔ)知識(shí)，掌握基本的算法分析方法和常見的算法設(shè)計(jì)方法，能熟練應(yīng)用課程介紹的算法設(shè)計(jì)方法來解決軟件開發(fā)中的實(shí)際問題。通過對(duì)算法實(shí)例的分析，進(jìn)一步加深學(xué)生對(duì)算法設(shè)計(jì)方法的認(rèn)識(shí)和理解。四、課程教學(xué)模塊（或教學(xué)內(nèi)容）與學(xué)時(shí)分配序號(hào)教學(xué)模塊知識(shí)點(diǎn)學(xué)時(shí)1項(xiàng)目一概述理解：算法的概念、算法的時(shí)間復(fù)雜性和空間復(fù)雜性掌握：求解問題的基本步驟掌握：算法運(yùn)行時(shí)

4、間的估計(jì)42項(xiàng)目二遞歸與分治策略掌握：遞歸的概念，掌握設(shè)計(jì)有效算法的分治策略理解：分治策略的基本原理和效率分析，掌握設(shè)計(jì)有效算法的分治策略 103項(xiàng)目三動(dòng)態(tài)規(guī)劃理解：動(dòng)態(tài)規(guī)劃算法的概念 掌握動(dòng)態(tài)規(guī)劃算法的基本要素、掌握設(shè)計(jì)動(dòng)態(tài)規(guī)劃算法的步驟以及典型問題的應(yīng)用與分析104項(xiàng)目四貪心算法理解：貪心算法的基本思想、適用條件掌握：貪心算法的設(shè)計(jì)策略，掌握貪心算法典型問題的應(yīng)用與分析85項(xiàng)目五回溯法理解：回溯法的基本思想及效率估計(jì)，限界函數(shù)掌握：回溯法在典型問題的應(yīng)用及分析106項(xiàng)目六分支限界法理解：分支限界法的基本思想及效率估計(jì)掌握：分支限界法的算法框架，分支限界法在典型問題的應(yīng)用47項(xiàng)目七概率算法理

5、解：分概率法的基本思想及效率估計(jì)掌握：概率法在典型問題的應(yīng)用2序號(hào)實(shí)驗(yàn)項(xiàng)目名稱內(nèi)容摘要實(shí)驗(yàn)學(xué)時(shí)實(shí)驗(yàn)類型開出要求1C/C+環(huán)境及遞歸算法熟悉C/C+語言的集成開發(fā)環(huán)境，加深對(duì)遞歸過程的理解2設(shè)計(jì)性必做2分治算法熟悉二分搜索算法和快速排序算法，初步掌握分治算法2設(shè)計(jì)性必做3動(dòng)態(tài)規(guī)劃算法熟悉最長公共子序列問題的算法，掌握動(dòng)態(tài)規(guī)劃算法。2設(shè)計(jì)性必做4動(dòng)態(tài)規(guī)劃算法熟悉最長最大字段和問題的算法，進(jìn)一步掌握動(dòng)態(tài)規(guī)劃算法。2設(shè)計(jì)性選做5貪心算法熟悉多機(jī)調(diào)度問題的算法，初步掌握貪心算法2設(shè)計(jì)性必做6貪心算法掌握背包問題的算法。進(jìn)一步掌握貪心算法2設(shè)計(jì)性必做7回溯算法掌握裝載問題的回溯算法，初步掌握回溯算法2設(shè)計(jì)

6、性選做8回溯算法掌握0-1背包問題的回溯算法，進(jìn)一步掌握回溯算法2設(shè)計(jì)性必做9分支限界法掌握旅行商售貨員問題的分支限界算法，區(qū)分分支限界算法與回溯算法的區(qū)別，加深對(duì)分支限界法的理解。2驗(yàn)證性選做10概率算法掌握拉斯維加斯算法，加深對(duì)概率算法的理解2驗(yàn)證性選做五、教學(xué)方法與策略1、講授法：介紹算法設(shè)計(jì)策略的基本思想，然后從解決計(jì)算機(jī)科學(xué)與應(yīng)用中出現(xiàn)的實(shí)際問題入手，由簡到繁地描述幾個(gè)經(jīng)典的精巧算法，同時(shí)對(duì)每個(gè)算法所需要的時(shí)間和空間進(jìn)行分析。2、實(shí)驗(yàn)課：學(xué)生在上課過程中完成6個(gè)設(shè)計(jì)性實(shí)驗(yàn)，在課后自行安排時(shí)間完成4個(gè)試驗(yàn)，通過各個(gè)實(shí)踐性環(huán)節(jié)的訓(xùn)練，學(xué)生基本能夠掌握算法設(shè)計(jì)的主要方法。培養(yǎng)學(xué)生嚴(yán)謹(jǐn)?shù)目茖W(xué)態(tài)度、科學(xué)的思維方法以及技術(shù)創(chuàng)新能力。六、學(xué)生學(xué)習(xí)成效考核方式考核環(huán)節(jié)構(gòu)成（均為100分制）評(píng)分依據(jù)占總成績的比重上課出勤、實(shí)驗(yàn)上課缺席一次扣2 分，缺課達(dá)1/3取消資格。40%期末考試成績期末考試卷面成績?yōu)闇?zhǔn)60