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

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