算法分析及設(shè)計

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

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

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

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