应用组合数学(原书第2版)
点击看大图基本信息
- 原书名： Applied Combinatorics
- 原出版社： Prentice Hall
- 作者： (美)Fred S.Roberts Barry Tesman [作译者介绍]
- 译者： 冯速
- 丛书名： 华章数学译丛
- 出版社：机械工业出版社
- ISBN：9787111209348
- 上架时间：2007-5-28
- 出版日期：2007 年5月
- 开本：16开
- 页码：570
- 版次：2-1
- 所属分类：
数学 > 文科、经管、金融、工程数学 > 应用数学
教材 > 研究生/本科/专科教材 > 理学 > 数学
推荐阅读
内容简介回到顶部↑
本书介绍组合数学的基本知识，以及这些知识在计算机科学、生物学、医学、遗传学等各个领域的实际应用。全书分为四个部分：第一部分介绍组合数学的基本工具，第二部分介绍计数问题，第三部分讲述组合数学求解中的存在问题，第四部分讨论优化问题。
本书布局精巧、内容翔实，讨论深入浅出，简明扼要，可作为高等院校数学专业和计算机科学专业“组合数学”课程的教材，也可以作为相关科研人员的参考书。
本书布局精巧、内容翔实，讨论深入浅出，简明扼要，可作为高等院校数学专业和计算机科学专业“组合数学”课程的教材，也可以作为相关科研人员的参考书。
目录回到顶部↑
译者序
前言
记号
第1章 什么是组合数学
1.1 组合数学的三个问题
1.2 组合数学的历史和应用
练习
参考文献
第一部分 组合数学的基本工具
第2章 基本计数规则
2.1 乘法规则
2.2 加法规则
2.3 排列
2.4 计算的复杂度
2.5 r排列
2.6 子集
2.7 r组合
2.8 概率
2.9 放回取样
2.10 分装问题
前言
记号
第1章 什么是组合数学
1.1 组合数学的三个问题
1.2 组合数学的历史和应用
练习
参考文献
第一部分 组合数学的基本工具
第2章 基本计数规则
2.1 乘法规则
2.2 加法规则
2.3 排列
2.4 计算的复杂度
2.5 r排列
2.6 子集
2.7 r组合
2.8 概率
2.9 放回取样
2.10 分装问题
译者序回到顶部↑
本书以组合数学的实际应用为背景，非常全面地讲述了组合数学的基本知识和基本问题，以及这些知识在计算机科学、密码学、政治经济学、生物学、医学、遗传学等各个领域的实际应用． .
本书分四个部分．第一部分讲述组合数学的基本工具，而其余三个部分分别讲述组合数学的三个基本问题：计数问题、存在问题和优化问题．各章以实际应用为例，引出该章的主要课题，然后对前后关联的知识点逐步展开讨论，在讨论中又提出更多的示例，力图让读者掌握所讲述的思想并灵活运用相关的方法．另外，各节给出很多相关的练习，使读者能够检验所学知识，同时引入新概念和新应用，为读者灵活运用书中的组合技术提供素材．因此，本书的一大特点就是包含大量的实际例子及练习，其中许多例子和练习都来自于最新的文献．这些例子和练习前后呼应、反复出现，形成若干系列，可以看出经过了作者的精心筛选．
本书的另一个特点是强调算法．当今计算机的快速发展和各种算法的开发是促进组合数学快速发展和广泛应用的主要动力之一，而组合数学的快速发展同样促进了计算机理论的发展及计算机在各个领域的广泛应用．所以，组合数学与计算机科学之间已经形成了密不可分的关系，组合数学是计算机科学——特别是计算机算法的基础．现在，组合数学已经成为多数大学计算机专业研究生的必修课程． ..
本书的第三个特点是，不仅给出了绝大多数结果的严密证明，而且不拘泥于通常教科书所用的概念和结果，对一些概念和结果进行了扩展．
本书可以作为计算机专业和数学专业高年级本科生或研究生的教材，也可以作为相关科研人员的参考书．不满足于“离散数学”课程所学内容的学生可以通过本书继续自学，而本书各章后的参考文献则为希望继续深入学习、了解科研前沿及应用前沿的读者提供了参考．
在翻译本书时，我们遇到了许多不同专业的术语．我们力图使术语简单、易懂，一些术语没有采用数学专业的说法，而是采用计算机科学专业的说法．对于中文特别难以反映其本质内容的术语，我们采取了不译的做法．由于书中涉及应用的多样性和译者的水平所限，难免有不当之处，敬请读者批评指正． ...
译 者
于北京师范大学
本书分四个部分．第一部分讲述组合数学的基本工具，而其余三个部分分别讲述组合数学的三个基本问题：计数问题、存在问题和优化问题．各章以实际应用为例，引出该章的主要课题，然后对前后关联的知识点逐步展开讨论，在讨论中又提出更多的示例，力图让读者掌握所讲述的思想并灵活运用相关的方法．另外，各节给出很多相关的练习，使读者能够检验所学知识，同时引入新概念和新应用，为读者灵活运用书中的组合技术提供素材．因此，本书的一大特点就是包含大量的实际例子及练习，其中许多例子和练习都来自于最新的文献．这些例子和练习前后呼应、反复出现，形成若干系列，可以看出经过了作者的精心筛选．
本书的另一个特点是强调算法．当今计算机的快速发展和各种算法的开发是促进组合数学快速发展和广泛应用的主要动力之一，而组合数学的快速发展同样促进了计算机理论的发展及计算机在各个领域的广泛应用．所以，组合数学与计算机科学之间已经形成了密不可分的关系，组合数学是计算机科学——特别是计算机算法的基础．现在，组合数学已经成为多数大学计算机专业研究生的必修课程． ..
本书的第三个特点是，不仅给出了绝大多数结果的严密证明，而且不拘泥于通常教科书所用的概念和结果，对一些概念和结果进行了扩展．
本书可以作为计算机专业和数学专业高年级本科生或研究生的教材，也可以作为相关科研人员的参考书．不满足于“离散数学”课程所学内容的学生可以通过本书继续自学，而本书各章后的参考文献则为希望继续深入学习、了解科研前沿及应用前沿的读者提供了参考．
在翻译本书时，我们遇到了许多不同专业的术语．我们力图使术语简单、易懂，一些术语没有采用数学专业的说法，而是采用计算机科学专业的说法．对于中文特别难以反映其本质内容的术语，我们采取了不译的做法．由于书中涉及应用的多样性和译者的水平所限，难免有不当之处，敬请读者批评指正． ...
译 者
于北京师范大学
前言回到顶部↑
本书第2版的面世距初版时间已有20年之久．新版进行了大幅度修订，加入200多页新材料，许多章节有了重大变更，并增加了大量新的例子与练习．但是，本书的宗旨没有改变．下面三段话引自第1版前言，这些文字至今仍是适用的． .
当代数学发展最快的领域可能就是组合数学了． 它之所以发展快速，一个主要原因是它在计算机科学、通信、交通运输、遗传学、实验设计和排程等方面的广泛应用．因此，本书将从应用的观点向读者介绍组合数学的工具．
组合数学的发展是同计算机的发展齐头并进的． 当今的高速计算机使得各领域中实际组合问题的求解成为可能，而这些问题在不久以前还是无法解决的． 这种情况增强了研究组合问题求解方法的重要性． 与此同时，计算机科学的发展本身又带来了大量具有挑战性的组合问题． 因此，我们很难把组合数学和计算技术割裂开来．读者将会看到本书中对计算技术的强调，我们会经常采用计算机科学中的大量应用实例，频繁讨论算法，等等． 另一方面，我们认为：组合数学在大量学科中有着广阔的应用前景，我们强调的重点是应用的多样性，而不限于某一方面．
本书选取的数学题材中，许多是快速发展的组合数学教科书中相对而言称为标准的内容． 另一部分题材的选择，或者来自当前的研究文献，或者由于其学科应用价值而被选用． 我们相信，本书在对应用的广泛讨论方面是与众不同的．书中有若干完整的小节专门介绍这样的应用，例如开关函数，使用酶揭示未知的RNA链，信息检索中的搜索与排序，错误校正码的构造，化学成分的计算，选举中的势力预测以及斐波那契数的应用． 还有一些小节介绍与卷积有关的递推的应用、欧拉链的应用以及生成函数的应用等，这在许多教材中是没有的．
第2版中的新内容
本书之所以受到欢迎，大部分原因在于它引用了最新文献和各种实际应用．推动着组合数学发展的应用仍然在不断扩展，尤其是在自然科学和社会科学中．在第2版中，许多新应用更是来自计算机科学和生物学．在增加应用题材的同时，我们也增加了某些新的主题，删去了一些特殊的内容，改变了组织结构，并对例子、练习和参考文献也做了改进与更新．
下面说明第2版中所做的某些主要修改．
第1章：增加了有关列表着色的新材料，扩充了对州立法会议日程安排的讨论．列表着色问题在书中许多地方还会出现．
第2章：在第1版中，2．16节仅限于讨论生成排列的算法方法，第2版现在补充了大量材料，并分成几个小节．2．18节介绍“好算法”的概念和NP完全问题，进行了大幅度改写和更新．此外，还添加了有关“鸽巢原理”的新章节．讨论拉姆齐理论的小节是由第1版8．1节的材料和8．2节的部分材料合成的．另外，我们还增加了讨论排列之间的倒位距离和进化论生物学中的突变问题的内容—
第3章：在3．3节中增加了图着色问题的一小节，着重讨论图着色的扩展，例如多重着色和T着色．这类着色问题是由现实应用引起的，例如移动电话问题、交通灯切换和信道分配．此外，在本章中我们还增加了物种进化树重构的内容．对于第1版第8章有关拉姆齐理论的许多材料中没有写进第2章的部分，已改写为新的一节．
第4章：这一章是全新的． 内容包括二元关系的定义及其与有向图的联系，用有向图和关系引入的顺序以及对线性序和弱序的处理，偏序、线性扩展和维数，链和可比较图，格，布尔代数，开关函数和门网络．该章紧密结合应用来讨论，其中涉及信息论、效用理论、搜索与排序以及诸如开关函数这样一些较早的应用．这一章包含的某些应用在组合数学的文献中没有受到广泛关注，如优先选择、搜索引擎、杂交顺序和心理物理量表法等．基于该章中的概念的许多例子也出现在以后各章中．第4章涉及的范围可以一直延续到第11章之后．
第5章：在第1版中这是第4章．前面几章引入的许多新概念与例子在这一章又重新出现，例如第4章的弱序和第3章的列表着色．
第6章：这是第1版中的第5章．该章增加了有关DNA序列对位的新材料，作为排列的“转置平均值”的内容．
第7章：这是第1版中的第6章．该章增加了有关密码技术和整数因子分解的新素材(在本书后面还要提到)．
第1版原第8章：这一章已经被删去，其中的重要材料加进第2章，而其余的材料已纳入书中其他章节．
第8章：这是第l版中的第7章．该章中新增加了一些例子，这些例子以第4章中的概念(如弱序)为基础．同时，该章中还增加了一小节，讨论图的自同构，并在该章多处地方提到．
第9章：该章增加了讨论正交阵列和密码技术的一节，内容涉及识别码和秘密分享．与此同时，该章还讨论了模算术与RSA密码系统之间的联系，以及秘密分享应用的一个可求解设计的内容．此外，该章关于“组群测试”的新内容涉及几个应用，其中包括次品鉴别、疾病筛查、基因组图谱测绘和卫星通信．
第10章：有关“合意解码”的小节是新增的，这同寻找分子序列中的蛋白质有关，同时加入了涉及光盘错误校正码的内容．关于“判读”DNA产生蛋白质的材料也是新增加的．
第11章：在11．2节中增加了讨论单行线问题的几小节．这些新的内容涉及有关广场取向和栅格的最新结果，分别反映不同城市类型的需要．该章还增加了关于测试巨大图的连通性问题的内容，这类问题出现在与电信业务量和网上数据有关的最新应用中．此外，该章还包括关于DNA杂交顺序的内容．
第12章；这一章用若干新的例子解释概念，包括天花疫苗接种、音响系统和石油钻井的例子．我们写了新的一节讨论稳定婚姻问题及其许多最新的应用，包括医院实习医生分配等．第1版第13章中有关最大权匹配的内容已移至该章中．
当代数学发展最快的领域可能就是组合数学了． 它之所以发展快速，一个主要原因是它在计算机科学、通信、交通运输、遗传学、实验设计和排程等方面的广泛应用．因此，本书将从应用的观点向读者介绍组合数学的工具．
组合数学的发展是同计算机的发展齐头并进的． 当今的高速计算机使得各领域中实际组合问题的求解成为可能，而这些问题在不久以前还是无法解决的． 这种情况增强了研究组合问题求解方法的重要性． 与此同时，计算机科学的发展本身又带来了大量具有挑战性的组合问题． 因此，我们很难把组合数学和计算技术割裂开来．读者将会看到本书中对计算技术的强调，我们会经常采用计算机科学中的大量应用实例，频繁讨论算法，等等． 另一方面，我们认为：组合数学在大量学科中有着广阔的应用前景，我们强调的重点是应用的多样性，而不限于某一方面．
本书选取的数学题材中，许多是快速发展的组合数学教科书中相对而言称为标准的内容． 另一部分题材的选择，或者来自当前的研究文献，或者由于其学科应用价值而被选用． 我们相信，本书在对应用的广泛讨论方面是与众不同的．书中有若干完整的小节专门介绍这样的应用，例如开关函数，使用酶揭示未知的RNA链，信息检索中的搜索与排序，错误校正码的构造，化学成分的计算，选举中的势力预测以及斐波那契数的应用． 还有一些小节介绍与卷积有关的递推的应用、欧拉链的应用以及生成函数的应用等，这在许多教材中是没有的．
第2版中的新内容
本书之所以受到欢迎，大部分原因在于它引用了最新文献和各种实际应用．推动着组合数学发展的应用仍然在不断扩展，尤其是在自然科学和社会科学中．在第2版中，许多新应用更是来自计算机科学和生物学．在增加应用题材的同时，我们也增加了某些新的主题，删去了一些特殊的内容，改变了组织结构，并对例子、练习和参考文献也做了改进与更新．
下面说明第2版中所做的某些主要修改．
第1章：增加了有关列表着色的新材料，扩充了对州立法会议日程安排的讨论．列表着色问题在书中许多地方还会出现．
第2章：在第1版中，2．16节仅限于讨论生成排列的算法方法，第2版现在补充了大量材料，并分成几个小节．2．18节介绍“好算法”的概念和NP完全问题，进行了大幅度改写和更新．此外，还添加了有关“鸽巢原理”的新章节．讨论拉姆齐理论的小节是由第1版8．1节的材料和8．2节的部分材料合成的．另外，我们还增加了讨论排列之间的倒位距离和进化论生物学中的突变问题的内容—
第3章：在3．3节中增加了图着色问题的一小节，着重讨论图着色的扩展，例如多重着色和T着色．这类着色问题是由现实应用引起的，例如移动电话问题、交通灯切换和信道分配．此外，在本章中我们还增加了物种进化树重构的内容．对于第1版第8章有关拉姆齐理论的许多材料中没有写进第2章的部分，已改写为新的一节．
第4章：这一章是全新的． 内容包括二元关系的定义及其与有向图的联系，用有向图和关系引入的顺序以及对线性序和弱序的处理，偏序、线性扩展和维数，链和可比较图，格，布尔代数，开关函数和门网络．该章紧密结合应用来讨论，其中涉及信息论、效用理论、搜索与排序以及诸如开关函数这样一些较早的应用．这一章包含的某些应用在组合数学的文献中没有受到广泛关注，如优先选择、搜索引擎、杂交顺序和心理物理量表法等．基于该章中的概念的许多例子也出现在以后各章中．第4章涉及的范围可以一直延续到第11章之后．
第5章：在第1版中这是第4章．前面几章引入的许多新概念与例子在这一章又重新出现，例如第4章的弱序和第3章的列表着色．
第6章：这是第1版中的第5章．该章增加了有关DNA序列对位的新材料，作为排列的“转置平均值”的内容．
第7章：这是第1版中的第6章．该章增加了有关密码技术和整数因子分解的新素材(在本书后面还要提到)．
第1版原第8章：这一章已经被删去，其中的重要材料加进第2章，而其余的材料已纳入书中其他章节．
第8章：这是第l版中的第7章．该章中新增加了一些例子，这些例子以第4章中的概念(如弱序)为基础．同时，该章中还增加了一小节，讨论图的自同构，并在该章多处地方提到．
第9章：该章增加了讨论正交阵列和密码技术的一节，内容涉及识别码和秘密分享．与此同时，该章还讨论了模算术与RSA密码系统之间的联系，以及秘密分享应用的一个可求解设计的内容．此外，该章关于“组群测试”的新内容涉及几个应用，其中包括次品鉴别、疾病筛查、基因组图谱测绘和卫星通信．
第10章：有关“合意解码”的小节是新增的，这同寻找分子序列中的蛋白质有关，同时加入了涉及光盘错误校正码的内容．关于“判读”DNA产生蛋白质的材料也是新增加的．
第11章：在11．2节中增加了讨论单行线问题的几小节．这些新的内容涉及有关广场取向和栅格的最新结果，分别反映不同城市类型的需要．该章还增加了关于测试巨大图的连通性问题的内容，这类问题出现在与电信业务量和网上数据有关的最新应用中．此外，该章还包括关于DNA杂交顺序的内容．
第12章；这一章用若干新的例子解释概念，包括天花疫苗接种、音响系统和石油钻井的例子．我们写了新的一节讨论稳定婚姻问题及其许多最新的应用，包括医院实习医生分配等．第1版第13章中有关最大权匹配的内容已移至该章中．
加载中...
