算法分析及設(shè)計

1、課程名稱：算法分析及設(shè)計課程編碼：C201課程學分：2適用學科：計算機應用技術(shù)算法分析及設(shè)計Design and Analysis of advancedAlgorithms教學大綱一、課程性質(zhì)算法的設(shè)計與分析是計算機科學的核心問題之一，是計算機科學與工程各專業(yè)學生及研究生的一門重要的專業(yè)基礎(chǔ)課。其內(nèi)容是研究計算機領(lǐng)域及相關(guān)領(lǐng)域中的一些常用的算法設(shè)計方法及算法的復雜性分析方法。同時，通過講授NP 理論的主要概念及一些近似算法，為學生從事計算機算法的研究工作奠定基礎(chǔ)。學習和掌握這些知識不僅對計算機專業(yè)的技術(shù)人員，而且對使用計算機的其他各專業(yè)技術(shù)人員都是必不可少的。二、課程教學目的通過本課程的學習

2、，應使學生掌握算法設(shè)計的常用方法，以便能夠運用這些方法設(shè)計解決計算機應用中的實際問題的有效算法，并能夠利用已有算法去解決實際問題。此外還要使學生學會分析算法，估計算法的時空復雜性，從而對算法做出科學的評價。三、教學基本內(nèi)容及基本要求第一章 緒論1、 、 算法定義（了解）2、 算法特征3、 計算機求解問題過程4、 算法描述語言5、 算法分類第二章算法復雜性分析（要求全部掌握）1、 、 算法復雜性2、 算法復雜性計量3、 復雜性的漸進形態(tài)4、 漸進分析5、 遞歸方程解的漸進階第三章算法設(shè)計的基本方法（要求全部掌握）1 、 貪心法2 、 分治法3 、 動態(tài)規(guī)劃4 、 回溯法5 、 分支限界法第四章圖

3、和網(wǎng)絡算法（要求全部掌握）1 、 基本概念2 、 樹的算法3 、 路的算法4 、 流的算法第五章計算幾何（要求全部掌握）1 相交問題2 求夾角3 求凸包4 判斷一點在幾何體內(nèi)部5 Voronoi 圖第六章 概率算法（要求全部掌握）1 概率算法簡介2 隨機數(shù)3 素數(shù)的概率算法4 線性時間選擇算法5 平面點集最近點對概率算法第七章NP完全性理論及近似算法（要求全部掌握）1 確定性圖靈機2 非確定性圖靈機3 P 類與 NP 類4 Cook 定理與 NP 完全問題5 NP 完全問題近似解法第八章 新技術(shù)綜述（一般了解）四本課程與其他相關(guān)課程的聯(lián)系與分工先修課程：程序設(shè)計，數(shù)據(jù)結(jié)構(gòu)，離散數(shù)學等。五實踐環(huán)

4、節(jié)教學內(nèi)容的安排與要求對作業(yè)中的一些典型問題，要求學生運用所學的算法設(shè)計方法給出相應的算法程序并上機實現(xiàn)，并給出具體算法程序的時空復雜性數(shù)值實驗結(jié)果。六、本課程課外練習的要求課外練習為習題，每節(jié)的作業(yè)量不少于二道題。七、本課程的教學方法及使用現(xiàn)代化教學手段的要求教學方法以課堂教學為主，借助于計算機和投影設(shè)備將重要的算法描述及復雜性分析過程制作成生動、直觀的教學課件，以提高教學效率和效果。八、本課程成績的考查方法及評定標準作業(yè)：20%實驗報告：20%期末考試：60%九、教材及參考書教 材：”算法設(shè)計與分析導引” 盧開澄 清華大學出版社參考書：“算法設(shè)計與分析”周培德機械工業(yè)出版社“算法與數(shù)據(jù)結(jié)構(gòu)”傅清祥等電子工業(yè)出版社“算法設(shè)計和分析”朱洪等上?？萍嘉墨I出版社十、課程各章節(jié)學時分配早下內(nèi)容總課時講授課 時討論、論文、 實驗、設(shè)計備注第1章緒論22第2章算法復雜性分析44第3章算法設(shè)計方法66弟4早圖和網(wǎng)絡算法44弟5早計算幾何44弟6早概率算法22弟7早NPI全性理論及近似66算法第8章新技木綜述22習題課22合