《計算機算法》:主要講述、分析了各種算法的基本原理和解題技巧，以五種通用 -百科知識中文網

信息

計算機算法[平裝]

~胡金初(編者)
市場價:￥21.00
價格:￥14.90
為您節省:￥6.10(7.1折)
VIP價:￥14.45SVIP價:￥14.16

內容簡介

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

第1章緒論
1.1算法的時間複雜性
1.2算法的空間複雜性
1.3兩個算法的分析實例
1.4算法設計技術
1.4.1分治方法
1.4.2回溯法
1.4.3貪心法
1.4.4動態規劃法
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基數排序
2.6外部排序
2.6.1歸併排序
2.6.2多步歸併算法
2.7各種內部排序方法的比較討論
習題
第3章查找樹
3.1二分查找樹
3.22—3—4樹
3.3紅黑樹
3.48樹
習題
第4章圖的算法
4.1基本概念
4.2圖的表示方法
4.3圖的遍歷
4.4所有點對之間的最短路徑
4.5最小生成樹
習題
第5章串匹配
5.1簡單的字元串匹配算法
5.2Knuth—Morris—Pratt（KMP）字元串匹配
5.3BM算法
5.4RK算法
習題
第6章分治算法
6.1二分搜尋
6.2求最大元和最小元
6.3大整數乘法
6.4矩陣乘法算法
6.5矩陣乘積的Winograd算法
習題
第7章貪心算法
7.1背包問題
7.2帶時限的作業排序
7.3單源最短路徑問題
7.4最小生成樹問題
7.5Dijkstra各點之間最短路徑的最佳化算法
習題
第8章回溯法
8.1n皇后問題
8.2圖的著色問題
8.30—1背包問題
8.4哈密頓迴路
8.5子集和數
習題
第9章動態規劃法
9.1最長公共子序列問題
9.2矩陣連乘問題
9.3多階段決策過程最最佳化問題
9.40—1背包問題
9.5流水線調度問題
習題
第10章分支限界法
10.1分支限界的策略
10.20－1背包問題
習題
第11章機率算法
11.l隨機數
11.2數值機率算法
11.3蒙特卡羅算法
11.4拉斯維加斯算法
11.5舍伍德算法
習題
第12章幾何問題算法
12.1直線相交問題的算法
12.2點是否包含在多邊形內部
12.3求凸包問題
習題
第13章NP完全問題
13.1不確定算法和不確定圖靈機
13.2NP難度和NP完全問題
13.3COOK定理
13.4幾個NP完全問題
習題
第14章密碼學算法
14.1什麼是密碼
14.2基本數論
14.3背包公鑰密碼
14.4RSA算法
14.5數字簽名
習題
第15章近似算法
15.1任務調度近似算法.
15.2頂點覆蓋問題近似算法
15.3旅行商問題的近似解
15.4子集和數問題的近似算法
習題
第16章並行算法
16.1並行計算機
16.2並行算法的基本概念
16.3並行算法的描述
16.4SIMD-SM上的非線性方程求根同步並行算法
16.5SIMD-SM上的同步並行求和算法
16.6SIMD-CC超立方機器上的同步並行求和算法
16.7MIMD-SM上的異步並行求和算法
習題
參考文獻

序言

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