算法分析及設(shè)計(jì)

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

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

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

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