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

內(nèi)容概要

　　本教材為計(jì)算機(jī)科學(xué)技術(shù)專業(yè)核心課程“算法設(shè)計(jì)與分析”教材.全書以算法設(shè)計(jì)技術(shù)和分析方法為主線來組織各知識(shí)單元，主要內(nèi)容包括基礎(chǔ)知識(shí)、分治策略、動(dòng)態(tài)規(guī)劃、貪心法、回溯與分支限界、算法分析與問題的計(jì)算復(fù)雜度、NP完全性、近似算法、隨機(jī)算法、處理難解問題的策略等。書中突出對(duì)問題本身的分析和求解方法的闡述，從問題建模、算法設(shè)計(jì)與分析、改進(jìn)措施等方面給出適當(dāng)?shù)慕ㄗh，同時(shí)也簡要介紹了計(jì)算復(fù)雜性理論的核心內(nèi)容和處理難解問題的一些新技術(shù)。
　　本書有配套的學(xué)習(xí)指導(dǎo)與習(xí)題解析用書以及PPT電子教案。
　　本書可作為大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)、軟件工程、信息安全、信息與計(jì)算機(jī)科學(xué)等專業(yè)本科生和研究生教學(xué)用書，也可以作為從事實(shí)際問題求解的算法設(shè)計(jì)與分析工作的參考書。

作者簡介

屈婉玲，北京大學(xué)信息科學(xué)技術(shù)學(xué)院教授，博士生導(dǎo)師。長期從事離散數(shù)學(xué)、算法分析與計(jì)算復(fù)雜性等方向的教學(xué)和研究工作。參與完成多項(xiàng)國家研究課題，撰寫多部教材、教學(xué)參考書與譯著，其中包括國家級(jí)規(guī)劃教材、北京市精品教材、教育部高等教育精品教材等。曾獲得北京市教學(xué)成果獎(jiǎng)一等獎(jiǎng)，被評(píng)為北京大學(xué)十佳教師和北京市優(yōu)秀教師，系國家精品課“離散數(shù)學(xué)”課程主持人，“算法設(shè)計(jì)與分析”課程主持人。劉田博士，北京大學(xué)信息科學(xué)技術(shù)學(xué)院副教授，中國電子學(xué)會(huì)電路與系統(tǒng)分會(huì)圖論與系統(tǒng)優(yōu)化專業(yè)委員會(huì)秘書長，中國電子學(xué)會(huì)和中國計(jì)算機(jī)學(xué)會(huì)高級(jí)會(huì)員。目前主要從事算法分析和計(jì)算復(fù)雜度方面的研究和教學(xué)工作。翻譯多部國外著名離散數(shù)學(xué)和計(jì)算理論教材，系國家精品課“離散數(shù)學(xué)”課程主講教師，“算法設(shè)計(jì)與分析”課程主講教師。張立昂，北京大學(xué)信息科學(xué)技術(shù)學(xué)院教授，博士生導(dǎo)師。一直從事數(shù)學(xué)和理論計(jì)算機(jī)科學(xué)的教學(xué)與研究工作，主要研究方向是計(jì)算復(fù)雜性理論和算法設(shè)計(jì)與分析。撰寫多部教材、教學(xué)參考書與譯著，其中包括國家級(jí)規(guī)劃教材、北京市精品教材、教育部高等教育精品教材等。曾獲得北京市教學(xué)成果獎(jiǎng)一等獎(jiǎng)和教育部科技進(jìn)步二等獎(jiǎng)。王捍貧博士，北京大學(xué)信息科學(xué)技術(shù)學(xué)院教授，博士生導(dǎo)師，軟件研究所副所長，人工智能學(xué)會(huì)離散數(shù)學(xué)專委會(huì)副主任。長期從事離散數(shù)學(xué)、形式化方法及算法設(shè)計(jì)與分析的教學(xué)和研究工作。主持完成多項(xiàng)國家研究課題，撰寫和翻譯多部離散數(shù)學(xué)和計(jì)算理論教材，曾獲得北京市教學(xué)成果獎(jiǎng)一等獎(jiǎng)，系國家精品課“離散數(shù)學(xué)”課程主講教師，“算法設(shè)計(jì)與分析”課程主講教師。

書籍目錄

第1章　基礎(chǔ)知識(shí)
　1.1　有關(guān)算法的基本概念
　1.2　算法的偽碼描述
　1.3　算法的數(shù)學(xué)基礎(chǔ)
　　1.3.1　函數(shù)的漸近的界
　　1.3.2　求和的方法
　　1.3.3　遞推方程求解方法
　習(xí)題1
第2章　分治策略
　2.1　分治策略的基本思想
　　2.1.1　兩個(gè)熟悉的例子
　　2.1.2　分治算法的一般性描述
　2.2　分治算法的分析技術(shù)
　2.3　改進(jìn)分治算法的途徑
　　2.3.1　通過代數(shù)變換減少子問題個(gè)數(shù)
　　2.3.2　利用預(yù)處理減少遞歸內(nèi)部的計(jì)算量
　2.4　典型實(shí)例
　　2.4.1　快速排序算法
　　2.4.2　選擇問題
　　2.4.3　n -1次多項(xiàng)式在全體2 n 次方根上的求值
　習(xí)題2
第3章　動(dòng)態(tài)規(guī)劃
　3.1　動(dòng)態(tài)規(guī)劃的設(shè)計(jì)思想
　　3.1.1　多起點(diǎn)、多終點(diǎn)的最短路徑問題
　　3.1.2　使用動(dòng)態(tài)規(guī)劃技術(shù)的必要條件
　3.2　動(dòng)態(tài)規(guī)劃算法的設(shè)計(jì)要素
　　3.2.1　子問題的劃分和遞推方程
　　3.2.2　動(dòng)態(tài)規(guī)劃算法的遞歸實(shí)現(xiàn)
　　3.2.3　動(dòng)態(tài)規(guī)劃算法的迭代實(shí)現(xiàn)
　　3.2.4　一個(gè)簡單實(shí)例的計(jì)算過程
　3.3　動(dòng)態(tài)規(guī)劃算法的典型應(yīng)用
　　3.3.1　投資問題
　　3.3.2　背包問題
　　3.3.3　最長公共子序列LCS
　　3.3.4　圖像壓縮
　　3.3.5　最大子段和
　　3.3.6　最優(yōu)二分檢索樹
　　3.3.7　生物信息學(xué)中的動(dòng)態(tài)規(guī)劃算法
　習(xí)題3
第4章　貪心法
　4.1　貪心法的設(shè)計(jì)思想
　4.2　關(guān)于貪心法的正確性證明
　4.3　對(duì)貪心法得不到最優(yōu)解情況的處理
　4.4　貪心法的典型應(yīng)用
　　4.4.1　最優(yōu)前綴碼
　　4.4.2　最小生成樹
　　4.4.3　單源最短路徑
　習(xí)題4
第5章　回溯與分支限界
第6章　算法分析與問題的計(jì)算復(fù)雜度
第7章　NP完全性
第8章　近似算法
第9章　隨機(jī)算法
第10章　處理難解問題的策略
參考文獻(xiàn)

章節(jié)摘錄

版權(quán)頁：插圖：

編輯推薦

《算法設(shè)計(jì)與分析》以算法設(shè)計(jì)技術(shù)為主線組織素材，以偽碼描述算法，深入分析了各種設(shè)計(jì)技術(shù)的適用范圍、設(shè)計(jì)步驟、算法正確性證明與時(shí)間復(fù)雜度估計(jì)方法，以及改進(jìn)算法的途徑、局限性等，為實(shí)際問題的建模與算法設(shè)計(jì)在理論上提供清晰的整體思路。從對(duì)具體算法的設(shè)計(jì)與分析，自然過渡到對(duì)問題難度的分析和界定，系統(tǒng)地介紹了一些關(guān)于問題復(fù)雜度的分析方法。力求用清晰易懂的語言介紹NP完全性理論的核心內(nèi)容和難解問題的處理策略，希望為求解實(shí)際中的復(fù)雜問題提供幫助。除了傳統(tǒng)的算法外，《算法設(shè)計(jì)與分析》還介紹了隨機(jī)算法、模擬退火算法、基于統(tǒng)計(jì)物理的消息傳遞算法、量子算法等，給有興趣的讀者提供進(jìn)一步學(xué)習(xí)和研究的入門知識(shí)?！端惴ㄔO(shè)計(jì)與分析》的主要素材來自多年的教學(xué)積淀，也有一些研究的心得。既注意理論上的嚴(yán)謹(jǐn)性，又精選了大量實(shí)例，并配有難度適當(dāng)?shù)木毩?xí)，適合教學(xué)使用。根據(jù)教育部“高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)規(guī)范”組織編寫。與美國ACM和lEEE CS Computing Curricula最新進(jìn)展同步。

圖書封面

圖書標(biāo)簽Tags

無

評(píng)論、評(píng)分、閱讀與下載

---

    算法設(shè)計(jì)與分析 PDF格式下載

---