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