計(jì)算機(jī)算法

前言

計(jì)算機(jī)算法是計(jì)算機(jī)學(xué)科的核心課程，熟練掌握這門課程后可以很好地解決在計(jì)算機(jī)研究中遇到的疑難問題，該課程的主要目的是培養(yǎng)讀者分析和設(shè)計(jì)算法的能力，從而為編寫高效的程序和開發(fā)優(yōu)秀軟件奠定基礎(chǔ)。本書主要介紹五種通用的算法設(shè)計(jì)技術(shù)，并且分析了各算法的基本原理和解題技巧。為了方便讀者的理解，書中算法給出程序?qū)崿F(xiàn)的方法和描述，讀者可以用自己擅長的語言對這些算法進(jìn)行上機(jī)實(shí)踐以加深自己對這些算法的理解。全書共分16章，第1章介紹了算法設(shè)計(jì)和分析的基本概念，詳細(xì)地對在一個(gè)表中搜索給定值和矩陣乘法兩個(gè)算法進(jìn)行算法分析，簡單地介紹了算法的5種通用算法設(shè)計(jì)技術(shù)遞歸方程解的展開式；第2章介紹了幾種常用的排序算法，從內(nèi)部排序和外部排序兩方面進(jìn)行分析；第3章討論了幾種查找樹的問題，包括二分查找樹、2-3-4樹、紅黑樹和B樹；第4章討論了圖的算法，講述了最短路徑和最小生成樹的問題；第5章介紹了串匹配問題，在該章中介紹了幾種串匹配問題，如BM算法、KMP算法等；第6章介紹了五種算法設(shè)計(jì)技術(shù)之一的分治算法，解決二分搜索問題、最大最小元問題、大整數(shù)乘法問題、矩陣乘法問題；第7章介紹算法設(shè)計(jì)技術(shù)之二的貪心算法，解決背包問題、帶時(shí)限的作業(yè)排序問題、單源最短路徑問題、最小生成樹問題、Dilkstra最短路徑的優(yōu)化算法；第8章介紹了算法設(shè)計(jì)技術(shù)之三的回溯法，解決n皇后問題、圖的著色問題、0-1背包問題、哈密頓回路問題、子集和數(shù)問題；第9章介紹了算法設(shè)計(jì)技術(shù)之四的動(dòng)態(tài)規(guī)劃法應(yīng)用在最長公共子序列問題、矩陣連乘問題等；第10章從0-1背包問題入手用分支限界法進(jìn)行講解；第11章簡單地介紹了幾種概率算法；第12章主要介紹了幾何問題的實(shí)例；第13章介紹計(jì)算機(jī)算法的一個(gè)理論問題——NP問題，分析幾個(gè)NP完全問題；第14章講解了密碼學(xué)算法，從背包公鑰密碼、RSA算法、數(shù)字簽名等，對密碼學(xué)作了簡單的介紹；第15章介紹了近似算法；第16章重點(diǎn)介紹了一些數(shù)值問題的并行算法。在每章的結(jié)尾都有習(xí)題，以啟發(fā)學(xué)生運(yùn)用學(xué)到的知識(shí)解決實(shí)際問題。從整體上看，本書具有內(nèi)容全面、取材得當(dāng)、實(shí)用和指導(dǎo)性強(qiáng)等特點(diǎn)，是作者多年來計(jì)算機(jī)算法課程教學(xué)的經(jīng)驗(yàn)總結(jié)，是在授課講義基礎(chǔ)上，參考國內(nèi)外有關(guān)材料編寫而成。希望所有讀者能從本書中體會(huì)到計(jì)算機(jī)算法的精髓所在，能對今后的工作和學(xué)習(xí)有所幫助。在教學(xué)內(nèi)容的選擇上也可以根據(jù)本校教學(xué)的實(shí)際情況節(jié)選部分內(nèi)容。為了方便教師的教學(xué)，本書還配備有全套的教學(xué)幻燈片，可供教師在教學(xué)中選用。本書可作為高等院校的教科書或參考書，又可以作為計(jì)算機(jī)算法領(lǐng)域人員的參考書，還可以作為相關(guān)領(lǐng)域人員了解計(jì)算機(jī)算法知識(shí)的參考材料。

內(nèi)容概要

本書主要講述、分析了各種算法的基本原理和解題技巧，以五種通用的算法設(shè)計(jì)技術(shù)為主線論述了分治策略、貪心策略、動(dòng)態(tài)規(guī)劃策略、分支限界法、回溯法等問題，對算法的時(shí)間和空間復(fù)雜性進(jìn)行了分析。在內(nèi)容的選材上注重基本理論和具體實(shí)例的結(jié)合，以便于讀者理解。本書還對概率算法、近似算法、密碼算法和NP問題進(jìn)行了簡單的介紹。    本書可作為計(jì)算機(jī)系本科學(xué)生及研究生的教材，也可作為計(jì)算機(jī)科學(xué)研究和軟件開發(fā)技術(shù)人員的參考用書。

書籍目錄

第1章　緒論  1.1　算法的時(shí)間復(fù)雜性  1.2　算法的空間復(fù)雜性  1.3　兩個(gè)算法的分析實(shí)例  1.4　算法設(shè)計(jì)技術(shù)    1.4.1　分治方法    1.4.2　回溯法    1.4.3　貪心法    1.4.4　動(dòng)態(tài)規(guī)劃法    1.4.5　分支限界法    1.4.6　遞歸方程解的展開式  習(xí)題第2章　排序算法  2.1　插入算法    2.1.1　直接插入排序    2.1.2　折半插入排序    2.1.3　希爾排序  2.2　選擇排序    2.2.1　直接選擇排序    2.2.2　堆排序  2.3　交換排序    2.3.1　冒泡排序    2.3.2　快速排序  2.4　歸并排序  2.5　基數(shù)排序  2.6　外部排序    2.6.1　歸并排序    2.6.2　多步歸并算法  2.7　各種內(nèi)部排序方法的比較討論  習(xí)題第3章　查找樹  3.1　二分查找樹  3.2　2—3—4樹　3.3　紅黑樹　3.4　8樹　習(xí)題第4章　圖的算法　4.1　基本概念　4.2　圖的表示方法　4.3　圖的遍歷　4.4　所有點(diǎn)對之間的最短路徑　4.5　最小生成樹　習(xí)題第5章　串匹配  5.1　簡單的字符串匹配算法  5.2　Knuth—Morris—Pratt（KMP）字符串匹配  5.3　BM算法  5.4　RK算法  習(xí)題第6章　分治算法  6.1　二分搜索  6.2　求最大元和最小元  6.3　大整數(shù)乘法  6.4　矩陣乘法算法  6.5　矩陣乘積的Winograd算法  習(xí)題第7章　貪心算法　7.1　背包問題　7.2　帶時(shí)限的作業(yè)排序　7.3　單源最短路徑問題　7.4　最小生成樹問題　7.5　Dijkstra各點(diǎn)之間最短路徑的優(yōu)化算法　習(xí)題第8章　回溯法　8.1　n皇后問題　8.2　圖的著色問題　8.3　0—1背包問題　8.4　哈密頓回路　8.5　子集和數(shù)　習(xí)題第9章　動(dòng)態(tài)規(guī)劃法  9.1　最長公共子序列問題　9.2　矩陣連乘問題　9.3　多階段決策過程最優(yōu)化問題　9.4　0—1背包問題　9.5　流水線調(diào)度問題　習(xí)題第10章　分支限界法第11章　概率算法第12章　幾何問題算法第13章　NP完全問題第14章　密碼學(xué)算法第15章　近似算法第16章　并行算法參考文獻(xiàn)

章節(jié)摘錄

插圖：第1章　緒論1.4　算法設(shè)計(jì)技術(shù)算法設(shè)計(jì)的基本要求是：首先是正確性（Correctness），程序中不含語法錯(cuò)誤，程序?qū)σ磺泻侠淼妮斎霐?shù)據(jù)都能產(chǎn)生滿足要求的結(jié)果，程序也能對不合理的輸入數(shù)據(jù)產(chǎn)生符合規(guī)格要求的結(jié)果。其次，算法要具有可讀性（Readability），因?yàn)檠芯克惴ǖ哪康氖菫榱碎喿x和交流，可讀性有助于對算法的理解，可讀性有助于對算法的調(diào)試和修改。算法應(yīng)具有高效率與低存儲(chǔ)量，處理速度要快，存儲(chǔ)容量要小，有時(shí)候處理時(shí)間和存儲(chǔ)空間是矛盾的，實(shí)際中，往往是求得時(shí)間和空間的折中。多年來，人們提出了一些通用的算法設(shè)計(jì)技術(shù)如分治方法、貪心法、回溯法、動(dòng)態(tài)規(guī)劃法、分支限界法等，我們用它們解決了許多類的問題，產(chǎn)生有效的算法，其中貪心法、動(dòng)態(tài)規(guī)劃法和分支限界法大多用來解決最優(yōu)化的問題。本小節(jié)簡單地來介紹一下這五種設(shè)計(jì)方法，具體算法將會(huì)在第6、7、8、9、10章分別介紹。1.4.1　分治方法分治法的設(shè)計(jì)思想是將一個(gè)難以直接解決的大問題分割成一些規(guī)模較小但類型相同的問題，以便各個(gè)擊破，分而治之。

圖書封面

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

---

    計(jì)算機(jī)算法 PDF格式下載

---