算法設計與分析

《計算機科學與技術系列教材?算法設計與分析》作為普通高等學校計算機與信息安全專業本科生的教材，根據國內外計算機技術的最新發展，闡述計算機算法的各種設計策略、算法分析和一些經典及應用問題的算法。

全書共11章，第1章介紹算法引論；第2章闡述了排序算法；第3章介紹了分治算法；第4章介紹了圖的搜索算法；第5章介紹了貪心算法；第6章介紹了動態規劃算法；第7章介紹了分支限界法；第8章介紹了並行算法；第9 章介紹了NP-完全問題；第10章介紹了近似算法；第11章介紹了概率算法。 ^[1] 

內容簡介

前言

第1章 算法引論

1.1 算法

1.2 算法描述

1.2.1 算法描述約定

1.2.2 一個簡單問題的求解過程

1.3 算法分析基礎

1.3.1 算法分析的評估體系

1.3.2 算法的時間複雜度

1.3.3 算法的空間複雜度

1.3.4 NP-完全問題

1.4 基本數據結構

1.4.1 棧和隊列

1.4.2 樹

1.4.3 圖

1.5 迭代法

1.5.1 遞推法

1.5.2 倒推法

1.5.3 迭代法解方程

1.6 遞歸和消除遞歸

1.6.1 遞歸

1.6.2 消除遞歸

本章小結

習題1

第2章 排序算法

2.1 排序

2.1.1 排序問題

2.1.2 冒泡排序

2.1.3 交換排序

2.1.4 選擇排序

2.1.5 插入排序

2.2 堆排序

2.2.1 堆

2.2.2 建堆

2.2.3 堆排序算法

2.2.4 堆排序的應用

2.3 快速排序

2.3.1 快速排序的描述

2.3.2 快速排序的性能

2.3.3 隨機化的快速排序算法

2.3.4 快速排序分析

2.4 線性時間排序

2.4.1 排序算法的下界

2.4.2 計數排序

2.4.3 基數排序

2.4.4 桶排序

2.5 中數排序

2.5.1 最大和最小元素

2.5.2 一般選擇問題

本章小結

習題2

第3章 分治法

3.1 一般算法

3.2 二分檢索

3.3 找最大值和最小值

3.4 歸併分類

3.4.1 基本方法

3.4.2 改進的歸併分類算法

3.5 快速分類

3.5.1 快速分類算法

3.5.2 快速分類分析

3.6 選擇問題

3.6.1 選擇問題算法

3.6.2 SELECT2的實現

本章小結

習題3

第4章 圖的搜索算法

4.1 圖的基本概念

4.1.1 圖的定義

4.1.2 圖的基本術語

4.2 圖的檢索與遍歷

4.2.1 廣度優先檢索與遍歷

4.2.2 深度優先檢索與遍歷

4.3 回溯法

4.3.1 回溯法的一般方法

4.3.2 回溯算法的抽象描述

4.3.3 n-皇后問題

4.3.4 子集和數問題

4.3.5 O/l揹包問題

4.3.6 圖的m-着色問題

4.3.7 哈密頓環

4.3.8 連續郵資問題

4.3.9 回溯法的效率估計

本章小結

習題4

第5章 貪心算法

5.1 算法概述

5.1.1 貪心選擇性質

5.1.2 最優子結構性質

5.1.3 活動安排問題

5.2 揹包問題

5.3 帶有限期的作業排序

5.3.1 帶有限期的作業排序算法

5.3.2 改進的帶有限期的作業排序算法

5.4 最優歸併模式

5.5 哈夫曼編碼

5.5.1 前綴碼

5.5.2 哈夫曼編碼

5.6 最小生成樹

5.6.1 Prim算法

5.6.2 Kmskal算法

5.7 單源點最短路徑

本章小結

習題5

第6章 動態規劃算法

6.1 一般方法

6.2 多段圖

6.3 每對結點之間的最短路徑

6.4 最優二分檢索樹

6.5 O/I揹包問題

6.5.1 O/I揹包問題的實例分析

6.5.2 DKP的實現

6.5.3 過程DKNAP的分析

6.6 可靠性設計

6.7 貨郎擔問題

6.8 流水線調度問題

本章小結

習題6

第7章 分支限界法

7.1 一般方法

7.1.1 FIFO和LIFO-檢索

7.1.2 LC-檢索

7.1.3 LC-檢索的抽象化描述

7.1.4 分支限界法解最優化問題

7.2 O/I揹包問題

7.2.1 LC-分支限界求解

7.2.2 PIFO-分支限界求解

7.3 貨郎擔問題

7.4 效率分析

本章小結

習題7

第8章 並行算法

8.1 並行計算機及並行模型

8.1.1 並行計算機

8.1.2 並行計算模型

8.1.3 並行計算機網絡

8.1.4 並行算法的一般術語

8.2 SIMD共享存儲模型的並行算法

8.2.1 播送算法

8.2.2 求和算法

8.2.3 並行k-選擇算法

8.2.4 並行桶排序算法

8.2.5 有序表搜索並行算法

8.3 SIMD互聯網絡模型的並行算法

8.3.1 網孔上的隨機序列搜索算法

8.3.2 樹機上的矩陣和向量乘法

8.3.3 一維線性陣列上的奇偶轉置排序算法

8.3.4 樹機上求最小值算法

8.3.5 樹機上的連通分量算法

8.4 MIMD共享存儲模型的並行算法

8.4.1 異步枚舉排序算法

8.4.2 單源點最短路徑並行算法

8.4.3 最小生成樹並行算法

8.4.4 Gauss-Seidel算法

8.4.5 牛頓求根並行算法

8.5 MIMD異步通信模型的並行算法

8.5.1 快速排序並行算法

8.5.2 二維網孔上的矩陣轉置並行算法

8.5.3 矩陣並行分塊乘法算法

8.5.4 分佈式矩陣求逆的並行算法

8.5.5 分佈式高斯消去並行算法

本章小結

習題8

第9章 NP-完全問題

9.1 計算模型

9.1.1 有限自動機

9.1.2 下推自動機

9.1.3 圖靈機

9.2 P類與NP類問題

9.2.1 多項式時間界(Polynomial time)

9.2.2 P類問題

9.2.3 NP類問題

9.3 NP-完全問題

9.3.1 判定NP-完全問題的關鍵概念

9.3.2 NP-完全性

9.3.3 Cook定理

9.4 典型的NP-完全問題

9.4.1 NP-完全性的證明方法

9.4.2 典型的NP-完全問題

9.4.3 NP-完全問題的計算機實現

本章小結

習題9

第10章 近似算法

10.1 近似算法的性能

10.2 啓發式算法

10.2.1 圖着色問題

10.2.2 旅行商問題

10.3 任務安排的近似算法

10.4 覆蓋問題的近似算法

10.4.1 頂點覆蓋問題的近似算法

10.4.2 集合覆蓋問題的近似算法

10.5 旅行售貨員問題近似算法

10.5.1 具有三角不等式的旅行售貨員問題

10.5.2 一般旅行售貨員問題

10.6 揹包問題

10.7 子集合問題的近似算法

10.7.1 解子集合問題的指數時間算法

10.7.2 子集合問題的完全多項式時間近似格式

本章小結

習題10

第11章 概率算法

11.1 概率算法概述

11.2 偽隨機數

11.3 數值概率算法

11.3.1 用隨機投點法計算1T值

11.3.2 計算定積分

11.3.3 解非線性方程組

11.4 Sherwood算法

11.4.1 線性時間選擇算法

11.4.2 搜索有序表

11.4.3 跳躍表

11.5 Las Vegas算法

11.5.1 n後問題

11.5.2 整數因子分解

11.6 Monte Carlo算法

11.6.1 Monte Carlo算法的基本思想

11.6.2 主元素問題

11.6.3 素數性測試

本章小結

習題11

主要參考文獻