算法设计技巧与分析 - Softcover

新华书店北美网

Softcover

ISBN 10: 7121298341 ISBN 13: 9787121298349

Publisher: 电子工业出版社, 2016

Synopsis

本书是国际著名算法专家李德财教授主编的系列丛书"LectureNotesSeriesonComputing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。本书的组织方式简明扼要，而且包含一般算法书籍中较少涉及的概率算法和近似算法。以算法的设计技术为纲，讲述一个又一个的算法技术，然后分析其算法复杂性。对于想了解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带压缩和线性增速

Edition details

• Publisher: 电子工业出版社
• Publication date: 2016
• Language: Chinese
• ISBN 10: 7121298341
• ISBN 13: 9787121298349
• Binding: Paperback
• Edition number: 1