計算機算法

內容概要

本書是計算機算法在設計與分析文獻的一本經典著作。書中介紹了算法和算法性能的基本知識，基本的數(shù)據(jù)結構知識，重點討論了不同的算法設計策略，研究了下界理論等，提供了計算機算法的設計技術和有效的算法分析，以及大量的詳細實例和實際應用。同時，對NP難和NP完全問題能否有效求解進行了分析。本書還匯聚了各種隨機算法與并行算法的充分比較。    本書為讀者提供了當前流行的對象設計語言C++的實現(xiàn)版本，適合作為高等院校計算機專業(yè) 教材，也是計算機算法方面的重要參考書。

作者簡介

Ellis Horowitz于威斯康星-邁迪遜大學獲得計算機科學博士學位，從事數(shù)據(jù)結構、算法和軟件設計等領域的計算機科學教育。他是美國國家科學基金會主要調查員。

書籍目錄

第1章  導論  1.1  什么是算法  1.2  算法規(guī)范      1.2.1  引言      1.2.2  遞歸算法  1.3  性能分析      1.3.1  空間復雜度      1.3.2  時間復雜度      1.3.3  漸近符號 （O、 Ω、 Θ）      1.3.4  實際復雜度      1.3.5  性能度量  1.4  隨機算法      1.4.1  概率論基礎      1.4.2  隨機算法： 非形式化的描述      1.4.3  識別重復元素      1.4.4  素數(shù)測試      1.4.5  優(yōu)點與缺點  1.5  參考文獻和讀物第2章  基本數(shù)據(jù)結構   2.1  棧和隊列  2.2  樹      2.2.1  術語      2.2.2  二叉樹  2.3  字典      2.3.1  二叉查找樹      2.3.2  代價分攤  2.4  優(yōu)先隊列      2.4.1  堆      2.4.2  堆排序  2.5  集合和不相交集合的并      2.5.1  概述      2.5.2  并和查找操作  2.6  圖      2.6.1  概述      2.6.2  定義      2.6.3  圖的表示方法  2.7  參考文獻和讀物第3章  分治算法  3.1  一般方法  3.2  二叉查找  3.3  查找最大值和最小值  3.4  歸并排序  3.5  快速排序      3.5.1  性能度量      3.5.2  隨機排序算法  3.6  選擇      3.6.1  最壞情況下的最優(yōu)算法      3.6.2  Select2的實現(xiàn)  3.7  Strassen矩陣乘法  3.8  凸包      3.8.1  幾種原始幾何方法      3.8.2  QuickHull算法      3.8.3  Graham掃描算法      3.8.4  一個O(nlogn)的分治算法  3.9  參考文獻和讀物  3.10  附加習題第4章  貪心算法  4.1  一般方法  4.2  背包問題  4.3  樹節(jié)點分割  4.4  帶有期限的作業(yè)順序問題  4.5  最小代價生成樹      4.5.1  Prim算法      4.5.2  Kruskal算法      4.5.3  一個最優(yōu)隨機算法（*）  4.6  磁帶的最優(yōu)存儲  4.7  最優(yōu)歸并模式  4.8  單源最短路徑  4.9  參考文獻和讀物  4.10  附加習題第5章  動態(tài)規(guī)劃  5.1  一般方法  5.2  多部圖  5.3  每一對頂點之間的最短路徑  5.4  單源最短路徑： 普通權值  5.5  最優(yōu)二叉查找樹(*)  5.6  串編輯  5.7  0/1背包  5.8  可靠性設計  5.9  旅行商問題  5.10  流水作業(yè)調度  5.11  參考文獻和讀物  5.12  附加習題第6章  基本的查找和遍歷技術  6.1  二叉樹算法  6.2  圖算法      6.2.1  廣度優(yōu)先搜索和遍歷      6.2.2  深度優(yōu)先搜索和遍歷  6.3  連通分支和生成樹  6.4  雙連通分支和DFS算法  6.5  參考文獻和讀物第7章  回溯  7.1  一般方法  7.2  8皇后問題  7.3  子集求和問題  7.4  圖的著色  7.5  哈密頓回路  7.6  背包問題  7.7  參考文獻和讀物  7.8  附加習題第8章  分支限界法  8.1  一般方法      8.1.1  最小代價查找      8.1.2  15拼板： 一個例子      8.1.3  LC查找的控制抽象      8.1.4  限界      8.1.5  FIFO分支限界法      8.1.6  LC分支限界法  8.2  0/1背包問題      8.2.1  LC分支限界法求解      8.2.2  FIFO分支限界法求解  8.3  旅行商問題(*)  8.4  效率因素  8.5  參考文獻和讀物第9章  代數(shù)問題  9.1  一般方法  9.2  計算和插值  9.3  快速傅里葉變換      9.3.1  FFT的原地版本      9.3.2  一些保留問題  9.4  模運算  9.5  更快的計算和插值  9.6  參考文獻和讀物第10章  下界理論  10.1  比較樹      10.1.1  有序查找      10.1.2  排序      10.1.3  選擇  10.2  喻示和對立論      10.2.1  歸并      10.2.2  最大和次大      10.2.3  狀態(tài)空間方法      10.2.4  選擇  10.3  通過規(guī)約求下界      10.3.1  尋找凸包      10.3.2  不相交集合問題      10.3.3  即時中值查找      10.3.4  三角矩陣相乘      10.3.5  下三角矩陣求逆      10.3.6  計算傳遞閉包  10.4  解決代數(shù)問題的技術(*)  10.5  參考文獻和讀物第11章  難與完全問題  11.1  基本概念      11.1.1  非確定性算法      11.1.2  難和完全類  11.2  Cook定理（*）  11.3  難的圖問題      11.3.1  團判定問題      11.3.2  節(jié)點覆蓋判定問題      11.3.3  色數(shù)判定問題      11.3.4  有向哈密頓回路（*）      11.3.5  旅行商判定問題      11.3.6  與/或圖判定問題  11.4  難的調度問題      11.4.1  調度相同的處理器      11.4.2  流水作業(yè)調度      11.4.3  作業(yè)安排調度  11.5  難的代碼生成問題      11.5.1  帶有公共子表達式的代碼生成      11.5.2  實現(xiàn)并行賦值指令  11.6  一些簡化的難問題  11.7  參考文獻和讀物  11.8  附加習題第12章  近似算法  12.1  概述  12.2  絕對近似      12.2.1  平面圖著色      12.2.2  最多程序存儲問題      12.2.3  難的絕對近似  12.3  ε近似      12.3.1  獨立任務的調度      12.3.2  裝箱問題      12.3.3  難的ε近似問題  12.4  多項式時間近似方案      12.4.1  獨立任務的調度      12.4.2  0/1背包  12.5  完全多項式時間近似方案      12.5.1  舍入法      12.5.2  區(qū)間劃分法      12.5.3  分割法  12.6  概率上的好算法(*)  12.7  參考文獻和讀物  12.8  附加習題第13章  PRAM算法  13.1  概述  13.2  計算模型  13.3  基本技術和算法      13.3.1  前綴計算      13.3.2  表排序  13.4  選擇      13.4.1  使用n?2個處理器選擇最大值      13.4.2  使用n個處理器選擇最大值      13.4.3  在整數(shù)中選擇最大值      13.4.4  使用n?2個處理器的一般選擇問題      13.4.5  一個工作最優(yōu)的隨機算法(*)  13.5  歸并      13.5.1  對數(shù)時間算法      13.5.2  奇偶歸并      13.5.3  工作最優(yōu)的算法      13.5.4  O(log logm)時間算法  13.6  排序      13.6.1  奇偶歸并排序      13.6.2  隨機選擇算法      13.6.3  Preparata算法      13.6.4  Reischuk隨機算法（*）  13.7  圖問題      13.7.1  計算傳遞閉包的另一種算法      13.7.2  每一對頂點之間的最短路徑  13.8  計算凸包  13.9  下界      13.9.1  平均情況下排序的下界      13.9.2  尋找最大值  13.10  參考文獻和讀物  13.11  附加習題第14章  網(wǎng)格算法  14.1  計算模型  14.2  分組路由      14.2.1  線性陣列中的分組路由      14.2.2  網(wǎng)格上PPR的貪心算法      14.2.3  具有小隊列的隨機算法  14.3  基本算法      14.3.1  廣播      14.3.2  前綴計算      14.3.3  數(shù)據(jù)集中      14.3.4  稀疏枚舉排序  14.4  選擇      14.4.1  n=p(*)時的隨機算法      14.4.2  n＞p(*)時的隨機選擇      14.4.3  n＞p時的確定性算法  14.5  歸并      14.5.1  在線性陣列上的順序號歸并      14.5.2  線性陣列上的奇偶歸并      14.5.3  在網(wǎng)格上的奇偶歸并  14.6  排序      14.6.1  在線性陣列上的排序      14.6.2  在網(wǎng)格上的排序  14.7  圖問題      14.7.1  傳遞閉包的n×n網(wǎng)格算法      14.7.2  每一對頂點之間的最短路徑  14.8  計算凸包  14.9  參考文獻和讀物  14.10  附加習題第15章  超立方體算法  15.1  計算模型      15.1.1  超立方體      15.1.2  蝶形網(wǎng)絡      15.1.3  其他網(wǎng)絡的嵌入  15.2  PPR路由      15.2.1  貪心算法      15.2.2  隨機算法  15.3  基本算法      15.3.1  廣播      15.3.2  前綴計算      15.3.3  數(shù)據(jù)集中      15.3.4  稀疏枚舉排序  15.4  選擇      15.4.1  n=p(*)時的隨機算法      15.4.2  n＞p(*)時的隨機選擇      15.4.3  n＞p時的確定性算法  15.5  歸并      15.5.1  奇偶歸并      15.5.2  雙調諧歸并  15.6  排序      15.6.1  奇偶歸并排序      15.6.2  雙調諧排序  15.7  圖問題  15.8  計算凸包  15.9  參考文獻和讀物  15.10  附加習題索引

編輯推薦

　　《計算機算法（C++版）》作者均是世界著名的計算機科學家，在計算機科學理論和算法領域做出了杰出的貢獻?！队嬎銠C算法（C++版）》著重在計算機科學發(fā)展領域中，推動新的計算機算法的設計和分析，是一本經典著作，也是計算機算法方面的重要參考書。書中為讀者提供了計算機算法的設計技術，對計算機算法的實際設計提供了有效的算法分析。在計算機算法設計方面提供了大量的詳細實例和實際應用，并致力于隨機算法和并行算法富有成效的深入研究和開發(fā)?！队嬎銠C算法（C++版）》為讀者提供了當前流行的對象設計語言C++的實現(xiàn)版本，以及現(xiàn)代計算機科學發(fā)展和研究的最新研究成果。

圖書封面

圖書標簽Tags

無

評論、評分、閱讀與下載

---

    計算機算法 PDF格式下載

---