基本信息·出版社：科学出版社 ·页码：268 页 ·出版日期：2003年09月 ·ISBN：9787030117417 ·条形码：9787030117417 ·版本：第1版 ·装帧：平装 ·开 ...
| 商家名称 |
信用等级 |
购买信息 |
订购本书 |
|
|
 |
计算机算法引论:设计与分析技术 |
 |
|
|
计算机算法引论:设计与分析技术 |
|
基本信息·出版社：科学出版社
·页码：268 页
·出版日期：2003年09月
·ISBN：9787030117417
·条形码：9787030117417
·版本：第1版
·装帧：平装
·开本：16
·正文语种：中文
·丛书名：新世纪计算机专业系列教材
·图书品牌：科瀚伟业
内容简介 《计算机算法引论:设计与分析技术》是一本面向计算机、软件工程和网络工程专业及相关专业的本科生(高年级)和研究生教材，根据国内外计算机技术的最新发展，讲述计算机算法的各种设计策略，包括分治技术、贪心技术、动态规划技术、回溯和分支限界技术等；介绍算法分析技术、算法的时间和空间复杂度分析方法，包括最坏情况和平均情况的分析等；讨论各类经典和应用问题的算法，包括排序算法、搜索算法、字符串匹配算法、图论算法、调度算法、组合优化算法、数论算法等。并在计算复杂性理论的基础上，引入近似算法、概率算法等最新内容。
编辑推荐 《计算机算法引论:设计与分析技术》由科学出版社出版。
目录 1 绪论
1.1 交通信号灯问题
1.1.1 问题
1.1.2 实例
1.1.3 图着色问题
1.1.4 算法设计讨论
1.1.5 讨论
1.2 什么是算法
1.2.1 算法
1.2.2 算法与问题
1.2.3 算法与程序
1.3 算法的评估
1.3.1 正确性
1.3.2 时间代价
1.3.3 空间代价
1.3.4 最优性
1.4 算法理论的基本概念
1.4.1 摹本操作
1.4.2 问题实例长度
1.4.3 复杂度的渐进性质
1.4.4 最坏情形和最好情形
1.4.5 平均情形和算法的期望复杂度
1.4.6 复杂度函数的表示
1.5 算法的研究与Moore定律
1.6 MAXMIN问题
1.6.1 平凡算法
1.6.2 改进一
1.6.3 改进二
1.6.4 改进三
1.6.5 讨论
习题1
2 排序算法与算法的分析技术
2.1 排序问题
2.2O (n)阶的排序算法
2.2.1 选择排序
2.2.2 插入排序
2.2.3 起泡排序
2.3 基于相邻元比较的排序算法和希尔排序
2.3.1 插入排序的最优性
2.3.2 希尔排序
2.4 (nlogn)阶的排序算法
2.4.1 快速排序算法
2.4.2 合并排序算法
2.4.3 堆排序算法
2.5 比较排序算法的时间复杂度下界
2.5.1 判定树模型
2.5.2 最坏情形
2.5.3 平均情形
2.6 排序算法的有关研究
习题2
3 分治技术
3.1 分治策略的思想
3.2 大整数乘法
3.3 矩阵相乘的Strassen算法
3.3.1 问题
3.3.2 分治
3.3.3 Strassen的分治方法
3.3.4 Strassen算法的描述
3.3.5 讨论
3.4 选择问题的线性算法
3.4.1 问题
3.4.2 简单算法
3.4.3 O(n)阶选择算法的思路
3.4.4 选择算法
3.4.5 选择算法Select的分析
3.4.6 讨论
习题3
4 数据集合上的搜索算法
4.1 动态数据集与抽象数据类型
4.2 二叉搜索树
4.2.1 二叉搜索树
4.2.2 查询的实现
4.2.3 插入与删除操作
4.3 随机二叉搜索树
4.4 红黑树
4.4.1 红黑树的性质
4.4.2 RB树的插入与删除算法
4.4.3 关于RB树的几点讨论
4.5 2-3-4树
4.5.1 2-3-4树及其实例
4.5.2 2-3-4树上的查询操作算法
4.5.3 2-3-4树的构造过程
4.5.4 2-3-4树的性能分析
4.5.5 有关2-3-4树的几点讨论
4.6 Hash技术
4.6.1 Hash算法的基本思想与一般模型
4.6 ,2Hash函数的设计
4.6.3 解决冲突的策略
4.6.4 Hash算法的优劣分析
4.6.5 Hash技术的几种新发展
习题4
5 贪心技术
5.1 贪心策略的思想
5.1.1 付款问题
5.1.2 铺砖问题
5.1.3 贪心算法的基本思想
5.2 背包问题
5.3 Huffman编码
5.4 多机调度问题的近似解法
5.5 单源最短路径的Dijkstra算法
习题5
6 字符串匹配
6.1 字符串匹配问题
6.2 KMP算法
6.2.1 KMP算法的思路
6.2.2 KMP算法
6.2.3 KMP算法的正确性
6.2.4 KMP算法的分析
6.2.5 有关KMP算法的讨论
6.3 BM算法
6.3.1 BM算法的两种处理思路
6.3.2 BM算法的时间复杂度分析
6.3.3 对BM算法的进一步讨论
6.4 RK算法
6.4.1 RK算法的思路
6.4.2 RK算法的描述
6.4.3 RK算法的分析与讨论
习题6
7 动态规划
7.1 动态规划的基本原理
7.1.1 Fibonacci数的计算
7.1.2 矩阵连乘的顺序问题
7.1.3 动态规划算法的基本条件
7.2 最优二分搜索树
7.2.1 最优二分搜索树问题
7.2.2 动态规划算法的思路
7.2.3 OBST算法
7.2.4 OBST算法的复杂度分析
7.2.5 讨论
7.3 近似串匹配问题
7.3.1 近似串匹配问题的描述
7.3.2 动态规划算法的思路
7.3.3 动态规划算法
7.3.4 算法的复杂度分析与实例
7.3.5 讨论
习题7
8 回溯与分枝限界技术
8.1 回溯和分枝限界的基本思想
8.1.1 八皇后问题
8.1.2 子集合问题
8.1.3 回溯与分枝限界算法的基本思路
8.2 0-1背包问题的回溯算法
8.2.1 0-1背包问题
8.2.2 回溯策略的解题思路
8.2.3 0-1背包问题的回溯算法
8.2.4 算法的复杂度分析
8.2.5 一个运行实例
8.3 无向图的团集问题
8.3.1 团集问题
8.3.2 解题思路
8.3.3 团集问题的回溯算法
8.3.4 算法MaxClique()的分析与讨论
8.4 旅行商问题的回溯算法
8.4.1 旅行商问题
8.4.2 旅行商问题的回溯算法
8.5 分枝限界算法思路的特征
8.5.1 0-1背包问题的分枝限界策略
8.5.2 分枝限界算法的优点和缺点
8.5.3 用分枝限界算法解旅行商问题的一个实例
习题8
9 计算机难解问题与NP-完全性问题
9.1 一些难解问题
9.1.1 图着色问题
9.1.2 0-1背包问题
9.1.3 子集合问题
9.1.4 装箱问题
9.1.5 作业调度问题
9.1.6 可满足性问题
9.1.7 图的团集问题
9.1.8 Hamiltonian回路问题与Hamiltonian路径问题
9.1.9 旅行商问题
9.2 多项式界与P类问题
9.2.1 多项式(时间)界
9.2.2 问题求解与判定问题
9.2.3 P类
9.3 不确定算法与NP类
9.3.1 问题求解与验证
9.3.2 非确定算法与NP类
9.4 问题的多项式归约和NP-完全性
9.4.1 多项式归约
9.4.2 NP-完全性
9.4.3 Cook定理
9.5 与NP-完全问题相关的理论问题与实际问题
9.5.1 理论可计算性与实际可计算性
9.5.2 “P=NP”问题
9.5.3 NP-完全问题的计算处理
习题9
10 近似算法
10.1 近似算法的思想与基本概念
10.1.1 顶点覆盖问题的近似算法
10.1.2 顶点覆盖问题的近似算法aVertexCover()
10.1.3 近似算法aVertexCover()的复杂度分析
10.1.4 算法aVertexCover()的近似度分析
10.2 装箱问题的近似算法
10.2.1 装箱问题
10.2.2 装箱问题的近似策略的讨论
10.2.3 装箱问题的FF策略近似算法
10.2.4 bpFFD算法的复杂度
10.2.5 近似算法bqFFD()解的最优性分析
10.2.6 讨论
10.3 旅行商问题的近似算法
10.3.1 最近邻点策略
10.3.2 最短链接策略
10.3.3 满足三角不等式的旅行商问题
10.3.4 几点讨论
习题10
11 数论算法及其在计算机安全系统中的应用
11.1 RSA公钥密码系统
11.1.1 数据加密的历史及现状
11.1.2 公钥密码系统
11.1.3 RSA公钥密码系统
11.1.4 公钥密码系统的数字签名功能
11.1.5 公钥密码系统与计算机网络安全
11.1.6 RSA公钥密码系统的主要技术问题
11.2 判素问题的概率算法
11.2.1 判素问题
11.2.2 输入长度和算术计算的时间代价
11.2.3 基于数论的素数判别概率算法
11.3 大素数的获得和Miller-Rabin算法的应用
11.3.1 素数的稠密性
11.3.2 Miller-Rabin测试算法的时间代价
11.3.3 Miller-Rabin算法判定素数的正确性
11.4 加密解密算法
11.5 大整数分解与RSA系统的安全性
11.5.1 整数的因子分解问题
11.5.2 Pollard的rho启发式算法
习题11
附录A 递归方程(递归不等式)的求解判定方法
附录B 实际性能最佳的排序算法的设计
附录C 计算模型
附录D Cook定理
附录E 若干数论知识
附录F 算法索引
主要参考文献
……
序言 20年来，计算机学科的发展日新月异，促使现代科学在各个领域突飞猛进。目前、计算机科学技术已应用在实时控制、信息处理、通信传输、企事业管理等领域，成为人们工作、学习、生活必不可少的工具。计算机技术的发展瞬息万变，具有以下三方面特点：
（一）传统的工、理、文、医、商、农在计算机的应用方面都有着各自专业的需要，例如，经济、艺术、法律、管理、医学等各种学科都需要依赖于计算机技术的应用。除了各自领域的专业实践外，应用计算机已是各个专业提高效率、发挥潜能、促进发展的必不可少的手段。因此现在很难用传统的工、理、文、医、商、农等去界定学科的分类。
（二）计算机网络改变了计算机通信的时空距离。计算机应用的发展是与计算机网络的发展紧密相连的。从最初的局域网（LAN）到广域网（WAN），以至用一种新的方法将LAN和WAN互联起来，即成为网际网（Internetwork）。这种网际网的实验原型Internetwork，通常缩写为Internet。计算机网格将计算机互连起来，从而使计算机之间可以交换信息，而且这种信息交换可以在几分钟内就影响到世界各地。计算机网络的发展，带动了计算机学科在很多领域的拓展。
（三）现代计算机学科向综合性发展。计算技术发展伊始，每种学科均以软硬件分类，泾渭分明。但自网络发展以来，Internet软件中的两部分变得特别重要和特别具有开创性，即网际协议（Internet Protocol，简称IP）和传输控制协议（Transmisston Control Protocol，简称TCP）。这些协议是必不可少的软件系统。但是在网络系统中，网络的互连必须依靠路由器、服务器、接口插座、调制解调器等硬件设施，所以计算机网络很难归结为软件或硬件的单一体系。
随着计算机技术的发展，计算机与通讯、视频、声音等密不可分；随着多媒体的发展和应用，计算机科学已经愈来愈成为与数字传输、视频、声、光、电等综合的学科。
尽管计算机技术的发展如此神速、新异，但像一切新学科的发展一样，计算机教育水平仍滞后于计算机技术的发展。为了适应计算机教学改革的需要，我们国内部分重点院校的教授、学者，在科学出版社的积极鼓励和支持下，成立了新世纪计算机专业教材编委会。自2000年10月以来，我们群策群力，多次探讨了当前教育与技术进展之间的差距，并且仔细研讨了美国ACM／IEEE-CS公布的Computing CC4rr／Cula 2001的优点与不足，结合我国计算机教育的实际情况，提出了编著一套适用于计算机本科专业的励精图治的教材计划。这套教材的选题、定位乃至作者的遴选，都得到了国内很多著名教授和学者的认同，并且有很多选题都争取到了一些著名教授亲自参与编写。这套教材立意着重基础，反映导向，注重实践。
文摘 插图：
Hash方法这种独特的按内容寻址的检索方式是一种高级的“联想”式存储与检索技术，可以肯定，在这个领域的研究今后还会有广阔的前景。在应用领域，其受欢迎的根本原因是期望的时间代价为。（1）阶，随着人们要处理的数据量的不断增大，这种与数据集规模无关的检索算法必然成为优先选择。
当然，}lash技术发展到今天，还有若干不足之处，也许这正是今后研究与发展的出发点。
（1）按内容寻址的方式决定了它是把数据“散列”到Hash表中，因此，它不适用于涉及数据内容之间关系的查询。例如，求最大、最小元，删除最小元，后继，前导等。这些操作在二叉搜索树上可在O（logn）时间内完成，用Hash技术则根本无法实现。一些区域查询，如求关键字key值在某一范围内的一组数据，也无法用Hash技术实现。这个缺点可以说是卜tash技术固有的，是为获得高速检索性能所不得不付出的代价.-
（2）Hash算法的最坏情形时间代价为O（n）阶，这一点使其不能在诸如防空系统、空中交通调度系统等“紧急”系统中采用，因为即使是百万次正常运行之后出现一次最坏情形，也会因系统反应过慢而造成重大事故。这一缺点对于动态数据集上的算法来讲是很难克服的，但有关静态字典上进行的完备正lash函数的研究，正是要使操作的时间代价在最坏情形下也是O（1）阶。
（3）前文对Hash算法的性能分析过程中，所有的分析结果（如开地址法插入的时间代价为l／（1-a））都是在“实际关键字集合S是全域U的一个随机子集”等条件下得到的。如果全集U中的关键字不是等可能性地出现在Hash表中，这种情况在实际问题中是经常遇到的，例如，关键字为程序中的标识符名，有些名称如m、n、ml、m2、m3等，出现的概率远远多于其他名称，在这种情形下，期望性能可能变差。对此，也有一些方法予以解决，如泛Hash（Universal Hashing）方法就是努力解决这一问题过程中产生的成果之一。
（4）定理4、6、4.7指出，Hash算法的性能与负载因子。的值密切相关。在数据集不断增加时，o值逐渐增大，并接近于l，会使系统性能明显下降，即使数据总数n尚未超过存储空间的大小m。如o：n／m>0.9或>0.95时，不得不扩大Hash区，即所谓空间倍增（Array Doubling），需要把数据集中的所有数据按照新的Hash函数重新转存入新的Hash区，这一工作代价很大。
