算法設(shè)計方法

前言

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

內(nèi)容概要

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

作者簡介

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


書籍目錄
前言第1章 算法設(shè)計與分析概論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 非負整數(shù)矩陣乘法的凝聚算法3.2.2 矩陣乘法的凝聚算法的改進3.2.3 布爾矩陣乘法的凝聚算法3.3 非負整數(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 圖靈機——可計算性和計算復(fù)雜性的度量標(biāo)準(zhǔn)8.1.1 確定的圖靈機8.1.2 圖靈機用于計算整函數(shù)8.1.3 多帶圖靈機8.1.4 不確定的圖靈機8.1.5 圖靈機的停機問題與可計算性度量8.1.6 計算復(fù)雜性的度量8.2 P類和NP類問題8.2.1 P類問題的實例8.2.2 NP類問題的實例8.3 NP完全問題與Cook定理8.3.1 多項式規(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í)題參考文獻


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




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





圖書封面






評論、評分、閱讀與下載



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


 


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