算法分析导论——计算机科学丛书
|
读过这本书吗？
最近在读
读过
想读
还不熟悉
|
图书城书列：
加入到博客或社交网站：
|
|
我来评论这本书：
内容提要：
本书阐述了用于算法数学分析的主要方法，所涉及的材料来自经典数学课题，包括离散数学、初等实分析、组合数学，以及来自经典的计算机科学课题，包括算法和数据结构，本书内容集中覆盖基础、重要和有趣的算法，前面侧重数学，后面集中讨论算法分析的应用，重点的算法分的的数学方法。每章包含大量习题以及参考文献，使读者可以更深入地理解书中的内容。
本书适合作为高等院校数学、计算机科学以及相关专业的本科生和研究生的教材，也可供相关技术人员参考。 作者简介：
Robert Sedgewick，斯坦福大学博士（导师为Dondld E.Knuth），普林斯顿大学计算机科学系dobe Systems公司董事，曾是Xerox PARC的研究人员，还曾就职于美国国防部防御分析研究所以及INRIA。
目录：
出版者的话
专家指导委员会 译者序 序 前言 记号解释 第1章 算法分析概述 1.1 为什么要对算法进行分析 1.2 计算复杂性 1.3 算法分析的过程 1.4 平均情形分析 1.5 例:快速排序的分析 1.6 渐近逼近 1.7 分布 1.8 概率算法 参考文献 第2章 递归关系 2.1 基本性质 2.2 一阶递归 2.3 非线性一阶递归 2.4 高阶递归 2.5 求解递归的方法 2.6 二分分治递和二进制数 2.7 一般的分治递归 参考文献 第3章 生成函数 3.1 常规生成函数 3.2 指数生成函数 3.3 利用生成函数求解递归 3.4 生成函数求解递归 3.5 利用生成函数进行变换 3.6 关于生成函数的函数方程 3.7 利用OGF求解三数中值Quicksort递归 3.8 利用生成函数的计数 3.9 符号方法 3.10 拉格郎日反演 3.11 概率生成函数 3.12 二元生成函数 3.13 特殊函数 参考文献 第4章 渐近逼近 4.1 有关渐近逼近的记号 4.2 渐近展开式 4.3 渐近展开式的操作 4.4 有限和的渐近逼近 4.5 欧拉-麦克劳林求和 4.6 二元渐近性 4.7 拉普拉斯方法 4.8 算法分析中的“正态”例 4.9 算法分析中的“泊松”例 4.10 生成函数的渐近性 参考文献 第5章 树 5.1 二叉树 5.2 树和森林 5.3 树的性质 5.4 树的算法 5.5 二叉查找树 5.6 Catalan树中的平均路径长 5.7 二叉查找树中的路径长 5.8 随机树的可加参数 5.9 高 5.10 树性质平均情形结果的小结 5.11 树和二叉树的表示 5.12 无序树 5.13 标号树 5.14 其他类型的树 参考文献 第6章 排列 6.1 提列的基本性质 6.2 排列的算法 6.3 排列的表示法 6.4 计数问题 6.5 利用CGF分析排列的性质 6.6 逆序与插入排序 6.7 左向右最小值与选择排序 6.8 圈与原位排列 6.9 极值参数 参考文献 第7章 串与trie树 7.1 串查找 7.2 位串的组合性质 7.3 规则表达式 7.4 有限状态自动机与Knuth-Morris-Pratt算法 7.5 上下文无关语法 7.6 trie树 7.7 trie算法 7.8 trie树的组合性质 7.9 更大的字母表 参考文献 第8章 字与映射 8.1 使用分离链接的散列 8.2 字的基本性质 8.3 生日悖论与赠券收藏家问题 8.4 占有约束与极值参数 8.5 占有分布 8.6 开放定址散列法 8.7 映射 8.8 整数因子分解与映射 参考文献 索引 前言：
本书是对算法数学分析中主要方法的综述。所涉及的材料来自经典的数学课题，包括离散数学、初等实分析、组合数学，以及来自经典的计算机科学课题，包括算法和数据结构。重点在于“平均情形”或“概率”分析，不过，也包括“最坏情形”和“复杂性”分析所需要的基本数学工具。.
我们假设读者熟悉计算机科学和实分析中的基本概念。概括地说，读者应该既能编写程序，又能够证明定理；在其他方面，本书是自包容的。书中还在文献里捉供了丰富的预备性材料。我们计划中的本书姐妹篇将讨论更为先进的方法。这两部著作总共涵盖那些主要的方法和技巧，并提供通向算法分析日益增长的文献的捷径。
本书计划作为算法数学分析初级..
序言：
分析算法的人享有双重的幸福。首先，他们能够体验到优雅数学模式纯粹的美，这种模式存在于优美的计算过程之中。其次，当他们的理论使得其他工作能够做得更快、更经济时，他们能够得到实际的褒奖。.
数学模型始终是所有科学活动至关重要的灵感，尽管它们只是真实世界现象的近似理想化，在计算机内部，这种模型比以前更优美，因为计算机程序创建了人造世界。在这样的世界中，数学模型常常得以精确地使用。我想，这就是为什么当我还是研究生时就沉迷于算法分柝，以及为什么这个课题迄今为止始终是我一生主要工作的原因。..
然而，直到最近，算法分析在很大程度上依然是研究生和研究人员的禁区。它的概念确实不..
|