計算機算法

前言

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

內(nèi)容概要

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

書籍目錄

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

章節(jié)摘錄

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

圖書封面

評論、評分、閱讀與下載

---

    計算機算法 PDF格式下載

---