演算法設計與分析--C++語言描述(第4版新工科建設之路電腦類專業系列教材普通高等教育十一五國家級規劃教材)

作者：編者:陳慧南|責編:冉哲
出版社：電子工業
ISBN：9787121483325

出版日期：2025/01/01
裝幀：平裝
頁數：300

人民幣：RMB 69 元售價：元

內容大鋼

本書為普通高等教育「十一五」國家級規劃教材。本書內容分為3部分：演算法和演算法分析、演算法設計策略及求解困難問題。第1部分介紹演算法問題求解基礎和演算法分析基礎，以及兩種新的數據結構：伸展樹與跳錶；第2部分討論常用的演算法設計策略，包括基本搜索和遍歷方法、分治法、貪心法、動態規劃法、回溯法和分枝限界法；第3部分介紹NP完全問題、隨機演算法、近似演算法、遺傳演算法和密碼演算法，並對現代密碼學和數論做了簡要論述。本書結構清晰、內容翔實、邏輯嚴謹、講解深入淺出。書中演算法有完整的C++程序，這些程序構思精巧，有詳細註釋，並且已在C++環境下編譯通過能正確運行。它們既是講解演算法設計的示例，幫助理解和掌握複雜抽象的演算法設計，也是很好的C++程序設計示例。書中包含大量實例，並附有豐富的習題，便於教學和自學。本書可作為高等學校電腦及其他相關專業本科生和研究生「演算法設計與分析」課程的教材或參考書，是「演算法與數據結構」或「數據結構」課程有益的教學參考書，也可供電腦相關從業者及其他希望了解和學習演算法知識的人員參考。

作者介紹

編者:陳慧南|責編:冉哲

第1部分  演算法和演算法分析
  第1章  演算法問題求解基礎
    1.1  演算法概述
      1.1.1  什麼是演算法
      1.1.2  為什麼學習演算法
    1.2  問題求解方法
      1.2.1  問題和問題求解
      1.2.2  問題求解過程
      1.2.3  軟體生命周期
    1.3  演算法設計與分析
      1.3.1  演算法問題求解過程
      1.3.2  如何設計演算法
      1.3.3  如何表示演算法
      1.3.4  如何確認演算法
      1.3.5  如何分析演算法
    1.4  遞歸和歸納
      1.4.1  遞歸
      1.4.2  遞歸演算法示例
      1.4.3  歸納證明
    習題1
  第2章  演算法分析基礎
    2.1  演算法複雜度
      2.1.1  什麼是好的演算法
      2.1.2  影響程序執行時間的因素
      2.1.3  演算法的時間複雜度
      2.1.4  使用程序步分析演算法
      2.1.5  演算法的空間複雜度
    2.2  漸近表示法
      2.2.1  大O記號
      2.2.2  Ω記號
      2.2.3  Θ記號
      2.2.4  小o記號
      2.2.5  演算法按時間複雜度分類
    2.3  遞推關係
      2.3.1  遞推方程
      2.3.2  替換方法
      2.3.3  迭代方法
      2.3.4  遞歸樹
      2.3.5  主方法
    2.4  分攤分析
      2.4.1  聚集分析
      2.4.2  會計方法
      2.4.3  勢能方法
    習題2
  第3章  伸展樹與跳錶
    3.1  伸展樹
      3.1.1  二叉搜索樹
      3.1.2  自調節樹和伸展樹
      3.1.3  伸展操作
      3.1.4  伸展樹類

      3.1.5  旋轉的實現
      3.1.6  插入運算的實現
      3.1.7  分攤分析
    3.2  跳錶
      3.2.1  什麼是跳錶
      3.2.2  跳錶類
      3.2.3  層次分配
      3.2.4  插入運算的實現
      3.2.5  性能分析
    習題3
第2部分  演算法設計策略
  第4章  基本搜索和遍歷方法
    4.1  基本概念
    4.2  圖的搜索和遍歷
      4.2.1  搜索方法
      4.2.2  鄰接表類
      4.2.3  廣度優先搜索
      4.2.4  深度優先搜索
    4.3  雙連通分量
      4.3.1  基本概念
      4.3.2  發現關節點
      4.3.3  構造雙連通圖
    4.4  與或圖
      4.4.1  問題分解
      4.4.2  判斷與或樹是否可解
      4.4.3  構建解樹
    4.5  區間最值查詢（RMQ）
      4.5.1  區間信息維護與查詢
      4.5.2  ST演算法求解RMQ問題
    4.6  最近公共祖先（LCA）
      4.6.1  概述
      4.6.2  倍增法求解LCA問題
      4.6.3  在線RMQ法求解LCA問題
      4.6.4  Tarjan演算法求解LCA問題
    習題4
  第5章  分治法
    5.1  一般方法
      5.1.1  分治法的基本思想
      5.1.2  演算法分析
      5.1.3  數據結構
    5.2  求最大、最小元
      5.2.1  分治法求解
      5.2.2  時間分析
    5.3  二分搜索
      5.3.1  分治法求解
      5.3.2  對半搜索
      5.3.3  二叉判定樹
      5.3.4  搜索演算法的時間下界
    5.4  排序問題
      5.4.1  合併排序

      5.4.2  快速排序
      5.4.3  排序演算法的時間下界
    5.5  選擇問題
      5.5.1  分治法求解
      5.5.2  隨機選擇主元
      5.5.3  線性時間選擇演算法
      5.5.4  時間分析
      5.5.5  允許重複元素的選擇演算法
    5.6  斯特拉森矩陣乘法
      5.6.1  分治法求解
      5.6.2  斯特拉森矩陣乘法簡介
    習題5
  第6章  貪心法
    6.1  一般方法
    6.2  背包問題
      6.2.1  問題描述
      6.2.2  貪心法求解
      6.2.3  演算法正確性
    6.3  帶時限的作業排序問題
      6.3.1  問題描述
      6.3.2  貪心法求解
      6.3.3  演算法正確性
      6.3.4  可行性判定
      6.3.5  作業排序貪心演算法
      6.3.6  改進演算法
    6.4  最佳合併模式
      6.4.1  問題描述
      6.4.2  貪心法求解
      6.4.3  演算法正確性
    6.5  最小代價生成樹
      6.5.1  問題描述
      6.5.2  貪心法求解
      6.5.3  普里姆演算法
      6.5.4  克魯斯卡爾演算法
      6.5.5  演算法正確性
    6.6  單源最短路徑
      6.6.1  問題描述
      6.6.2  貪心法求解
      6.6.3  迪傑斯特拉演算法
      6.6.4  演算法正確性
    6.7  磁帶最優存儲
      6.7.1  單帶最優存儲
      6.7.2  多帶最優存儲
    6.8  貪心法的基本要素
      6.8.1  最優量度標準
      6.8.2  最優子結構
    習題6
  第7章  動態規劃法
    7.1  一般方法和基本要素
      7.1.1  一般方法

      7.1.2  基本要素
      7.1.3  多段圖問題
      7.1.4  資源分配問題
      7.1.5  關鍵路徑問題
    7.2  每對結點間的最短路徑
      7.2.1  問題描述
      7.2.2  動態規劃法求解
      7.2.3  弗洛伊德演算法
      7.2.4  演算法正確性
    7.3  矩陣連乘
      7.3.1  問題描述
      7.3.2  動態規劃法求解
      7.3.3  矩陣連乘演算法
      7.3.4  備忘錄方法
    7.4  最長公共子序列
      7.4.1  問題描述
      7.4.2  動態規劃法求解
      7.4.3  最長公共子序列演算法
      7.4.4  改進演算法
    7.5  最優二叉搜索樹
      7.5.1  問題描述
      7.5.2  動態規劃法求解
      7.5.3  最優二叉搜索樹演算法
    7.6  0/1背包問題
      7.6.1  問題描述
      7.6.2  動態規劃法求解
      7.6.3  0/1背包問題演算法框架
      7.6.4  0/1背包問題演算法
      7.6.5  性能分析
      7.6.6  使用啟髮式方法
    7.7  流水線作業調度
      7.7.1  問題描述
      7.7.2  動態規劃法求解
      7.7.3  Johnson演算法
    習題7
  第8章  回溯法
    8.1  一般方法
      8.1.1  基本概念
      8.1.2  剪枝函數和回溯法
      8.1.3  回溯法的效率分析
    8.2  n-皇后問題
      8.2.1  問題描述
      8.2.2  回溯法求解
      8.2.3  n-皇后演算法
      8.2.4  時間分析
    8.3  子集和數問題
      8.3.1  問題描述
      8.3.2  回溯法求解
      8.3.3  子集和數演算法
    8.4  圖著色問題

      8.4.1  問題描述
      8.4.2  回溯法求解
      8.4.3  圖著色演算法
      8.4.4  時間分析
    8.5  哈密頓環問題
      8.5.1  問題描述
      8.5.2  哈密頓環演算法
    8.6  0/1背包問題
      8.6.1  問題描述
      8.6.2  回溯法求解
      8.6.3  限界函數
      8.6.4  0/1背包問題演算法
    8.7  批處理作業調度
      8.7.1  問題描述
      8.7.2  回溯法求解
      8.7.3  批處理作業調度演算法
    習題8
  第9章  分枝限界法
    9.1  一般方法
      9.1.1  分枝限界法概述
      9.1.2  LC分枝限界法
      9.1.3  15謎問題
    9.2  求最優解的分枝限界法
      9.2.1  上下界函數
      9.2.2  FIFO分枝限界法
      9.2.3  LC分枝限界法
    9.3  帶時限的作業排序
      9.3.1  問題描述
      9.3.2  分枝限界法求解
      9.3.3  帶時限的作業排序演算法
    9.4  0/1背包問題
      9.4.1  問題描述
      9.4.2  分枝限界法求解
      9.4.3  0/1背包問題演算法
    9.5  旅行商問題
      9.5.1  問題描述
      9.5.2  分枝限界法求解
    9.6  批處理作業調度
      9.6.1  問題描述
      9.6.2  分枝限界法求解
      9.6.3  批處理作業調度演算法
    習題9
第3部分  求解困難問題
  第10章  NP完全問題
    10.1  基本概念
      10.1.1  不確定演算法和不確定機
      10.1.2  可滿足性問題
      10.1.3  P類問題和NP類問題
      10.1.4  NP難度問題和NP完全問題
    10.2  Cook定理和證明

      10.2.1  Cook定理
      10.2.2  簡化的不確定機模型
      10.2.3  證明Cook定理
    10.3  一些典型的NP完全問題
      10.3.1  最大集團
      10.3.2  頂點覆蓋
      10.3.3  三元CNF可滿足性
      10.3.4  圖的著色數
      10.3.5  有向哈密頓環
      10.3.6  恰切覆蓋
      10.3.7  子集和數
      10.3.8  分划
    習題10
  第11章  隨機演算法
    11.1  基本概念
      11.1.1  隨機演算法概述
      11.1.2  隨機數發生器
      11.1.3  隨機演算法分類
    11.2  拉斯維加斯演算法
      11.2.1  標記重複元素演算法
      11.2.2  性能分析
      11.2.3  n-皇后問題
      11.2.4  拉斯維加斯演算法和回溯法的結合演算法
    11.3  蒙特卡羅演算法
      11.3.1  多數元素問題
      11.3.2  素數測試問題
      11.3.3  偽素數測試問題
      11.3.4  米勒-拉賓演算法
    11.4  舍伍德演算法
      11.4.1  快速排序舍伍德演算法
      11.4.2  性能分析
      11.4.3  舍伍德演算法的其他應用
    習題11
  第12章  近似演算法
    12.1  近似演算法的性能
      12.1.1  基本概念
      12.1.2  絕對性能保證
      12.1.3  相對性能保證
      12.1.4  近似方案
    12.2  絕對近似演算法的應用
      12.2.1  最多程序存儲問題
      12.2.2  NP難度問題
    12.3  □（數學符號）-近似演算法的應用
      12.3.1  頂點覆蓋問題
      12.3.2  旅行商問題
      12.3.3  NP難度□（數學符號）-近似旅行商問題
      12.3.4  具有三角不等式性質的旅行商問題
      12.3.5  多機調度問題
    12.4  □（數學符號）（n）-近似演算法
      12.4.1  集合覆蓋問題

      12.4.2  集合覆蓋問題近似演算法
      12.4.3  ln（n）-近似演算法
    12.5  多項式時間近似方案
      12.5.1  多機調度近似方案
      12.5.2  時間分析
    12.6  子集和數問題的完全多項式時間近似方案
      12.6.1  子集和數問題的指數時間演算法
      12.6.2  完全多項式時間近似方案
    習題12
  第13章  遺傳演算法
    13.1  進化計算
    13.2  遺傳演算法的生物學基礎
    13.3  遺傳演算法的基本思想
    13.4  基本遺傳演算法
      13.4.1  基本遺傳演算法的構成要素
      13.4.2  基本遺傳演算法的流程圖
    13.5  遺傳演算法的特點和應用
      13.5.1  遺傳演算法的特點
      13.5.2  遺傳演算法的應用
    13.6  基本遺傳演算法的實現方法
      13.6.1  數據結構
      13.6.2  主程序
      13.6.3  選擇運算
      13.6.4  交叉運算
      13.6.5  變異運算
    13.7  旅行商問題
      13.7.1  排列編碼
      13.7.2  目標函數和適應度函數
      13.7.3  錦標賽選擇法
      13.7.4  順序交叉
      13.7.5  交換變異
      13.7.6  參數選擇
      13.7.7  實例運行結果
    習題13
  第14章  密碼演算法
    14.1  信息安全和密碼學
      14.1.1  信息安全
      14.1.2  什麼是密碼
      14.1.3  密碼體制
    14.2  數論初步
    14.3  背包問題密碼演算法
      14.3.1  背包問題
      14.3.2  超遞增背包問題
      14.3.3  由私人密鑰產生公開密鑰
      14.3.4  加密方法
      14.3.5  解密方法
      14.3.6  背包問題安全性
    14.4  RSA演算法
      14.4.1  RSA演算法概述
      14.4.2  RSA演算法安全性

    14.5  散列函數和消息認證
      14.5.1  散列函數
      14.5.2  散列函數的結構
      14.5.3  消息認證
    14.6  數字簽名
      14.6.1  RSA演算法實現直接數字簽名
      14.6.2  需仲裁的數字簽名
    習題14
參考文獻

同類熱銷排行榜

最近瀏覽的商品

演算法設計與分析--C++語言描述(第4版新工科建設之路電腦類專業系列教材普通高等教育十一五國家級規劃教材)