算法分析及設計

算法分析及設計算法分析及設計算法分析及設計xxx公司算法分析及設計文件編號：文件日期：修訂次數：第1.0次更改批準審核制定方案設計，管理制度課程名稱：算法分析及設計課程編碼：C201課程學分：2適用學科：計算機應用技術算法分析及設計DesignandAnalysisofadvancedAlgorithms教學大綱一、課程性質算法的設計與分析是計算機科學的核心問題之一，是計算機科學與工程各專業(yè)學生及研究生的一門重要的專業(yè)基礎課。其內容是研究計算機領域及相關領域中的一些常用的算法設計方法及算法的復雜性分析方法。同時，通過講授NP理論的主要概念及一些近似算法，為學生從事計算機算法的研究工作奠定基礎。學習和掌握這些知識不僅對計算機專業(yè)的技術人員，而且對使用計算機的其他各專業(yè)技術人員都是必不可少的。二、課程教學目的通過本課程的學習，應使學生掌握算法設計的常用方法，以便能夠運用這些方法設計解決計算機應用中的實際問題的有效算法，并能夠利用已有算法去解決實際問題。此外還要使學生學會分析算法，估計算法的時空復雜性，從而對算法做出科學的評價。三、教學基本內容及基本要求緒論算法定義（了解）算法特征計算機求解問題過程算法描述語言算法分類算法復雜性分析（要求全部掌握）算法復雜性算法復雜性計量復雜性的漸進形態(tài)漸進分析遞歸方程解的漸進階算法設計的基本方法（要求全部掌握）貪心法分治法動態(tài)規(guī)劃回溯法分支限界法第四章圖和網絡算法（要求全部掌握）基本概念 樹的算法路的算法流的算法第五章計算幾何（要求全部掌握）相交問題求夾角求凸包判斷一點在幾何體內部Voronoi圖第六章概率算法（要求全部掌握）概率算法簡介隨機數素數的概率算法線性時間選擇算法平面點集最近點對概率算法第七章NP完全性理論及近似算法（要求全部掌握）確定性圖靈機非確定性圖靈機P類與NP類Cook定理與NP完全問題NP完全問題近似解法第八章新技術綜述（一般了解）四、本課程與其他相關課程的聯(lián)系與分工 先修課程：程序設計，數據結構，離散數學等。五、實踐環(huán)節(jié)教學內容的安排與要求 對作業(yè)中的一些典型問題，要求學生運用所學的算法設計方法給出相應的算法程序并上機實現，并給出具體算法程序的時空復雜性數值實驗結果。六、本課程課外練習的要求課外練習為習題，每節(jié)的作業(yè)量不少于二道題。七、本課程的教學方法及使用現代化教學手段的要求教學方法以課堂教學為主，借助于計算機和投影設備將重要的算法描述及復雜性分析過程制作成生動、直觀的教學課件，以提高教學效率和效果。八、本課程成績的考查方法及評定標準作業(yè)：20%實驗報告:20%期末考試：60%九、教材及參考書教材：“算法設計與分析導引”盧開澄清華大學出版社參考書：“算法設計與分析”周培德機械工業(yè)出版社“算法與數據結構”傅清祥等電子工業(yè)出版社“算法設計和分析”朱洪等上海科技文獻出版社十、課程各章節(jié)學時分配章節(jié)內容總課時講授課時討論、論文、實驗、設計備注第1章緒論22第2章算法復雜性分析44第3章算法設計方法66第4章圖和網絡算法44第5章計算幾何44第6章概率算法22第7章NP完全性理論及近似算法66第8章新技術綜述22習題課22合計32302大綱撰寫人：付曉玲