《編程拓展課程設(shè)計》-實驗教學(xué)大綱

PAGEPAGE7《編程拓展課程設(shè)計》課程教學(xué)大綱一、課程基本信息課程代碼：16056602課程名稱：編程拓展課程設(shè)計英文名稱：Coursedesignofprogramming課程類別：專業(yè)必修課學(xué)時：32學(xué)分：2適用對象:計算機科學(xué)與技術(shù)專業(yè)考核方式：考查先修課程：C語言程序設(shè)計二、課程簡介中文簡介：算法和編程思維無處不在，遍及計算機科學(xué)和其他鄰域。本課程將算法和編程作為一個設(shè)計過程來介紹，即從計算機應(yīng)用領(lǐng)域提出問題開始，繼而建立對算法和程序設(shè)計技術(shù)的理解,最終形成對這些問題有效的解決方案。理解復(fù)雜算法最好的方法通常是重構(gòu)從初始的簡單想法到最終解決問題的思考過程，包括錯誤的初始想法和行不通的想法。因此，本課程以來自計算機科學(xué)和相關(guān)領(lǐng)域的問題為例來介紹算法和程序設(shè)計的基本技術(shù)。這些技術(shù)包括貪心策略，分治策略，動態(tài)規(guī)劃，隨機算法等。通過該課程，進一步加強對學(xué)生專業(yè)技術(shù)能力的培養(yǎng)，以及樹立專業(yè)報國技術(shù)報國的信念，建立科學(xué)分析問題的態(tài)度和專業(yè)工匠精神，從專業(yè)多角度進一步體會技術(shù)是國家強盛的基礎(chǔ)，提升為國家服務(wù)的理念和態(tài)度。英文簡介：Algorithmicideasandprogrammingarepervasive,andtheirreachisapparentinexamplesbothwithincomputerscienceandbeyond.Thiscourseistoconveythisapproachtoalgorithmsandprogramming,asadesignprocessthatbeginswithproblemsarisingacrossthefullrangeofcomputingapplications,buildsonanunderstandingofalgorithmandprogramdesigntechniques,andresultsinthedevelopmentofefficientsolutionstotheseproblems.Sophisticatedalgorithmsareoftenbestunderstoodbyreconstructingthesequenceofideas—includingfalsestartsanddeadends—thatledfromsimplerinitialapproachestotheeventualsolution.Bydoingthis,thebasicalgorithmandprogramdesigntechniquesareintroducedbydrawingonproblemsfromacrossmanyareasofcomputerscienceandrelatedfields.Thesedesigntechniquesincludesgreedyalgorithms,divideandconquer,dynamicprogramming,andrandomizedalgorithms,etc.三、課程性質(zhì)與教學(xué)目的本課程通過講授一些基本的算法和程序設(shè)計技術(shù)，結(jié)合一些算法問題的編程訓(xùn)練，切實提高學(xué)生的算法和程序設(shè)計能力。要求學(xué)生通過學(xué)習(xí)掌握諸如貪心、分治、動態(tài)規(guī)劃、隨機化等算法和程序設(shè)計技術(shù)，并能運用這些技術(shù)編程求解一些較為復(fù)雜的問題。通過課程學(xué)習(xí)鍛煉學(xué)生的邏輯思維能力和編程實踐能力，培養(yǎng)和提高學(xué)生分析和解決一些復(fù)雜問題的能力。四、教學(xué)內(nèi)容及要求第一章算法分析入門目的與要求掌握算法分析的基本原理教學(xué)內(nèi)容第一節(jié)主要內(nèi)容。算法分析的基本知識最大子序列和問題基本概念和知識點算法分析中遞推關(guān)系的復(fù)雜度分析求解最大子序列和問題的分治策略問題與應(yīng)用（能力要求）思考與實踐課后編程實現(xiàn)最大子序列和問題的求解算法。教學(xué)方法與手段課堂講授，課堂討論，編程實現(xiàn)。在課堂中，通過講授算法分析的基礎(chǔ)概念和知識，傳遞科學(xué)分析問題的方法和思路，利用算法的不同體現(xiàn)多角度的思考問題的科學(xué)發(fā)展觀。第二章算法和程序設(shè)計的基本技術(shù)目的與要求掌握算法和程序設(shè)計的基本技術(shù)掌握一些復(fù)雜問題的算法分析技巧教學(xué)內(nèi)容第一節(jié)主要內(nèi)容活動選擇問題樹上的獨立集問題基本概念和知識點貪心策略的應(yīng)用貪心策略的正確性證明問題與應(yīng)用（能力要求）第二節(jié)主要內(nèi)容主定理（Mastertheorem）最近點對問題基本概念和知識點分治策略的應(yīng)用分治策略的時間復(fù)雜度分析問題與應(yīng)用（能力要求）第三節(jié)主要內(nèi)容整數(shù)的快速乘法問題矩陣的快速乘法問題基本概念和知識點整數(shù)的快速乘法算法矩陣的快速乘法算法問題與應(yīng)用（能力要求）第四節(jié)主要內(nèi)容動態(tài)規(guī)劃的基本原理矩陣乘法順序安排問題基本概念和知識點矩陣乘法順序安排的動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法的時間復(fù)雜度分析問題與應(yīng)用（能力要求）第五節(jié)主要內(nèi)容最優(yōu)二叉查找樹問題最短路徑問題基本概念和知識點最優(yōu)二叉查找樹的動態(tài)規(guī)劃算法最短路徑問題的動態(tài)規(guī)劃算法問題與應(yīng)用（能力要求）第六節(jié)主要內(nèi)容隨機算法的基本原理。跳躍表及其查找時間復(fù)雜度。素數(shù)測試的隨機算法?；靖拍詈椭R點隨機算法的應(yīng)用隨機算法的時間復(fù)雜度分析問題與應(yīng)用（能力要求）第七節(jié)主要內(nèi)容回溯算法的基本原理。收費公路重建問題。博弈樹?；靖拍詈椭R點回溯算法的應(yīng)用回溯算法的時間復(fù)雜度分析問題與應(yīng)用（能力要求）思考與實踐編程實現(xiàn)相關(guān)問題的求解算法。教學(xué)方法與手段課堂講授，課堂討論，編程實現(xiàn)。授課過程中，通過中美貿(mào)易摩擦，引入博弈論在政治經(jīng)濟等各領(lǐng)域的案例分析，引導(dǎo)學(xué)生進一步理解國力的強盛是人民幸福生活的基礎(chǔ)和保證。第三章編程實踐目的與要求編程實現(xiàn)相關(guān)問題的求解教學(xué)內(nèi)容第一節(jié)主要內(nèi)容Josephus問題基本概念和知識點Josephus問題問題與應(yīng)用（能力要求）第二節(jié)主要內(nèi)容八皇后問題基本概念和知識點八皇后問題問題與應(yīng)用（能力要求）第三節(jié)主要內(nèi)容二叉樹中節(jié)點的最小公共祖先問題基本概念和知識點二叉樹中節(jié)點的最小公共祖先問題問題與應(yīng)用（能力要求）第四節(jié)主要內(nèi)容幾個簡單問題的動態(tài)規(guī)劃基本概念和知識點幾個簡單問題的動態(tài)規(guī)劃問題與應(yīng)用（能力要求）第五節(jié)主要內(nèi)容有向圖的強連通分量基本概念和知識點有向圖的強連通分量問題與應(yīng)用（能力要求）第六節(jié)主要內(nèi)容串的模式匹配基本概念和知識點串的模式匹配問題與應(yīng)用（能力要求）第七節(jié)主要內(nèi)容最短路徑的Floyd-Warshall算法基本概念和知識點最短路徑的Floyd-Warshall算法問題與應(yīng)用（能力要求）第八節(jié)主要內(nèi)容總結(jié)各種算法和程序設(shè)計技術(shù)基本概念和知識點各種算法和程序設(shè)計技術(shù)問題與應(yīng)用（能力要求）思考與實踐編程實現(xiàn)課堂中講述的近似算法。教學(xué)方法與手段課堂講授，課堂討論，編程實現(xiàn)。授課過程中，通過二叉樹中公共祖先的知識點，引出各中華民族同根同源的概念，強調(diào)民族自尊心和民族自信心的建立。五、各教學(xué)環(huán)節(jié)學(xué)時分配教學(xué)環(huán)節(jié)教學(xué)時數(shù)課程內(nèi)容講課習(xí)題課討論課實驗其他教學(xué)環(huán)節(jié)小計第一