算法分析及設(shè)計

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