算法設(shè)計(jì)方法

前言

　　算法是計(jì)算機(jī)科學(xué)的核心內(nèi)容之一，也是應(yīng)用電子計(jì)算機(jī)求解實(shí)際問題的基礎(chǔ)。對復(fù)雜的實(shí)際應(yīng)用問題的求解，大多都?xì)w結(jié)為算法的設(shè)計(jì)，然后把求解算法轉(zhuǎn)化為計(jì)算機(jī)程序。同算法設(shè)計(jì)密切相關(guān)的內(nèi)容是算法分析，即算法的正確性證明和算法的時(shí)空復(fù)雜性分析。因此，國內(nèi)外各高校都把算法設(shè)計(jì)與分析作為計(jì)算機(jī)專業(yè)的重要課程。　　自20世紀(jì)七八十年代以來，國內(nèi)一些高校先后編寫和出版過多種算法設(shè)計(jì)與分析教材，同時(shí)也引進(jìn)或翻譯出版了一些國外的經(jīng)典教材。就國內(nèi)編寫出版的教材而言，20世紀(jì)的教材大多從問題入手進(jìn)行內(nèi)容組織和處理，即在同一章中敘述一類問題的各種不同的算法設(shè)計(jì)方法。2l世紀(jì)的教材則大多從方法入手來進(jìn)行內(nèi)容的組織和處理，即在一章中介紹一種典型的算法設(shè)計(jì)方法，而把適用于該種算法設(shè)計(jì)方法的各類問題作為實(shí)例在同一章中分節(jié)闡述。從問題入手轉(zhuǎn)化為從方法入手編寫教材，是學(xué)科發(fā)展(求解問題類大量增加)的必然，也是知識分類和內(nèi)容組織的一種進(jìn)步。不過，有些教材雖然從方法入手分章編寫，但敘述重點(diǎn)還是放在對各類問題的求解算法的詳細(xì)描述上，而對算法的設(shè)計(jì)思想的闡述仍不夠透徹、突出。對各類問題的求解算法的詳細(xì)描述雖然便于學(xué)生把書本上給出的算法轉(zhuǎn)化為計(jì)算機(jī)程序，但如果不能理解和掌握各種典型算法的基本思想，就難以對適用于同類算法設(shè)計(jì)方法的(書本上未討論過的)問題進(jìn)行算法設(shè)計(jì)。　　我們認(rèn)為，算法設(shè)計(jì)與分析這門課程的主要教學(xué)目標(biāo)是讓學(xué)生領(lǐng)會和掌握各種典型算法的基本設(shè)計(jì)思路。因此一方面，我們采用從方法入手來對課程內(nèi)容進(jìn)行組織和處理；另一方面，在講述每一種典型的算法設(shè)計(jì)方法時(shí)，首先對這種典型算法的基本思路進(jìn)行充分的闡述，然后把適用于該典型算法的各類問題作為實(shí)例分節(jié)闡述，對每一類實(shí)際問題都要把典型算法設(shè)計(jì)思路在該類問題求解中的具體體現(xiàn)作為重點(diǎn)內(nèi)容，并對所設(shè)計(jì)出的算法給出時(shí)間復(fù)雜性分析。本教材共分為8章。第l章是算法設(shè)計(jì)與分析概論，介紹了算法描述和算法分析的基本方法。第2-7章是本書的主體部分，依次討論了分治與遞歸算法、散列與凝聚算法、貪心算法、動態(tài)規(guī)劃算法、回溯算法和分支限界算法等典型的算法設(shè)計(jì)方法。第8章對NP完全問題進(jìn)行了討論，并介紹了求解NP困難問題常用的近似算法和概率算法。全書的講授約需72學(xué)時(shí)。如果在各種典型算法中挑選一些問題類讓學(xué)生自學(xué)，也可以用60左右學(xué)時(shí)完成本書的教學(xué)。

內(nèi)容概要

　　本書共分為8章。第1章介紹了算法的基本概念以及算法描述和算法分析的基本知識。第2章至第7章分別論述了分治與遞歸算法、散列與凝聚算法、貪心算法、動態(tài)規(guī)劃算法、回溯算法和分支限界算法。在每一章的開頭，都先對相應(yīng)的典型算法的基本思路進(jìn)行詳細(xì)、清晰的闡述，然后通過多種實(shí)際問題的求解，對該典型算法的設(shè)計(jì)方法作進(jìn)一步的剖析。第8章對NP完全問題的基本理論進(jìn)行討論，并介紹了求解NP困難問題的近似算法和概率算法。

作者簡介

　　吳哲輝，男，教授，博士生導(dǎo)師，中共黨員。1941年生于廣東省連縣（現(xiàn)連州市）。1965年畢業(yè)于中山大學(xué)數(shù)學(xué)專業(yè)，1981年12月到1983年12月在美國芝加哥伊利諾大學(xué)作訪問學(xué)者。現(xiàn)任山東科技大學(xué)信息科學(xué)與工程學(xué)院教授、博士生導(dǎo)師，中國科學(xué)院計(jì)算技術(shù)研究所兼職博士生導(dǎo)師，中國計(jì)算機(jī)學(xué)會理事，中國計(jì)算機(jī)學(xué)會petri網(wǎng)專業(yè)委員會主任。　　主要研究領(lǐng)域有：petri網(wǎng)理論與并行分時(shí)系統(tǒng)、算法設(shè)計(jì)與分析、形式語言與自動機(jī)理論、密碼學(xué)等。先后主持承擔(dān)國家自然科學(xué)基金項(xiàng)目6項(xiàng)（從1987年到2004年，每3年1項(xiàng)）、山東省自然科學(xué)基金項(xiàng)目2項(xiàng)、煤炭科學(xué)基金項(xiàng)目2項(xiàng)；在《中國科學(xué)》、《科學(xué)通報(bào)》、《計(jì)算機(jī)學(xué)報(bào)》、《軟件學(xué)報(bào)》等國內(nèi)核心刊物，以及高校學(xué)報(bào)、國外刊物和國際學(xué)術(shù)會議發(fā)表學(xué)術(shù)論文90多篇，出版編、譯著3部；獲得過全國煤炭系統(tǒng)出國留學(xué)人員科研成果一等獎1項(xiàng)（獨(dú)立）、國家教委科技進(jìn)步三等獎1項(xiàng)（首位）、山東省科技進(jìn)步二等獎1項(xiàng)（1項(xiàng)首位，1項(xiàng)第二位），山東省優(yōu)秀教學(xué)成果一等獎1項(xiàng)（首位）、二等獎2項(xiàng)（均首位）?！　?989年被評為全國優(yōu)秀教師；1991年被評為全國有突出貢獻(xiàn)的回國留學(xué)人員，并獲得國務(wù)院頒發(fā)的政府特殊津貼；1992年被評為國家有突出貢獻(xiàn)的中青年專家；1993年和1994年兩度被評為山東省專業(yè)技術(shù)拔尖人才；1995年被評為山東省十大優(yōu)秀教師；1998年被評為全國教育系統(tǒng)勞動模范，并被授予全國模范教師稱號和獎?wù)隆?/pre>


書籍目錄
前言第1章 算法設(shè)計(jì)與分析概論1.1 算法的定義和特征1.2 算法的描述1.3 算法分析1.4 遞歸方程求解1.4.1 遞歸公式的展開1.4.2 常系數(shù)線性齊次遞歸方程的特征方程求解方法1.4.3 常系數(shù)線性非齊次遞歸方程求解1.5 生成函數(shù)1.6 習(xí)題第2章 分治與遞歸算法2.1 分治與遞歸算法的基本思路2.2 查找中的分治與遞歸算法2.2.1 二分查找算法2.2.2 二叉樹查找2.2.3 AVL樹2.3 排序問題的分治與遞歸算法2.3.1 合并排序2.3.2 快速排序2.4 矩陣乘法的strassen算法2.5 快速傅里葉變換2.5.1 離散傅里葉變換2.5.2 快速傅里葉變換算法2.6 減治與遞歸2.7 變治與遞歸2.8 習(xí)題第3章 散列與凝聚算法3.1 散列算法3.1.1 散列查找算法3.1.2 桶排序算法3.2 矩陣乘法的凝聚算法3.2.1 非負(fù)整數(shù)矩陣乘法的凝聚算法3.2.2 矩陣乘法的凝聚算法的改進(jìn)3.2.3 布爾矩陣乘法的凝聚算法3.3 非負(fù)整數(shù)向量卷積的凝聚算法3.4 習(xí)題第4章 貪心算法4.1 背包問題的貪心算法4.2 求最小生成樹的Kruskal算法4.3 求最小生成樹的Prim算法4.4 求單源最短路的Dijkstra算法4.5 哈夫曼編碼4.6 習(xí)題第5章 動態(tài)規(guī)劃算法5.1 多段圖問題5.2 矩陣連乘積問題5.3 0.1背包問題5.4 旅行售貨員問題5.5 最長公共子序列問題5.6 流水作業(yè)調(diào)度問題5.7 資源分配問題5.8 動態(tài)規(guī)劃小結(jié)5.9 習(xí)題第6章 回溯算法6.1 回溯算法的基本思想6.2 旅行售貨員問題6.3 n后問題6.4 圖的m著色問題6.5 0-1背包問題6.6 批處理作業(yè)調(diào)度問題6.7 哈密爾頓回路問題6.8 子集和數(shù)問題6.9 回溯法效率分析6.10 習(xí)題第7章 分支限界算法7.1 基本思想7.2 0-1背包問題7.3 旅行售貨員問題7.4 任務(wù)分配問題7.5 批處理作業(yè)調(diào)度問題7.6 重排九宮問題7.7 習(xí)題第8章 NP-完全問題8.1 圖靈機(jī)——可計(jì)算性和計(jì)算復(fù)雜性的度量標(biāo)準(zhǔn)8.1.1 確定的圖靈機(jī)8.1.2 圖靈機(jī)用于計(jì)算整函數(shù)8.1.3 多帶圖靈機(jī)8.1.4 不確定的圖靈機(jī)8.1.5 圖靈機(jī)的停機(jī)問題與可計(jì)算性度量8.1.6 計(jì)算復(fù)雜性的度量8.2 P類和NP類問題8.2.1 P類問題的實(shí)例8.2.2 NP類問題的實(shí)例8.3 NP完全問題與Cook定理8.3.1 多項(xiàng)式規(guī)約與NP完全問題的基本理論8.3.2 Cook定理8.3.3 其他NP完全問題8.3.4 CO-NP問題與NPI問題8.4 NP困難問題的近似算法和概率算法8.4.1 近似算法8.4.2 概率算法8.5 習(xí)題參考文獻(xiàn)


章節(jié)摘錄
　　第1章 算法設(shè)計(jì)與分析概論　　1.1 算法的定義和特征　　通常的算法定義是：一個(gè)算法是求解某一類特定問題的一組有窮規(guī)則的集合。　　首先，一個(gè)算法是一組規(guī)則，通常稱之為算法步驟，這組規(guī)則是有窮的，即能用有限的形式表示出來。其次，一個(gè)算法是針對一類問題而設(shè)計(jì)的。如果給出了求解某類問題的一個(gè)算法，那么對這類問題的任意一組（一個(gè)）初始數(shù)據(jù)，這個(gè)算法都有效的，也就是說，根據(jù)算法給出的求解步驟，都能求出這組初始數(shù)據(jù)所對應(yīng)的計(jì)算結(jié)果。




編輯推薦
　　本書可作為計(jì)算機(jī)和相關(guān)專業(yè)的本科課程教材，也可作為科技人員的參考書。





圖書封面






評論、評分、閱讀與下載



還沒讀過(52)
勉強(qiáng)可看(377)
一般般(644)
內(nèi)容豐富(2671)
強(qiáng)力推薦(219)


 


    算法設(shè)計(jì)方法 PDF格式下載