适读人群：本书结构简明，内容丰富，适合于作为计算机学科以及相关学科算法课程的教材和参考书，尤其适宜于学过数据结构和离散数学课程之后的算法课教材。同时也可作为从事算法研究的一本好的入门书。
　　本书的组织方式简明扼要，而且包含一般算法书籍中较少涉及的概率算法和近似算法。
　　以算法的设计技术为纲，讲述一个又一个的算法技术，然后分析其算法复杂性。
　　对于想了解NP完全问题基本概念的读者，本书的篇幅给出了基本但又清楚的描述。

内容简介

　　本书是国际著名算法专家李德财教授主编的系列丛书"Lecture Notes Series on Computing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。

作者简介

　　朱洪，复旦大学计算机科学系教授，中国计算机学会理论专业委员会常委，中国人工智能学会离散数学专委会主任，中国密码学会理事。 M. H. Alsuwaiyel在沙特阿拉伯的Kin g Fahd University of Petroleum&Minerals;（KFUPM，皇家法哈德石油矿业大学）完成大学学业，在南加州（USC）大学获得计算机科学硕士和博士学位。作者曾任KFUPM的计算机科学系主任、工程与计算机学院院长。他在沙特阿拉伯有广泛的学术影响，是政府（包括内务部和国防部在内）的高级顾问。

第一部分基本概念和算法导引
第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参考注释参考文献

前言/序言

　　序言
　　多年来，我一直在寻找一本适合国内计算机专业学生用的有关算法方面的国外教材。尽管在国内引进了一些不错的国外教材，但总有篇幅过多，内容不够新颖或数据结构内容夹杂其中等等这样那样的不甚满意之处。
　　不久前我有幸看到世界科学图书出版社出版的由M．H．Alsuwaiyel撰写的“Algorithms Design Techniques and Analysis”，它是以国际著名算法专家，我国台湾出身的李德财教授所主编的系列从书“LectureNotesSeriesonComputing”中的一本。虽然此书不是美国的大学教材，而是沙特阿拉伯的大学计算机系教材，但是我很快就被该书的组织简明、概括，且包含当前市面上算法较少涉及的概率算法和近似算法的基本内容所吸引。它是一本适合本科生学习算法的好书。
　　该书涉及数据结构的部分较少，即使有一些，描述上也很快与算法中比较复杂的集合查找和合并运算等相结合，让读者不会感到和已经学过的数据结构重复。这比较适合国内大学计算机系中数据结构和算法分成两门课开设的实际状况。
　　对于想了解NP完全问题基本概念的读者，本书的篇幅给了他们基本但又清楚的描述。本书还包括计算几何一章，其取材也是适中的。
　　概率算法和近似算法是近20年来算法研究迅猛发展的领域，本书给予了足够的重视，这是本书特色之一，是我向国内学生特别推荐的主要原因。
　　本书的另一特色是以算法的设计技术为纲，讲述一个又一个的算法技术，然后分析其算法复杂性。
　　我希望该书(简体中文版)的出版能弥补短期内暂时无合适中文算法教材的空白。诚挚地向国内的广大算法老师推荐采用本书作为教材。
　　本书由上海应用技术学院的吴伟昶老师在算法界的老前辈方世昌教授的协助下翻译。吴伟昶多年来对算法很专研，在翻译过程中对原著的少量错误进行了纠正。方世昌教授是算法名著“The Design and Analysis of Computer Algorithms by Aho，Hopcroft and Ullman(1974)”我国最早译本之一的译者，虽然该书至今还没有理想的译本正式出版，但是方的译本在20世纪80年代的我国高校计算机系师生中广泛流传，对算法在我国的普及做出了不可磨灭的贡献。我坚信本译本的出版将对我国高校计算机系的算法教学起到很大的推动作用。
　　朱洪
　　复旦大学
　　译者序
　　算法设计与分析是计算机科学技术中处于核心地位的一门专业基础课，越来越受到重视。本书系统地介绍了一些常用的、经典的算法设计技术，并给出了详细的复杂性分析。全书分七部分19章，内容含有递归技术、分治、动态规划、贪心算法、图的遍历等，同时也包括了近年来发展迅速的近似算法、概率算法和几何算法，对于NP完全问题等复杂性理论的基础内容，也做了基本的、清楚的描述。本书结构合理，选材适度，陈述简明易读，每章附有适量的各种类型练习，没有过难或研讨性题目，适合于教学和自学。出版后已被许多大学选做本科和研究生的教材及参考书。
　　多年来，我一直在寻找一本适合国内计算机专业学生用的有关算法方面的国外教材。尽管在国内引进了一些不错的国外教材，但总有篇幅过多，内容不够新颖或数据结构内容夹杂其中等等这样那样的不甚满意之处。
　　不久前我有幸看到世界科学图书出版社出版的由M．H．Alsuwaiyel撰写的“Algorithms Design Techniques and Analysis”，它是以国际著名算法专家，我国台湾出身的李德财教授所主编的系列从书“LectureNotesSeriesonComputing”中的一本。虽然此书不是美国的大学教材，而是沙特阿拉伯的大学计算机系教材，但是我很快就被该书的组织简明、概括，且包含当前市面上算法较少涉及的概率算法和近似算法的基本内容所吸引。它是一本适合本科生学习算法的好书。
　　该书涉及数据结构的部分较少，即使有一些，描述上也很快与算法中比较复杂的集合查找和合并运算等相结合，让读者不会感到和已经学过的数据结构重复。这比较适合国内大学计算机系中数据结构和算法分成两门课开设的实际状况。
　　对于想了解NP完全问题基本概念的读者，本书的篇幅给了他们基本但又清楚的描述。本书还包括计算几何一章，其取材也是适中的。
　　概率算法和近似算法是近20年来算法研究迅猛发展的领域，本书给予了足够的重视，这是本书特色之一，是我向国内学生特别推荐的主要原因。
　　本书的另一特色是以算法的设计技术为纲，讲述一个又一个的算法技术，然后分析其算法复杂性。
　　我希望该书(简体中文版)的出版能弥补短期内暂时无合适中文算法教材的空白。诚挚地向国内的广大算法老师推荐采用本书作为教材。
　　本书由上海应用技术学院的吴伟昶老师在算法界的老前辈方世昌教授的协助下翻译。吴伟昶多年来对算法很专研，在翻译过程中对原著的少量错误进行了纠正。方世昌教授是算法名著“The Design and Analysis of Computer Algorithms by Aho，Hopcroft and Ullman(1974)”我国最早译本之一的译者，虽然该书至今还没有理想的译本正式出版，但是方的译本在20世纪80年代的我国高校计算机系师生中广泛流传，对算法在我国的普及做出了不可磨灭的贡献。我坚信本译本的出版将对我国高校计算机系的算法教学起到很大的推动作用。

算法设计技巧与分析 [Algorithms Design Techniques and Analysis] 下载 mobi epub pdf txt

算法设计技巧与分析 [Algorithms Design Techniques and Analysis] pdf epub mobi txt 下载