C程序設(shè)計教學(xué)大綱

教學(xué)大綱――算法設(shè)計與分析《算法設(shè)計與分析》課程教學(xué)大綱一、課程基本信息課程名稱（中文）算法設(shè)計與分析課程名稱（英文）AlgorithmDesignandAnalysis課程類型專業(yè)選修課學(xué)分4總學(xué)時64適用對象信息與計算科學(xué)專業(yè)三年級考核方式閉卷筆試結(jié)合實踐考核，平時成績占總成績的百分20%、實驗成績占總成績的20%，期末考試成績占總成績的60%先修課程程序設(shè)計語言、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)二、課程簡介《算法設(shè)計與分析》是信息與計算科學(xué)專業(yè)的專業(yè)選修課。算法是計算機科學(xué)的靈魂，《算法設(shè)計與分析》是一門面向設(shè)計，且處于計算機科學(xué)核心地位的課程。本課程的主要內(nèi)容包括：算法概述、遞歸與分治策略、動態(tài)規(guī)劃、貪心算法、回朔法、分枝限界法，隨機化算法等。三、課程目標(biāo)通過本課程中許多常見且有代表性算法的學(xué)習(xí)，使學(xué)生理解和掌握算法設(shè)計的主要方法，培養(yǎng)對算法時間復(fù)雜性進(jìn)行正確分析能力，為獨立的設(shè)計算法和給定算法進(jìn)行復(fù)雜性分析打下良好的基礎(chǔ)。培養(yǎng)學(xué)生具有針對給定問題設(shè)計和實現(xiàn)高效算法的能力。四、教學(xué)內(nèi)容及要求（一）算法概述1，教學(xué)目的與要求（1）了解算法與程序的概念（2）掌握算法復(fù)雜性分析及其有關(guān)的概念（3）了解NP完全問題2，教學(xué)內(nèi)容（1）算法與程序（2）算法復(fù)雜性分析（3）NP完全性理論（二）遞歸與分治策略1，教學(xué)目的與要求（1）理解遞歸的概念（2）了解分治法的基本思想（3）掌握二分搜索技術(shù)（4）掌握Strassen矩陣算法現(xiàn)（5）了解棋盤覆蓋問題的算法（6）理解合并排序和快速排序算法（7）了解線性時間選擇算法2，教學(xué)內(nèi)容（1）遞歸的概念（2）分治法的基本思想（3）二分搜索技術(shù)（4）大整數(shù)的乘法（5）Strassen矩陣乘法（6）棋盤覆蓋（7）合并排序（8）快速排序（9）線性時間選擇（10）最接近點對問題（11）循環(huán)日程表（三）動態(tài)規(guī)劃1，教學(xué)目的與要求（1）掌握動態(tài)規(guī)劃算法的概念、步驟和基本要素（2）掌握最長公共子序列算法設(shè)計和分析（3）掌握矩陣的連乘算法設(shè)計和分析（4）了解凸多邊形最優(yōu)三角剖分算法（5）了解多邊形游戲問題的算法分析（6）了解圖像壓縮算法分析（7）掌握電路布線問題的算法分析（8）掌握流水作業(yè)調(diào)度（9）了解背包問題的算法分析（10）了解最優(yōu)二叉搜索樹的算法分析2，教學(xué)內(nèi)容（1）矩陣的連乘問題（2）動態(tài)規(guī)劃算法的基本要素（3）最長公共子序列（4）最大子段和（5）凸多邊形最優(yōu)三角剖分（6）多邊形游戲（7）圖像壓縮（8）電路布線（9）流水作業(yè)調(diào)度（10）0－1背包問題（11）最優(yōu)二叉搜索樹（四）貪心算法1，教學(xué)目的與要求（1）掌握貪心算法的概念和基本要素（2）了解貪心算法的理論基礎(chǔ)（3）了解最優(yōu)裝載問題的算法分析（4）了解哈夫曼編碼的算法分析（5）了解單源最短路徑的Dijkstra算法的設(shè)計與分析（6）了解最小生成樹的Prim和Kruskal算法的設(shè)計與分析2，教學(xué)內(nèi)容《算法設(shè)計與分析》實驗教學(xué)大綱基本信息課程名稱（中文）算法設(shè)計與分析課程名稱（英文）AlgorithmDesignandAnalysis課程類型專業(yè)選修課學(xué)分4實驗學(xué)時32適用專業(yè)信息與計算科學(xué)專業(yè)三年級先修課程程序設(shè)計語言、離散數(shù)學(xué)、數(shù)據(jù)結(jié)構(gòu)二、實驗課程簡介《算法設(shè)計與分析》實驗課程是與《算法設(shè)計與分析》配套的課程。實驗內(nèi)容主要是使用C＋＋語言實驗與理論課程相關(guān)的算法，主要包括：基本算法、遞歸、分治策略、動態(tài)規(guī)劃、貪心算法、回溯法、分支界限法的實現(xiàn)。三、實驗?zāi)康摹端惴ㄔO(shè)計與分析》旨在教會學(xué)生處理各種問題的方法，而通過實驗，使學(xué)生能夠把所學(xué)的方法用于具體的問題，并對所用算法進(jìn)行比較分析，從而提高學(xué)生分析問題、解決問題的能力。只有通過實驗，學(xué)生才能判定自己所擬算法是否正確，是否算得上一個較優(yōu)算法。通過該課程的實驗，使學(xué)生對課堂中所講述的內(nèi)容有一個直觀的認(rèn)識，更好地掌握所學(xué)的知識。同時培養(yǎng)學(xué)生的實際動手能力，加強學(xué)生創(chuàng)新思維能力的培養(yǎng)。四、實驗內(nèi)容與要求（一）基本算法1．實驗?zāi)康呐c要求通過實驗使學(xué)生掌握使用C＋＋語言實現(xiàn)排序算法的方法，了解一些常見問題的算法設(shè)計與實驗方法。2．實驗內(nèi)容（1）插入排序（2）合并排序（3）統(tǒng)計數(shù)字問題（4）字典序問題（二）遞歸與分治策略1．實驗?zāi)康呐c要求通過實驗使學(xué)生掌握使用遞歸和分治法實現(xiàn)算法的方法。2．實驗內(nèi)容（1）遞歸的使用（2）分治法的實現(xiàn)（3）眾數(shù)問題（4）有重復(fù)元素的排列問題（三）動態(tài)規(guī)劃1．實驗?zāi)康呐c要求通過實驗使學(xué)生掌握使用動態(tài)規(guī)劃算法的基本設(shè)計思路，并用其解決實際問題。2．實驗內(nèi)容（1）矩陣連乘問題（2）最大子段和問題（3）最長公共子序列（4）0－1背包問題（5）獨立任務(wù)最優(yōu)調(diào)度問題（6）數(shù)字三角形問題（四）貪心算法1．實驗?zāi)康呐c要求掌握貪心算法的基本設(shè)計思路，并用其解決實際問題。2．實驗內(nèi)容（1）0－1背包問題（2）單源最短路徑問題（3）會場安排問題（4）最優(yōu)合并問題（五）回溯算法1．實驗?zāi)康呐c要求掌握回溯法的算法框架和算法的基本思想。2．實驗內(nèi)容（1）8皇后問題（2）批處理作業(yè)調(diào)度（3）0－1背包問題（4）子集和問題（六）分支界限法1．實驗?zāi)康呐c要求通過實現(xiàn)掌握分支界限法的基本思想，并能用其解決問題。2．實驗內(nèi)容（1）0－1背包問題（2）最小權(quán)頂點覆蓋問題（七）隨機化算法1．實驗?zāi)康呐c要求了解隨機化算法的基本思想。2．實驗內(nèi)容模平方根問題。五、主要儀器設(shè)備計算機六、實驗學(xué)時分配表序號實驗項目名稱學(xué)時實驗內(nèi)容實驗性質(zhì)每組人數(shù)必/選做演示驗證設(shè)計綜合1基本算法4221必做2遞歸與分治策略8621必做3動態(tài)規(guī)劃6421必做4貪心算法441必做5回溯法441必做6分支界限法221必做7隨機化算法441選做七、考核方法上機考試采用開卷考試方式。八、教材及參考書建議教材：《計算機算法設(shè)計與分析》（第四版）電子工業(yè)出版社2012年7月出版王曉東著《計算機算法設(shè)計與分析習(xí)題解答》（第二版）電子工業(yè)出版社2012年6月出版王