1、課程名稱：算法分析和設計課程代碼：C201課程學分：2應用領域：計算機應用技術算法分析和設計design and analysis of advanced algorithms教學大綱一、過程的性質(zhì)算法的設計和分析是計算機科學的核心問題之一，是計算機科學與工程各專業(yè)及研究生的重要專業(yè)基礎課程。是研究計算機領域及相關領域中常用的幾種算法設計方法和算法的復雜性分析方法的內(nèi)容。通過講授NP理論的主要概念和一些近似算法，為學生對計算機算法的研究奠定了基礎。學習和掌握這些知識不僅對計算機專業(yè)技術人員是必要的，對使用計算機的其他每個專業(yè)技術人員也是必要的。二、課程教育目的通過本課程的學習，應使學生設計解決

2、計算機應用實際問題的有效算法，并掌握算法設計的一般方法，以便利用現(xiàn)有算法解決實際問題。并讓學生分析算法，估計算法的時空復雜性，對算法進行科學評價。三、基本內(nèi)容和基本要求培訓第一章簡介1、定義算法(了解)2、算法特征3、計算機解決方案問題流程4、算法描述語言5、算法分類第二章算法復雜性分析(需要全部掌握)1、算法復雜性2、算法復雜性度量3、復雜性的漸進形式4、增量分析5，遞歸方程解的漸進序第三章算法設計的基本方法(全部需要掌握)1、貪心法2、分治法3、動態(tài)編程4、回溯方法5、分支極限法第4章圖表和網(wǎng)絡算法(需要所有主)1、基本概念2，樹算法3、道路算法4、流算法第五章計算幾何(全部需要掌握)1、

3、交叉問題2、求夾角3、求凸包判斷點位于幾何圖形內(nèi)部5，Voronoi圖第6章概率算法(需要所有掌握)1、概率算法簡介2、隨機數(shù)3、小數(shù)概率算法4、線性時間選擇算法5、平面點集最近點對概率算法第七章NP完備性理論和近似算法(必須掌握一切)1，確定性圖靈機2、不確定性圖靈機3、p類和NP類4、Cook定理和NP完全問題5、NP完全問題近似解第八章新技術概要(一般理解)四、本課程與其他相關課程的關系和分工第一課：編程、數(shù)據(jù)結構、離散數(shù)學等。五、實用環(huán)節(jié)教學內(nèi)容的準備和要求對于作業(yè)中的幾個典型問題，學生應利用所學的算法設計方法提出相應的算法程序，實現(xiàn)機器，并給出具體算法程序時空復雜性的數(shù)值實驗結果。六

4、、本課程課外練習的要求課外練習是一個練習題，各部分的作業(yè)數(shù)量不低于兩個問題。七、本課程的教學方法和現(xiàn)代教學方法的使用要求教學方法主要利用計算機和投影設備，將重要的算法說明和復雜性分析過程制作成生動直觀的教學課件，提高教學效率和效果。Viii .本課程成績的測試方法和評價標準任務：20%實驗報告： 20%期末考試：60%Ix。教材和參考書教育材料：算法設計與分析指南陸凱成清華大學出版社參考：算法設計與分析周培德機械工業(yè)出版社“算法和數(shù)據(jù)結構”傅慶祥等電子產(chǎn)業(yè)出版社上?？萍嘉墨I出版社，如算法設計與分析朱紅X.課程每章時間分布張內(nèi)容會話總數(shù)講課時間討論、論文、實驗、設計注釋第一章引言22第二章算法復雜性分析44第三章算法設計方法66第四章圖形和網(wǎng)絡算法44第五章計算幾何圖形44第六章概率算法22第七章NP完備性理論與近似算法66第八章新技術摘要22練習題課22總計32302大綱作者：傅曉玲概述審閱者：劉文平責任教授：李也先系主任(教研室):李愛森大學負