《算法分析與設(shè)計(jì)》課程實(shí)驗(yàn)教學(xué)大綱

《算法分析與設(shè)計(jì)》課程實(shí)驗(yàn)教學(xué)大綱《Analysis&DesignofAlgorithm》ExperimentOutline一、課程基本信息課程代碼：16158603課程名稱：算法分析與設(shè)計(jì)英文名稱:Analysis&DesignofAlgorithm實(shí)驗(yàn)總學(xué)時(shí)：12適用專業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)本科生課程類別：專業(yè)課先修課程：C或JAVA語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)教學(xué)的總體目的和要求1、對(duì)學(xué)生的要求(1)準(zhǔn)備好上機(jī)所需的程序。(2)上機(jī)輸入和調(diào)試自己所編的程序。一人一組，獨(dú)立上機(jī)調(diào)試，上機(jī)時(shí)出現(xiàn)的問(wèn)題，最好獨(dú)立解決。(3)上機(jī)結(jié)束后，要求整理出實(shí)驗(yàn)報(bào)告的實(shí)驗(yàn)項(xiàng)目，須在規(guī)定時(shí)間內(nèi)完成并上交。實(shí)驗(yàn)報(bào)告應(yīng)包括：題目、實(shí)驗(yàn)環(huán)境、算法描述、程序?qū)崿F(xiàn)、運(yùn)行結(jié)果、對(duì)運(yùn)行情況所作時(shí)間復(fù)雜性等的分析。2、對(duì)教師的要求教師要向?qū)W生明確每次實(shí)驗(yàn)任務(wù)。在實(shí)驗(yàn)過(guò)程中，原則上以學(xué)生思考、學(xué)生相互討論為主，反映比較普遍的問(wèn)題，應(yīng)給予統(tǒng)一的解答。對(duì)程序調(diào)試過(guò)程中，學(xué)生反映的問(wèn)題，可及時(shí)給予釋疑。教師應(yīng)當(dāng)配合實(shí)驗(yàn)室管理人員，保證實(shí)驗(yàn)設(shè)備和軟件環(huán)境的正常工作狀態(tài)。3、對(duì)實(shí)驗(yàn)條件的要求保證一人一臺(tái)計(jì)算機(jī)、安裝C語(yǔ)言或C++語(yǔ)言環(huán)境、能夠訪問(wèn)互聯(lián)網(wǎng)。實(shí)驗(yàn)教學(xué)內(nèi)容實(shí)驗(yàn)項(xiàng)目一：遞歸程序?qū)崿F(xiàn)實(shí)驗(yàn)名稱：數(shù)字計(jì)數(shù)問(wèn)題問(wèn)題定義：一本書(shū)的頁(yè)碼從自然數(shù)1開(kāi)始順序編碼到N。頁(yè)碼按照通常的習(xí)慣編排，即每個(gè)頁(yè)碼不能含多余的前倒數(shù)0，例如，、第6頁(yè)的頁(yè)碼為6，不能是06、006等。數(shù)字計(jì)數(shù)問(wèn)題要求從鍵盤(pán)輸入頁(yè)數(shù)N，輸出全書(shū)頁(yè)碼中分別用到0、1、2、3、4、5、6、7、8、9的次數(shù)；實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)求解“數(shù)字計(jì)數(shù)問(wèn)題”的算法，分析時(shí)間復(fù)雜性，并用C或C++語(yǔ)言編程實(shí)現(xiàn)，調(diào)試通過(guò)，得出正確答案。實(shí)驗(yàn)性質(zhì)：設(shè)計(jì)型實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)?zāi)康呐c要求：掌握遞歸算法的概念和基本思想，分析并掌握“數(shù)字計(jì)數(shù)”問(wèn)題的遞歸算法；掌握C/C++語(yǔ)言的基本庫(kù)函數(shù)；實(shí)驗(yàn)條件：C或C++，互聯(lián)網(wǎng)絡(luò)環(huán)境研究與思考：分析算法時(shí)間復(fù)雜性，能否將遞歸程序非遞歸化？實(shí)驗(yàn)項(xiàng)目二：遞歸與分治策略實(shí)驗(yàn)名稱：棋盤(pán)覆蓋問(wèn)題問(wèn)題定義：在一個(gè)2k×2k

個(gè)方格組成的棋盤(pán)中，恰有一個(gè)方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤(pán)為一特殊棋盤(pán)。在棋盤(pán)覆蓋問(wèn)題中，要用圖示的4種不同形態(tài)的L型骨牌覆蓋給定的特殊棋盤(pán)上除特殊方格以外的所有方格，且任何2個(gè)L型骨牌不得重疊覆蓋；實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)求解“棋盤(pán)覆蓋問(wèn)題”的算法，分析時(shí)間復(fù)雜性，并用C或C++語(yǔ)言編程實(shí)現(xiàn)，調(diào)試通過(guò)，得出正確答案。實(shí)驗(yàn)性質(zhì)：設(shè)計(jì)型實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)?zāi)康呐c要求：進(jìn)一步熟悉C/C++語(yǔ)言的集成開(kāi)發(fā)環(huán)境；通過(guò)本實(shí)驗(yàn)加深對(duì)遞歸與分治策略的理解和運(yùn)用；實(shí)驗(yàn)條件：C或C++，互聯(lián)網(wǎng)絡(luò)環(huán)境研究與思考：分析算法的時(shí)間復(fù)雜性，分析思考子問(wèn)題相互獨(dú)立在“棋盤(pán)覆蓋問(wèn)題”的具體體現(xiàn)。在講解這個(gè)實(shí)驗(yàn)過(guò)程中，介紹目前以AI和大數(shù)據(jù)為主要代表的第四次工業(yè)革命前景和現(xiàn)狀，進(jìn)一步認(rèn)識(shí)鄧小平提出的重要診斷：“科學(xué)是第一生產(chǎn)力”。實(shí)驗(yàn)項(xiàng)目三：動(dòng)態(tài)規(guī)劃算法(1)實(shí)驗(yàn)名稱：最長(zhǎng)公共子序列問(wèn)題定義：已知兩個(gè)串X和Y，求最長(zhǎng)公共子序列。(詳見(jiàn)教材)實(shí)驗(yàn)內(nèi)容：分析并掌握“最長(zhǎng)公共子序列”

問(wèn)題的動(dòng)態(tài)規(guī)劃算法求解方法，并用C或C++語(yǔ)言編程實(shí)現(xiàn)，調(diào)試通過(guò)，得出正確答案。實(shí)驗(yàn)性質(zhì)：設(shè)計(jì)型實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)?zāi)康呐c要求：通過(guò)動(dòng)態(tài)規(guī)劃算法的示例程序理解動(dòng)態(tài)規(guī)劃算法的基本思想；運(yùn)用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問(wèn)題加深對(duì)動(dòng)態(tài)規(guī)劃算法的理解和運(yùn)用；實(shí)驗(yàn)條件：C或C++，互聯(lián)網(wǎng)絡(luò)環(huán)境研究與思考：分析LCS的算法時(shí)間復(fù)雜性，思考其最優(yōu)子結(jié)構(gòu)和遞推方程式。在講解這個(gè)實(shí)驗(yàn)過(guò)程中，簡(jiǎn)要介紹生物信息學(xué)這個(gè)本世紀(jì)的新興學(xué)科，從而更深入地認(rèn)識(shí)“生物、醫(yī)藥、數(shù)學(xué)、化學(xué)、物理手段、計(jì)算機(jī)算法技術(shù)、存儲(chǔ)技術(shù)等等”的大融合，大統(tǒng)一，進(jìn)而推動(dòng)技術(shù)的更高層面的發(fā)展。實(shí)驗(yàn)項(xiàng)目四：動(dòng)態(tài)規(guī)劃算法(2)實(shí)驗(yàn)名稱：最大子段和問(wèn)題問(wèn)題定義：已知串X，求X的最大子段和（詳見(jiàn)教材）。實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)求解“最大子段和”的算法，并用C或C++語(yǔ)言編程實(shí)現(xiàn)，調(diào)試通過(guò)，得出正確答案。實(shí)驗(yàn)性質(zhì)：設(shè)計(jì)型實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)?zāi)康呐c要求：通過(guò)動(dòng)態(tài)規(guī)劃算法的示例程序理解動(dòng)態(tài)規(guī)劃算法的基本思想；運(yùn)用動(dòng)態(tài)規(guī)劃算法解決實(shí)際問(wèn)題加深對(duì)動(dòng)態(tài)規(guī)劃算法的理解和運(yùn)用；實(shí)驗(yàn)條件：C或C++，互聯(lián)網(wǎng)絡(luò)環(huán)境研究與思考：分析最大子段和問(wèn)題的算法時(shí)間復(fù)雜性，思考其最優(yōu)子結(jié)構(gòu)和遞推方程式。實(shí)驗(yàn)項(xiàng)目五：貪心算法實(shí)驗(yàn)名稱：會(huì)場(chǎng)安排問(wèn)題問(wèn)題定義：假設(shè)在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)（N個(gè)活動(dòng)），每個(gè)活動(dòng)事先給定活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間，試用貪心算法求出最少需要多少會(huì)場(chǎng)，并求出每個(gè)活動(dòng)安排在第幾個(gè)會(huì)場(chǎng)；實(shí)驗(yàn)內(nèi)容：掌握貪心算法的概念和基本思想，分析并掌握“會(huì)場(chǎng)安排”問(wèn)題的貪心算法；掌握C/C++語(yǔ)言的基本庫(kù)函數(shù)；實(shí)驗(yàn)性質(zhì)：設(shè)計(jì)型實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)?zāi)康呐c要求：通過(guò)貪心算法的示例程序理解貪心算法的基本思想；運(yùn)用貪心算法解決實(shí)際問(wèn)題加深對(duì)貪心算法的理解和運(yùn)用；實(shí)驗(yàn)條件：C或C++，互聯(lián)網(wǎng)絡(luò)環(huán)境研究與思考：分析程序的算法時(shí)間復(fù)雜性，理解該問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。在講解這個(gè)實(shí)驗(yàn)過(guò)程中，融合“從實(shí)際出發(fā)”的唯物論，從而在算法設(shè)計(jì)過(guò)程中，要善于針對(duì)問(wèn)題的特殊性，找到突破口，設(shè)計(jì)出更高效的算法。實(shí)驗(yàn)項(xiàng)目六：回溯法實(shí)驗(yàn)名稱：0-1背包問(wèn)題問(wèn)題定義：已知i種物品的重量wi和價(jià)值vi，背包的容重W，求價(jià)值最大的物品裝包方案（任一物品不能選擇部分入包，即物品j要么全部裝包，要么不裝包）。實(shí)驗(yàn)內(nèi)容：設(shè)計(jì)求解“0-1背包問(wèn)題”的算法，并用C或C++語(yǔ)言編程實(shí)現(xiàn)，調(diào)試通過(guò)，得出正確答案。實(shí)驗(yàn)性質(zhì)：設(shè)計(jì)型實(shí)驗(yàn)學(xué)時(shí)：2實(shí)驗(yàn)?zāi)康呐c要求：通過(guò)回溯法的示例程序理解回溯法的基本思想；運(yùn)用回溯法解決實(shí)際問(wèn)題進(jìn)一步加深對(duì)回溯法的理解和運(yùn)用；實(shí)驗(yàn)條件：C或C++，互聯(lián)網(wǎng)絡(luò)環(huán)境研究與思考：分析程序的算法時(shí)間復(fù)雜性，該問(wèn)題的回溯法求解，當(dāng)問(wèn)題規(guī)模足夠大時(shí)，是否可行？為什么？在講解這個(gè)實(shí)驗(yàn)過(guò)程中，要通過(guò)該問(wèn)題的多種算法的設(shè)計(jì)與實(shí)現(xiàn)（BF算法、分治算法、DP算法），強(qiáng)調(diào)馬克思主義哲學(xué)的方法論，使得我們?cè)谒伎紗?wèn)題的求解方法時(shí)，能夠一切從實(shí)際出發(fā)，理論聯(lián)系實(shí)際。四、考核方式共6個(gè)實(shí)驗(yàn)，須交6個(gè)問(wèn)題的求解算法，占平時(shí)成績(jī)的15%交兩份實(shí)驗(yàn)報(bào)告，給予評(píng)分，作為平時(shí)成績(jī)的一部分，占平時(shí)成績(jī)的5%五、推薦實(shí)驗(yàn)教材和教學(xué)參考書(shū)實(shí)驗(yàn)教材：《算法設(shè)計(jì)與實(shí)驗(yàn)題解》，王曉東編著，電子工業(yè)出版社，2007