《算法設(shè)計與分析》實驗教學大綱

PAGE1PAGE3《算法設(shè)計與分析》實驗課程教學大綱課程編號：08051100課程名稱：算法設(shè)計與分析/TheDesignandAnalysisofComputerAlgorithms課程屬性：必修實驗屬性：非獨立設(shè)課開課學期：6學時：16適用專業(yè)：計算機科學與技術(shù)學分：3.5開課部門：數(shù)計學院考核要求：考查課程簡介：《算法設(shè)計與分析》課程主要學習和掌握幾種基本的算法：分治算法、動態(tài)規(guī)劃、貪心算法、回溯法、分支限界法，掌握算法設(shè)計的基本思想和策略、算法優(yōu)化的技巧、算法性能分析的方法。本課程著重于培養(yǎng)學生的算法設(shè)計與分析能力，程序設(shè)計和實現(xiàn)能力，培養(yǎng)學生分析問題和解決問題的能力，使學生掌握算法設(shè)計的基本方法，熟悉算法分析的基本技術(shù)，并能熟練運用一些常用算法，為學生進一步學習奠定良好的基礎(chǔ)。一、實驗項目設(shè)置及學時分配項目編號實驗項目名稱實驗類型開出要求學時分配1蠻力法程序設(shè)計驗證型必做22分治法程序設(shè)計驗證型必做43動態(tài)規(guī)劃程序設(shè)計驗證型必做44貪婪法程序設(shè)計驗證型必做25回溯法程序設(shè)計驗證型必做4學時總計16二、實驗內(nèi)容及教學要求實驗項目1：蠻力法程序設(shè)計1、教學內(nèi)容用蠻力法編程，解決字符串匹配問題用蠻力法打印1、2、3、4的全排列2、教學目標（1）掌握蠻力法的編程方法（2）學會用蠻力法進行程序設(shè)計實驗項目2：分治法程序設(shè)計1、教學內(nèi)容用分治法編程，解決找最大值和最小值問題用分治法編程，對數(shù)組元素進行快速排序、歸并排序用分治法思想進行編程，解決找第K大數(shù)的問題用分治法對棋盤覆蓋問題進行編程2、教學目標（1）掌握分治法的基本思想和方法（2）學會用分治法進行程序設(shè)計實驗項目3：動態(tài)規(guī)劃程序設(shè)計1、教學內(nèi)容用動態(tài)規(guī)劃解決0-1背包問題用動態(tài)規(guī)劃解決矩陣連乘問題用動態(tài)規(guī)劃解決找零錢問題用動態(tài)規(guī)劃解決最長公共子序列問題2、教學目標（1）掌握動態(tài)規(guī)劃算法的基本思想和方法（2）掌握設(shè)計動態(tài)規(guī)劃算法的步驟實驗項目4：貪心法程序設(shè)計1、教學內(nèi)容用貪心算法解決找零錢問題用貪心算法解決部分背包問題用貪心算法解決活動選擇問題2、教學目標（1）掌握貪心算法的基本思想和編程方法（2）學會用貪心算法來編程解決問題實驗項目5：回溯法程序設(shè)計1、教學內(nèi)容用回溯法解決八皇后問題用回溯法解決0-1背包問題用回溯法解決走迷宮問題用回溯法解決騎士巡游問題用回溯法解決數(shù)字全排列問題2、教學目標（1）掌握回溯法的基本思想和方法（2）學會用回溯法進行程序設(shè)計三、考核方式及要求和理論課一起算成績，實驗占總成績的20%。四、主要儀器設(shè)備及實驗材料項目編號實驗項目名稱主要儀器設(shè)備及臺（套）數(shù)實驗材料備注1蠻力法程序設(shè)計電腦一臺2分治法程序設(shè)計電腦一臺3動態(tài)規(guī)劃程序設(shè)計電腦一臺4貪婪法程序設(shè)計電腦一臺5回溯法程序設(shè)計電腦一臺五、教材及參考書王紅梅