算法設計與分析

內(nèi)容概要

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

作者簡介

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

書籍目錄

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

章節(jié)摘錄

版權頁：插圖：

編輯推薦

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

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    算法設計與分析 PDF格式下載

---