算法設計技巧與分析(2016年電子工業出版社出版的圖書)

《算法設計技巧與分析》是2016年電子工業出版社出版的圖書。

基本介紹

• 中文名：算法設計技巧與分析
• 作者：M. H. Alsuwaiyel 
• 譯者：吳偉昶、方世昌
• 出版時間：2016年9月 
• 出版社： 電子工業出版社
• 頁數：332 頁
• ISBN： 9787121298349
• 原作品：Algorithms: Design Techniques and Analysis
• 定價：55.00 元
• 裝幀：平裝
• 叢書系列：國外計算機科學教材系列

內容簡介

本書是國際著名算法專家李德財教授主編的系列叢書《Lecture Notes Series on Computing》中的一本。本書涵蓋了絕大多數算法設計中的一般技術，在表達每一種技術時，闡述它的套用背景，注意用與其他技術比較的方法說明它的特徵，並提供大量相應實際問題的例子。全書分七部分19章，從算法設計和算法分析的基本概念和方法入手，先後介紹了遞歸技術、分治、動態規劃、貪心算法、圖的遍歷等技術，對NP完全問題進行了基本但清楚的討論。

圖書目錄

第一部分 基本概念和算法導引

第1章 算法分析基本概念

1．1引言

1．2歷史背景

1．3二分搜尋

1．4合併兩個已排序的表

1．5選擇排序

1．6插入排序

1．7自底向上合併排序

1．8時間複雜性

1．9空間複雜性

1．10最優算法

1．11如何估計算法運行時間

1．12最壞情況和平均情況的分析

1．13平攤分析

1．14輸入大小和問題實例

1．15練習

1．16參考注釋

第2章 數學預備知識

2．1集合、關係和函式

2．2證明方法

2．3對數

2．4底函式和頂函式

2．5階乘和二項式係數

2．6鴿巢原理

2．7和式

2．8遞推關係

2．9練習

第3章 數據結構

3．1引言

3．2鍊表

3．3圖

3．4樹

3．5根樹

3．6二叉樹

3．7練習

3．8參考注釋

第4章 堆和不相交集數據結構

4．1引言

4．2堆

4．3不相交集數據結構

4．4練習

4．5參考注釋

第二部分 基於遞歸的技術

第5章 歸納法

5．1引言

5．2兩個簡單的例子

5．3基數排序

5．4整數冪

5．5多項式求值（Horner規則）

5．6生成排列

5．7尋找多數元素

5．8練習

5．9參考注釋

第6章 分治

6．1引言

6．2二分搜尋

6．3合併排序

6．4分治範式

6．5尋找中項和第k小元素

6．6快速排序

6．7大整數乘法

6．8矩陣乘法

6．9最近點對問題

6．10練習

6．11參考注釋

第7章 動態規劃

7．1引言

7．2最長公共子序列問題

7．3矩陣鏈相乘

7．4動態規劃範式

7．5所有點對的最短路徑問題

7．6背包問題

7．7練習

7．8參考注釋

第三部分最先割技術

第8章 貪心算法

8．1引言

8．2最短路徑問題

8．3最小耗費生成樹（Kruskal算法）

8．4最小耗費生成樹(Prim算法)

8．5檔案壓縮

8．6練習

8．7參考注釋

第9章 圖的遍歷

9．1引言

9．2深度優先搜尋

9．3深度優先搜尋的套用

9．4廣度優先搜尋

9．5廣度優先搜尋的套用

9．6練習

9．7參考注釋第四部分問題的複雜性

第10章 NP完全問題

10．1引言

10．2P類

10．3NP類

10．4NP完全問題

10．5co?NP類

10．6NPI類

10．7四種類之間的關係

10．8練習

10．9參考注釋

第11章 計算複雜性引論

11．1引言

11．2計算模型：圖靈機

11．3k帶圖靈機和時間複雜性

11．4離線圖靈機和空間複雜性

11．5帶壓縮和線性增速

11．6複雜性類之間的關係

11．7歸約

11．8完全性

11．9多項式時間層次

11．10練習

11．11參考注釋

第12章 下界

12．1引言

12．2平凡下界

12．3決策樹模型

12．4代數決策樹模型

12．5線性時間歸約

12．6練習

12．7參考注釋第五部分克服困難性

第13章 回溯法

13．1引言

13．23著色問題

13．38皇后問題

13．4一般回溯方法

13．5分支限界法

13．6練習

13．7參考注釋

第14章 隨機算法

14．1引言

14．2Las Vegas和Monte Carlo算法

14．3隨機化快速排序

14．4隨機化的選擇算法

14．5測試串的相等性

14．6模式匹配

14．7隨機取樣

14．8素數性測試

14．9練習

14．10參考注釋

第15章 近似算法

15．1引言

15．2基本定義

15．3差界

15．4相對性能界

15．5多項式近似方案

15．6完全多項式近似方案

15．7練習

15．8參考注釋第六部分域指定問題的疊代改進

第16章 網路流

16．1引言

16．2預備知識

16．3Ford?Fulkerson方法

16．4最大容量增值

16．5最短路徑增值

16．6 Dinic算法

16．7 MPM算法

16．8練習

16．9參考注釋

第17章 匹配

17．1引言

17．2預備知識

17．3網路流方法

17．4二分圖的匈牙利樹方法

17．5一般圖中的最大匹配

17．6二分圖的On2．5算法

17．7練習

17．8參考注釋第七部分計算幾何技術

第18 章幾何掃描

18．1引言

18．2幾何預備知識

18．3計算線段的交點

18．4凸包問題

18．5計算點集的直徑

18．6練習

18．7參考注釋

第19章 Voronoi圖解

19．1引言

19．2最近點Voronoi圖解

19．3Voronoi圖解的套用

19．4最遠點Voronoi圖解

19．5最遠點Voronoi圖解的套用

19．6練習

19．7參考注釋參考文獻