演算法基礎(第5版) Foundations of Algorithms, 5/e

Richard Neapolitan

買這商品的人也買了...

商品描述

<內容介紹> 

 那不勒坦著的《演算法基礎(第5版)》通過大量示例介紹了演算法設計、演算法的複雜度分析以及計算複雜度。主要內容有:演算法設計與分析、分而治之方法、動態規劃方法、貪婪方法、回溯演算法、分支定界演算法、計算複雜度、難解性NP理論、遺傳演算法和遺傳編程、數論演算法、並行演算法等。此外,本書在每章末尾都提供了大量練習,而且還提供了全面的教輔材料及答案,是教授和學
    本書適合高等院校學生、程序員及演算法分析和設計人員。

<章節目錄>

第1章 演算法:效率、分析和階
  1.1 演算法
  1.2 開發高效演算法的重要性
    1.2.1 順序查找與二分查找的對比
    1.2.2 斐波那契序列
  1.3 演算法分析
    1.3.1 複雜度分析
    1.3.2 理論應用
    1.3.3 正確性分析
  1.4 階
    1.4.1 階的直觀介紹
    1.4.2 階數的嚴謹介紹
    1.4.3 利用極限計算階
  1.5 本書概要
  1.6 習題
第2章 分而治之
  2.1 二分查找
  2.2 合併排序
  2.3 分而治之方法
  2.4 快速排序(分割交換排序)
  2.5 Strassen矩陣乘法演算法
  2.6 大整數的算術運算
    2.6.1 大整數的表示:加法和其他線性時間運算
    2.6.2 大整數的乘法
  2.7 確定閾值
  2.8 不應使用分而治之方法的情況
  2.9 習題
第3章 動態規劃
  3.1 二項式係數
  3.2 Floyd短路徑演算法
  3.3 動態規劃與優化問題
  3.4 矩陣鏈乘法
  3.5 優二叉查找樹
  3.6 旅行推銷員問題
  3.7 序列對準
  3.8 習題
第4章 貪婪方法
  4.1 小生成樹
    4.1.1 Prim演算法
    4.1.2 Kruskal演算法
    4.1.3 Prim演算法與Kruskal演算法的比較
    4.1.4 終討論
  4.2 單源短路徑的Dijkstra演算法
  4.3 調度計劃
    4.3.1 使系統內總時間短
    4.3.2 帶有終期限的調度安排
  4.4 霍夫曼編碼
    4.4.1 前綴碼
    4.4.2 霍夫曼演算法
  4.5 貪婪方法與動態規劃的比較:背包問題

    4.5.1 0-1背包問題的一種貪婪方法
    4.5.2 部分背包問題的貪婪方法
    4.5.3 0-1背包問題的動態規劃方法
    4.5.4 0-1背包問題動態規劃演算法的改進
  4.6 習題
第5章 回溯
  5.1 回溯方法
  5.2 n皇後問題
  5.3 用蒙特卡洛演算法估計回溯演算法的效率
  5.4 「子集之和」問題
  5.5 圖的著色
  5.6 哈密頓迴路問題
  5.7 0-1背包問題
    5.7.1 0-1背包問題的回溯演算法
    5.7.2 比較0-1背包問題的動態規劃演算法與回溯演算法
  5.8 習題
第6章 分支定界
  6.1 用0-1背包問題說明分支定界
    6.1.1 帶有分支定界修剪的寬度優先查找
    6.1.2 帶有分支定界修剪的佳優先查找
  6.2 旅行推銷員問題
  6.3 溯因推理(診斷)
  6.4 習題
第7章 計算複雜度介紹:排序問題
  7.1 計算複雜度
  7.2 插入排序和選擇排序
  7.3 每次比較多減少一個倒置的演算法的下限
  7.4 再談合併排序
  7.5 再談快速排序
  7.6 堆排序
    7.6.1 堆和基本堆例程
    7.6.2 堆排序的一種實現
  7.7 合併排序、快速排序和堆排序的比較
  7.8 僅通過鍵的比較進行排序的下限
    7.8.1 排序演算法的決策樹
    7.8.2 差情況下的下限
    7.8.3 平均情況下的下限
  7.9 分配排序(基數排序)
  7.10 習題
第8章 再談計算複雜度:查找問題
  8.1 僅通過鍵的比較進行查找的下限
    8.1.1 差表現的下限
    8.1.2 平均情況下的下限
  8.2 插值查找
  8.3 樹中的查找
    8.3.1 二叉查找樹
    8.3.2 B樹
  8.4 散列
  8.5 選擇問題:對手論證
    8.5.1 找出大鍵

    8.5.2 同時找出大鍵和小鍵
    8.5.3 找出第二大的鍵
    8.5.4 查找第k小的鍵
    8.5.5 選擇問題的一種概率演算法
  8.6 習題
第9章 計算複雜度和難解性:NP理論簡介
  9.1 難解性
  9.2 再談輸入規模
  9.3 三類一般問題
    9.3.1 已經找到多項式時間演算法的問題
    9.3.2 已經證明難解的問題
    9.3.3 未被證明是難解的,但也從來沒有找到多項式時間演算法的問題
  9.4 NP理論
    9.4.1 集合P和
    9.4.2 NP完全問題
    9.4.3 NP困難、NP容易和NP等價問題
  9.5 處理NP困難問題
    9.5.1 旅行推銷員問題的近似演算法
    9.5.2 裝箱問題的近似演算法
  9.6 習題
第10章 遺傳演算法和遺傳編程
  10.1 遺傳知識複習
  10.2 遺傳演算法
    10.2.1 演算法
    10.2.2 說明範例
    10.2.3 旅行推銷員問題
  10.3 遺傳編程
    10.3.1 說明範例
    10.3.2 人造螞蟻
    10.3.3 在金融貿易中的應用
  10.4 討論及擴展閱讀
  10.5 習題
第11章 數論演算法
  11.1 數論回顧
    11.1.1 合數與質數
    11.1.2 大公約數
    11.1.3 質因子分解
    11.1.4 小公倍數
  11.2 計算大公約數
    11.2.1 歐氏演算法
    11.2.2 歐氏演算法的擴展
  11.3 模運算回顧
    11.3.1 群論
    11.3.2 關於n同餘
    11.3.3 子群
  11.4 模線性方程的求解
  11.5 計算模的冪
  11.6 尋找大質數
    11.6.1 尋找大質數
    11.6.2 檢查一個數字是否為質數

  11.7 RSA公鑰密碼系統
    11.7.1 公鑰加密系統
    11.7.2 RSA加密系統
  11.8 習題
第12章 並行演算法簡介
  12.1 並行體系結構
    12.1.1 控制機制
    12.1.2 地址空間的組織
    12.1.3 因特網絡
  12.2 PRAM模型
    12.2.1 為CREWPRAM模型設計演算法
    12.2.2 為CRCWPRAM模型設計演算法
  12.3 習題
  附錄A必備數學知識回顧
  附錄B求解遞歸方程:在遞歸演算法分析
  中的應用
  附錄C不交集的數據結構
  參考文獻