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

算法設(shè)計與分析課程教學(xué)大綱【課程編碼】JSZX0490【適用專業(yè)】運算機(jī)科學(xué)與技術(shù)【課時】理論課時：54，實驗課時：16【學(xué)分】3【課程性質(zhì)、目標(biāo)和要求】《算法設(shè)計與分析》是運算機(jī)科學(xué)與技術(shù)專業(yè)的專業(yè)課。無論是計算科學(xué)仍是計算實踐，算法都在其中扮演著重要角色。本課程的教學(xué)目的是教學(xué)在運算機(jī)應(yīng)用中常常碰到的實際問題的解法，教學(xué)設(shè)計和分析各類算法的大體原理、方式和技術(shù)，培育學(xué)生對算法復(fù)雜性進(jìn)行正確分析的能力。課程大體要求是⑴掌握算法分析的大體概念和理論。⑵掌握算法設(shè)計技術(shù)和分析算法和算法復(fù)雜性?！窘虒W(xué)時刻安排】本課程計3學(xué)分，理論課時54+實驗課時16,學(xué)時分派如下：序號課程內(nèi)容/實驗名稱實驗類型課時備注1算法引論理論課時4

2遞歸與分治策略/分治法實驗設(shè)計理論課時6+實驗課時83動態(tài)規(guī)劃/動態(tài)規(guī)劃實驗設(shè)計理論課時8+實驗課時8

4貪心算法理論課時65回溯法理論課時66分支限界法理論課時67概率算法理論課時68NP完全性理論理論課時49近似算法理論課時410算法優(yōu)化策略理論課時4

合計理論課時54+實驗課時16【教學(xué)內(nèi)容要點】第一章算法引論一、學(xué)習(xí)目的要求1．了解算法的計算復(fù)雜性分析方式2．理解算法分析的大體理論3．掌握算法分析的大體概念二、主要教學(xué)內(nèi)容1.算法的大體概念2.表達(dá)算法的抽象機(jī)制3.采用Java語言與自然語言相結(jié)合的方式描述算法的方式4.算法的計算復(fù)雜性分析方式第二章遞歸與分治策略一、學(xué)習(xí)目的要求1．理解典型范例中遞歸與分治策略應(yīng)用技能2．掌握遞歸與分治策略3．掌握數(shù)學(xué)歸納法證明算法正確性方式二、主要教學(xué)內(nèi)容1.遞歸的概念2.分治法的大體思想3.二分搜索技術(shù)4.大整數(shù)的乘法5.Strassen陣乘法6.棋盤覆蓋7.歸并排序8.快速排序9.線性時刻選擇10.最接近點對問題11.循環(huán)賽日程表第三章動態(tài)計劃一、學(xué)習(xí)目的要求1．理解典型范例中動態(tài)計劃算法的設(shè)計思想2．掌握動態(tài)計劃算法的大體要求和算法的設(shè)計要點二、主要教學(xué)內(nèi)容1.矩陣連乘問題2.動態(tài)計劃算法的大體要素3.最長公共子序列4.最大子段和5.凸多邊形最優(yōu)三角剖分6.多邊形游戲7.圖像緊縮8.電路布線9.流水作業(yè)調(diào)度10.0—l背包問題11.最優(yōu)二叉搜索樹12.動態(tài)計劃加速原理三、課堂討論選題1.最長公共子序列2.0—l背包問題第四章貪婪算法一、學(xué)習(xí)目的要求1．了解貪婪算法的理論基礎(chǔ)及大體要素2.理解典型范例中貪婪算法的設(shè)計思想3.掌握貪婪算法的設(shè)計要點二、主要教學(xué)內(nèi)容1.活動安排問題2.貪婪算法的大體要素3.最優(yōu)裝載4.哈夫曼編碼5.單源最短路徑6.最小生成樹7.多機(jī)調(diào)度問題8.貪婪算法的理論基礎(chǔ)三、課堂討論選題1.最優(yōu)裝載2.單源最短路徑第五章回溯法一、學(xué)習(xí)目的要求1．理解回溯法的效率分析方式2．掌握回溯法的算法框架和應(yīng)用技能二、主要教學(xué)內(nèi)容1.回溯法的算法框架2.裝載問題3.批處置作業(yè)調(diào)度4.符號三角形問題5.n后問題6.0—l背包問題7.最大團(tuán)問題8.圖的m著色問題9.旅行售貨員問題10.圓排列問題11.電路板排列問題12.持續(xù)郵資問題13.回溯法的效率分三、課堂討論選題1.0—l背包問題2.圖的m著色問題第六章分支限界法一、學(xué)習(xí)目的要求1．理解分支限界法的大體思想2．掌握典型范例中分支限界法的應(yīng)用技能二、主要教學(xué)內(nèi)容1.分支限界法的大體思想2.單源最短路徑問題3.裝載問題4.布線問題5.0-1背包問題6.最大團(tuán)問題7.旅行售貨員問題8.電路板排列問題9.批處置作業(yè)調(diào)度三、課堂討論選題1.0-1背包問題2.批處置作業(yè)調(diào)度第七章概率算法一、學(xué)習(xí)目的要求1．理解概率算法的大體思想2．掌握典型范例中概率算法的應(yīng)用技能二、主要教學(xué)內(nèi)容1.隨機(jī)數(shù)2.數(shù)值概率算法3.舍伍德算法4.拉斯維加斯算法5.蒙特卡羅算法第八章NP完全性理論一、學(xué)習(xí)目的要求1．了解P類與NP類問題2．了解典型的NP完全問題二、主要教學(xué)內(nèi)容1.計算模型2.P類與NP類問題3.NP完全問題4.一些典型的NP完全問題第九章近似算法一、學(xué)習(xí)目的要求1．掌握近似算法的大體思想2．掌握常常利用近似算法的應(yīng)用二、主要教學(xué)內(nèi)容1.近似算法的性能2.極點覆蓋問題的近似算法3.旅行售貨員問題近似算法4.集合覆蓋問題的近似算法5.子集和問題的近似算法第十章算法優(yōu)化策略一、學(xué)習(xí)目的要求1．掌握算法優(yōu)化策略2．掌握算法優(yōu)化的大體方式二、主要教學(xué)內(nèi)容1.算法優(yōu)化策略的比較與選擇2.動態(tài)計劃加速原理3.問題的算法特征4.優(yōu)化數(shù)據(jù)結(jié)構(gòu)5.優(yōu)化搜索策略【教學(xué)（實驗）內(nèi)容要點】算法設(shè)計與分析實驗是算法設(shè)計與分析課的一個實踐性教學(xué)環(huán)節(jié)。通過實驗使學(xué)生加深對大體算法設(shè)計方式的理解，增強(qiáng)學(xué)生對解決問題的不同算法運行時刻不同的感性熟悉，使學(xué)生在算法設(shè)計方式和編程技術(shù)等方面取得系統(tǒng)的訓(xùn)練，使學(xué)生養(yǎng)成設(shè)計良好算法的適應(yīng)，為此后從事軟件開發(fā)和軟件理論研究打下良好的實驗基礎(chǔ)。一、（實驗1）分治法實驗1.實驗?zāi)康囊髴?yīng)用分治法算法解決實際問題，并編程實現(xiàn)。2.實驗主要內(nèi)容(1)寫出并調(diào)試二分檢索的遞歸程序并調(diào)試通過。(2)寫出并調(diào)試"由底向上"的歸并分類程序，從而取消對?？臻g的需求。3、實驗儀器設(shè)備PC兼容機(jī)二、（實驗2）動態(tài)計劃實驗1.實驗?zāi)康囊蟀褎討B(tài)計劃算法應(yīng)用到求貨郎擔(dān)問題和矩陣乘法問題，并編程實現(xiàn)。2.實驗主要內(nèi)容（1）寫出并調(diào)試用動態(tài)計劃方式求貨郎擔(dān)問題的程序。（2）寫出并調(diào)試用動態(tài)計劃方式求矩陣乘法的程序。3.實驗儀器設(shè)備PC兼容機(jī)?！境煽兛己朔绞健?.成績評定總則全面考核學(xué)生在課程學(xué)習(xí)各個環(huán)節(jié)的理解、掌握和參與情形2.平時成績評定平時成績＝考勤成績＋作業(yè)成績+課堂討論成績3.期末考核評定課程成績＝平時成績(10%)+實驗成績(20%)+期末成績(70%)【教材與參考書目】指定教材：《算法設(shè)計與分析》王曉東編著2003年1月第1版清華大學(xué)出版社參考書目：1.《算法設(shè)計與分析》周培德編著1991年1月第1版機(jī)械工業(yè)出版社2.《算法設(shè)計與分析》曹新譜編著1984年11月第1