計算機算法

第1章  導(dǎo)論
  1.1  什么是算法
  1.2  算法規(guī)范
      1.2.1  引言
      1.2.2  遞歸算法
  1.3  性能分析
      1.3.1  空間復(fù)雜度
      1.3.2  時間復(fù)雜度
      1.3.3  漸近符號 （O、 Ω、 Θ）
      1.3.4  實際復(fù)雜度
      1.3.5  性能度量
  1.4  隨機算法
      1.4.1  概率論基礎(chǔ)
      1.4.2  隨機算法： 非形式化的描述
      1.4.3  識別重復(fù)元素
      1.4.4  素數(shù)測試
      1.4.5  優(yōu)點與缺點
  1.5  參考文獻(xiàn)和讀物
第2章  基本數(shù)據(jù)結(jié)構(gòu) 
  2.1  棧和隊列
  2.2  樹
      2.2.1  術(shù)語
      2.2.2  二叉樹
  2.3  字典
      2.3.1  二叉查找樹
      2.3.2  代價分?jǐn)?br />  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  參考文獻(xiàn)和讀物
第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  參考文獻(xiàn)和讀物
  3.10  附加習(xí)題
第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  參考文獻(xiàn)和讀物
  4.10  附加習(xí)題
第5章  動態(tài)規(guī)劃
  5.1  一般方法
  5.2  多部圖
  5.3  每一對頂點之間的最短路徑
  5.4  單源最短路徑： 普通權(quán)值
  5.5  最優(yōu)二叉查找樹(*)
  5.6  串編輯
  5.7  0/1背包
  5.8  可靠性設(shè)計
  5.9  旅行商問題
  5.10  流水作業(yè)調(diào)度
  5.11  參考文獻(xiàn)和讀物
  5.12  附加習(xí)題
第6章  基本的查找和遍歷技術(shù)
  6.1  二叉樹算法
  6.2  圖算法
      6.2.1  廣度優(yōu)先搜索和遍歷
      6.2.2  深度優(yōu)先搜索和遍歷
  6.3  連通分支和生成樹
  6.4  雙連通分支和DFS算法
  6.5  參考文獻(xiàn)和讀物
第7章  回溯
  7.1  一般方法
  7.2  8皇后問題
  7.3  子集求和問題
  7.4  圖的著色
  7.5  哈密頓回路
  7.6  背包問題
  7.7  參考文獻(xiàn)和讀物
  7.8  附加習(xí)題
第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  參考文獻(xiàn)和讀物
第9章  代數(shù)問題
  9.1  一般方法
  9.2  計算和插值
  9.3  快速傅里葉變換
      9.3.1  FFT的原地版本
      9.3.2  一些保留問題
  9.4  模運算
  9.5  更快的計算和插值
  9.6  參考文獻(xiàn)和讀物
第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ù)問題的技術(shù)(*)
  10.5  參考文獻(xiàn)和讀物
第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  難的調(diào)度問題
      11.4.1  調(diào)度相同的處理器
      11.4.2  流水作業(yè)調(diào)度
      11.4.3  作業(yè)安排調(diào)度
  11.5  難的代碼生成問題
      11.5.1  帶有公共子表達(dá)式的代碼生成
      11.5.2  實現(xiàn)并行賦值指令
  11.6  一些簡化的難問題
  11.7  參考文獻(xiàn)和讀物
  11.8  附加習(xí)題
第12章  近似算法
  12.1  概述
  12.2  絕對近似
      12.2.1  平面圖著色
      12.2.2  最多程序存儲問題
      12.2.3  難的絕對近似
  12.3  ε近似
      12.3.1  獨立任務(wù)的調(diào)度
      12.3.2  裝箱問題
      12.3.3  難的ε近似問題
  12.4  多項式時間近似方案
      12.4.1  獨立任務(wù)的調(diào)度
      12.4.2  0/1背包
  12.5  完全多項式時間近似方案
      12.5.1  舍入法
      12.5.2  區(qū)間劃分法
      12.5.3  分割法
  12.6  概率上的好算法(*)
  12.7  參考文獻(xiàn)和讀物
  12.8  附加習(xí)題
第13章  PRAM算法
  13.1  概述
  13.2  計算模型
  13.3  基本技術(shù)和算法
      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  奇偶?xì)w并
      13.5.3  工作最優(yōu)的算法
      13.5.4  O(log logm)時間算法
  13.6  排序
      13.6.1  奇偶?xì)w并排序
      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  參考文獻(xiàn)和讀物
  13.11  附加習(xí)題
第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  線性陣列上的奇偶?xì)w并
      14.5.3  在網(wǎng)格上的奇偶?xì)w并
  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  參考文獻(xiàn)和讀物
  14.10  附加習(xí)題
第15章  超立方體算法
  15.1  計算模型
      15.1.1  超立方體
      15.1.2  蝶形網(wǎng)絡(luò)
      15.1.3  其他網(wǎng)絡(luò)的嵌入
  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  奇偶?xì)w并
      15.5.2  雙調(diào)諧歸并
  15.6  排序
      15.6.1  奇偶?xì)w并排序
      15.6.2  雙調(diào)諧排序
  15.7  圖問題
  15.8  計算凸包
  15.9  參考文獻(xiàn)和讀物
  15.10  附加習(xí)題
索引