1、算法分析與設(shè)計(jì)課程大綱一、課程概況所屬專業(yè):物聯(lián)網(wǎng)工程專業(yè)開(kāi)課單位：數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院課程類(lèi)型:專業(yè)選修課程課程代碼:07495550開(kāi)課學(xué)期:4學(xué)分：2學(xué)時(shí)：32核心課程:否擬使用教材：國(guó)內(nèi)(外)現(xiàn)有教材：算法與數(shù)據(jù)結(jié)構(gòu)傅清祥等編 2001年1月第1版電子工業(yè)出版社計(jì)算機(jī)算法設(shè)計(jì)與分析王曉東編著 2012年第4版:電子工業(yè)出版社二、課程描述算法分析與設(shè)計(jì)是一門(mén)面向設(shè)計(jì)，且處于計(jì)算機(jī)學(xué)科核心地位的教育課程。設(shè)計(jì)一個(gè)高效的程序不僅需要編程技巧，更需要合理的數(shù)據(jù)組織和清晰高效的算法，這正是計(jì)算機(jī)科學(xué)領(lǐng)域里算法分析與設(shè)計(jì)所研究的主要內(nèi)容。三、課程目標(biāo)本課程的教學(xué)目的是講授在計(jì)算機(jī)應(yīng)用中常常遇到的實(shí)

2、際問(wèn)題的解法，講授設(shè)計(jì)和分析各種算法的基本原理、方法和技術(shù)，培養(yǎng)學(xué)生對(duì)算法復(fù)雜性進(jìn)行正確分析的能力。四、教學(xué)要求依據(jù)課程的性質(zhì)、目的及任務(wù)，教學(xué)基本要求是緊扣多媒體教學(xué)、課后答疑等幾個(gè)主要環(huán)節(jié)，要求學(xué)生系統(tǒng)地了解、熟悉和掌握算法分析與設(shè)計(jì)基本知識(shí)。授課教師將按照學(xué)校本科教學(xué)工作有關(guān)要求做好教學(xué)各項(xiàng)工作，嚴(yán)格要求自己做到不遲到、不早退。將根據(jù)本大綱要求，認(rèn)真?zhèn)湔n完成教案與講稿編寫(xiě)等各項(xiàng)課前準(zhǔn)備工作；授課過(guò)程力求內(nèi)容充實(shí)、概念準(zhǔn)確、思路清晰、詳略得當(dāng)、邏輯性強(qiáng)、重難點(diǎn)突出；同時(shí)重視對(duì)學(xué)生的學(xué)習(xí)方法指導(dǎo)和課堂教學(xué)效果信息的反饋，實(shí)現(xiàn)教與學(xué)的雙向互動(dòng)；將結(jié)合課程目標(biāo)要求，做好考核內(nèi)容設(shè)計(jì)，并嚴(yán)格按照本

3、大綱要求做好出勤率統(tǒng)計(jì)、作業(yè)評(píng)價(jià)等各項(xiàng)工作。通過(guò)本課程教學(xué)，使學(xué)生不僅能夠?qū)W習(xí)到算法分析與設(shè)計(jì)的相關(guān)理論知識(shí)與設(shè)計(jì)分析方法，還能提高實(shí)踐操作與應(yīng)用的專業(yè)技能，以及分析問(wèn)題與解決問(wèn)題的全面綜合素質(zhì)。學(xué)生應(yīng)根據(jù)課程大綱要求制定本門(mén)課程學(xué)習(xí)計(jì)劃，加強(qiáng)學(xué)業(yè)管理，嚴(yán)格自我要求，提升自主學(xué)習(xí)能力，主動(dòng)適應(yīng)課程學(xué)習(xí)要求。參與課堂教學(xué)活動(dòng)不遲到、不早退，無(wú)正當(dāng)理由不請(qǐng)假，上課認(rèn)真聽(tīng)講，不做任何與課堂教學(xué)無(wú)關(guān)事宜，積極與授課教師進(jìn)行教學(xué)互動(dòng)，同時(shí)利用課余時(shí)間做好預(yù)習(xí)、復(fù)習(xí)、課外書(shū)籍閱讀等工作，主動(dòng)與同學(xué)開(kāi)展合作學(xué)習(xí)，認(rèn)真完成任課教師布置的各項(xiàng)作業(yè)。五、考核方式及要求教學(xué)過(guò)程是知識(shí)消化、理解和升華的過(guò)程，各個(gè)教學(xué)

4、環(huán)節(jié)之間是相互影響、相互依存的，各個(gè)環(huán)節(jié)的統(tǒng)一協(xié)調(diào)，齊抓并重是提高教學(xué)質(zhì)量的根本保證，也是培養(yǎng)學(xué)生自主學(xué)習(xí)能力的必要措施。因此，在教學(xué)過(guò)程中對(duì)學(xué)生的學(xué)習(xí)過(guò)程實(shí)施全程考核。課程將考勤、上機(jī)作業(yè)、答疑質(zhì)疑、綜合實(shí)驗(yàn)情況量化成分值作為本課程的平時(shí)成績(jī)。課程總成績(jī) = 平時(shí)分（60）+期末考試（40）課程期末考試形式：閉卷筆試六、課程內(nèi)容第一章算法引論（授課時(shí)間：第四學(xué)期第12周）教學(xué)目標(biāo)：了解算法的計(jì)算復(fù)雜性分析方法，理解算法分析的基本理論教學(xué)重點(diǎn)：掌握算法分析的基本概念教學(xué)難點(diǎn)：計(jì)算復(fù)雜性分析方法學(xué)時(shí)：4學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：（1）算法的基本概念；（2）表達(dá)算法的抽象機(jī)制；（3）描

5、述算法的方法；（4）算法的計(jì)算復(fù)雜性分析方法。學(xué)習(xí)方法：認(rèn)真聽(tīng)講、積極思考，小組討論課后作業(yè)：算法性能分析第二章分治算法（授課時(shí)間：第四學(xué)期第34周）教學(xué)目標(biāo)：理解典型范例中遞歸與分治策略應(yīng)用技巧，掌握遞歸與分治策教學(xué)重點(diǎn)：分治法的基本思想教學(xué)難點(diǎn)：遞歸與分治策略應(yīng)用技巧學(xué)時(shí)：4學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：（1）遞歸的概念；（2）分治法的基本思想；（3）二分搜索技術(shù)；（4）Strassen陣乘法。學(xué)習(xí)方法：認(rèn)真聽(tīng)講、積極思考，小組討論課后作業(yè)：最接近點(diǎn)對(duì)問(wèn)題，循環(huán)賽日程表第三章貪心算法（授課時(shí)間：第四學(xué)期第56周）教學(xué)目標(biāo)：了解貪心算法的理論基礎(chǔ)及基本要素，理解典型范例中貪心算法的設(shè)

6、計(jì)思想教學(xué)重點(diǎn)：貪心算法的理論基礎(chǔ)教學(xué)難點(diǎn)：貪心算法的設(shè)計(jì)要點(diǎn)學(xué)時(shí)：4學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：（1）貪心算法的基本要素；（2）哈夫曼編碼；（3）最小生成樹(shù)；（4）多機(jī)調(diào)度問(wèn)題。學(xué)習(xí)方法：認(rèn)真聽(tīng)講、積極思考，小組討論課后作業(yè)：最優(yōu)裝載，活動(dòng)安排第四章動(dòng)態(tài)規(guī)劃（授課時(shí)間：第四學(xué)期第79周）教學(xué)目標(biāo)：理解典型范例中動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)思想教學(xué)重點(diǎn)：掌握動(dòng)態(tài)規(guī)劃算法的基本要求以及算法的設(shè)計(jì)要點(diǎn)教學(xué)難點(diǎn)：動(dòng)態(tài)規(guī)劃算法的基本要素學(xué)時(shí)：6學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：（1）最長(zhǎng)公共子序列；（2）凸多邊形最優(yōu)三角剖分；（3）流水作業(yè)調(diào)度；（4）圖像壓縮；（5）動(dòng)態(tài)規(guī)劃加速原理。學(xué)習(xí)方法：認(rèn)

7、真聽(tīng)講、積極思考，小組討論課后作業(yè)：最長(zhǎng)公共子序列，0l背包問(wèn)題第五章回溯法（授課時(shí)間：第四學(xué)期第1012周）教學(xué)目標(biāo)：掌握回溯法的算法框架和應(yīng)用技巧教學(xué)重點(diǎn)：回溯法的算法框架教學(xué)難點(diǎn)：理解回溯法的效率分析方法學(xué)時(shí)：6學(xué)時(shí)教學(xué)方法：講授法、演示法主要內(nèi)容：（1）裝載問(wèn)題；（2）圖的m著色問(wèn)題；（3）旅行售貨員問(wèn)題；（4）連續(xù)郵資問(wèn)題；（5）回溯法的效率分析。學(xué)習(xí)方法：認(rèn)真聽(tīng)講、積極思考，小組討論課后作業(yè)：n后問(wèn)題，旅行售貨員問(wèn)題第六章分支限界法（授課時(shí)間：第四學(xué)期第1315周）教學(xué)目標(biāo)：理解分支限界法的基本思想及應(yīng)用教學(xué)重點(diǎn)：分支限界法的算法框架教學(xué)難點(diǎn)：掌握典型范例中分支限界法的應(yīng)用技巧學(xué)時(shí)：6學(xué)時(shí)教學(xué)方法：教學(xué)法、演示法主要內(nèi)容：（1）單源最短路徑問(wèn)題；（2）電路板排列問(wèn)題；（3）布線問(wèn)題；（4）批處理作業(yè)調(diào)度。學(xué)習(xí)方法：認(rèn)真聽(tīng)講、積極思考，小組討論課后作業(yè)：0-1背包問(wèn)題，批處理作業(yè)調(diào)度第七章NP完全性理論（授課時(shí)間：第四學(xué)期第1617周）教學(xué)目標(biāo)：理解P類(lèi)與NP類(lèi)問(wèn)題及應(yīng)用教學(xué)重點(diǎn)：P類(lèi)與NP類(lèi)問(wèn)題相關(guān)模型教學(xué)難點(diǎn)：理