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

前言

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

內(nèi)容概要

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

作者簡(jiǎn)介

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


書(shū)籍目錄
前言第1章 算法設(shè)計(jì)與分析概論1.1 算法的定義和特征1.2 算法的描述1.3 算法分析1.4 遞歸方程求解1.4.1 遞歸公式的展開(kāi)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 二叉樹(shù)查找2.2.3 AVL樹(shù)2.3 排序問(wèn)題的分治與遞歸算法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 背包問(wèn)題的貪心算法4.2 求最小生成樹(shù)的Kruskal算法4.3 求最小生成樹(shù)的Prim算法4.4 求單源最短路的Dijkstra算法4.5 哈夫曼編碼4.6 習(xí)題第5章 動(dòng)態(tài)規(guī)劃算法5.1 多段圖問(wèn)題5.2 矩陣連乘積問(wèn)題5.3 0.1背包問(wèn)題5.4 旅行售貨員問(wèn)題5.5 最長(zhǎng)公共子序列問(wèn)題5.6 流水作業(yè)調(diào)度問(wèn)題5.7 資源分配問(wèn)題5.8 動(dòng)態(tài)規(guī)劃小結(jié)5.9 習(xí)題第6章 回溯算法6.1 回溯算法的基本思想6.2 旅行售貨員問(wèn)題6.3 n后問(wèn)題6.4 圖的m著色問(wèn)題6.5 0-1背包問(wèn)題6.6 批處理作業(yè)調(diào)度問(wèn)題6.7 哈密爾頓回路問(wèn)題6.8 子集和數(shù)問(wèn)題6.9 回溯法效率分析6.10 習(xí)題第7章 分支限界算法7.1 基本思想7.2 0-1背包問(wèn)題7.3 旅行售貨員問(wèn)題7.4 任務(wù)分配問(wèn)題7.5 批處理作業(yè)調(diào)度問(wèn)題7.6 重排九宮問(wèn)題7.7 習(xí)題第8章 NP-完全問(wèn)題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ī)問(wèn)題與可計(jì)算性度量8.1.6 計(jì)算復(fù)雜性的度量8.2 P類和NP類問(wèn)題8.2.1 P類問(wèn)題的實(shí)例8.2.2 NP類問(wèn)題的實(shí)例8.3 NP完全問(wèn)題與Cook定理8.3.1 多項(xiàng)式規(guī)約與NP完全問(wèn)題的基本理論8.3.2 Cook定理8.3.3 其他NP完全問(wèn)題8.3.4 CO-NP問(wèn)題與NPI問(wèn)題8.4 NP困難問(wèn)題的近似算法和概率算法8.4.1 近似算法8.4.2 概率算法8.5 習(xí)題參考文獻(xiàn)


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




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





圖書(shū)封面






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



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


 


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