离散数学(原书第5版)(典藏版)/(美)约翰.A.多西
全新正版 极速发货
￥ 47.61 5.3折 ￥ 89 全新
库存4件
广东广州
认证卖家担保交易快速发货售后保障
作者[美]约翰·A.多西（JohnA.Dossey）阿尔伯特·D.奥托（Albert
出版社机械工业出版社
ISBN9787111640455
出版时间2017-12
装帧平装
开本16开
定价89元
货号1201997751
上书时间2024-09-30
商品详情
- 品相描述：全新
- 商品描述
-
目录
出版者的话
译者序
前言
致学生
离散数学纪年表
第1章 组合问题与组合技术引论1
1.1 工程完成时间的问题1
1.1.1 问题1
1.1.2 分析2
1.1.3 关键路径分析3
1.1.4 一个建筑的例子4
1.2 匹配问题7
1.2.1 问题7
1.2.2 分析7
1.2.3 排列8
1.2.4 航空公司问题解决方案的实用性9
1.3 背包问题11
1.3.1 问题11
1.3.2 分析12
1.3.3 回顾实验问题14
1.4 算法及其效率15
1.4.1 算法的比较15
1.4.2 多项式求值16
1.4.3 子集生成算法19
1.4.4 冒泡排序21
历史注记24
补充习题25
计算机题27
推荐读物27
第2章 集合、关系和函数28
2.1 集合运算28
2.2 等价关系32
*2.3 偏序关系37
2.3.1 偏序和全序37
2.3.2 哈斯图40
2.3.3 拓扑排序41
2.4 函数44
2.5 数学归纳法52
2.6 应用58
历史注记65
补充习题66
计算机题69
推荐读物69
第3章 编码理论70
3.1 同余70
3.2 欧几里得算法75
3.2.1 优选公约数75
3.2.2 欧几里得算法75
3.2.3 欧几里得算法的效率77
3.2.4 扩展的欧几里得算法77
3.3 RSA方法79
3.3.1 指数取模80
3.3.2 RSA方法的解密83
3.3.3 RSA方法的可行性85
3.4 检错码和纠错码86
3.5 矩阵码93
3.5.1 矩阵码93
3.5.2 编码的校验矩阵94
3.6 单纠错矩阵码99
3.6.1 校验矩阵行译码法100
3.6.2 汉明码101
历史注记105
补充习题106
计算机题109
推荐读物109
第4章 图110
4.1 图及其表示110
4.1.1 图的概念和表示110
4.1.2 图的其他表示112
4.1.3 同构113
4.2 通路和回路117
4.2.1 多重图、通路和回路117
4.2.2 欧拉回路和欧拉通路119
4.2.3 哈密顿回路和哈密顿通路122
4.3 最短通路和距离129
4.3.1 广度优先搜索算法129
4.3.2 带权图131
4.3.3 通路的数目134
4.4 图着色138
4.5 有向图和有向多重图144
4.5.1 有向图145
4.5.2 有向图的表示145
4.5.3 有向多重图146
4.5.4 有向欧拉回路和有向欧拉通路148
4.5.5 有向哈密顿回路和有向哈密顿通路149
历史注记155
补充习题156
计算机题160
推荐读物161
第5章 树162
5.1 树的性质162
5.2 生成树168
5.2.1 生成树169
5.2.2 广度优先搜索法169
5.2.3 最小生成树和优选生成树171
5.2.4 普里姆算法的证明174
5.3 深度优先搜索179
5.3.1 深度优先搜索法179
5.3.2 回溯183
5.4 根树188
5.5 二叉树和遍历193
5.5.1 表达式树193
5.5.2 前序遍历195
5.5.3 后序遍历197
5.5.4 中序遍历199
5.6 很优二叉树和二叉搜索树202
5.6.1 很优二叉树202
5.6.2 二叉搜索树208
历史注记215
补充习题216
计算机题219
推荐读物220
第6章 匹配221
6.1 相异代表系221
6.1.1 相异代表系221
6.1.2 霍尔定理222
6.2 图中的匹配225
6.2.1 匹配225
6.2.2 偶图的矩阵227
6.2.3 覆盖227
6.3 匹配算法231
6.3.1 独立集算法的应用示例231
6.3.2 将算法运用于优选独立集233
6.3.3 独立集算法234
6.3.4 课程分配235
6.4 算法的应用239
6.4.1 柯尼希定理240
6.4.2 霍尔定理的证明241
6.4.3 瓶颈问题242
6.5 匈牙利方法245
6.5.1 匈牙利算法245
6.5.2 匈牙利算法的证明247
6.5.3 不是方阵的矩阵248
6.5.4 优选和独立集249
历史注记250
补充习题251
计算机题252
推荐读物253
第7章 网络流254
7.1 流和割254
7.2 流增广算法261
7.3 优选流最小割定理269
7.4 流和匹配274
历史注记280
补充习题280
计算机题283
推荐读物283
第8章 计数技术284
8.1 帕斯卡三角形和二项式定理284
8.2 3个基本原理287
8.3 排列和组合293
8.4 允许重复的排列和组合297
8.5 概率302
*8.6 容斥原理306
*8.7 排列和r组合的生成315
8.7.1 排列的词典序枚举315
8.7.2 r组合的词典序枚举317
历史注记320
补充习题321
计算机题323
推荐读物324
第9章 递推关系与生成函数325
9.1 递推关系325
9.2 迭代法333
9.3 常系数线性差分方程341
9.3.1 一阶常系数线性差分方程341
9.3.2 二阶线性齐次差分方程344
*9.4 用递推关系分析算法的效率350
9.4.1 顺序查找算法和冒泡排序算法的效率…350
9.4.2 分治算法的效率352
9.4.3 排序算法的效率357
9.5 用生成函数计数359
9.5.1 生成函数360
9.5.2 形式幂级数361
9.6 生成函数的代数365
历史注记372
补充习题373
计算机题375
推荐读物376
第10章 组合电路和有限状态机377
10.1 逻辑门377
10.2 构造组合电路383
10.3 卡诺图388
10.4 有限状态机397
10.4.1 奇偶校验机398
10.4.2 有限状态机399
10.4.3 带输出的有限状态机400
历史注记404
补充习题405
计算机题407
推荐读物408
附录A 逻辑和证明简介409
附录B 矩阵425
附录C 本书中的算法432
参考文献436
奇数号习题答案440
内容摘要
本书是一本很好的离散数学入门教材，主要内容包括集合、关系、函数、编码理论、图、树、匹配、网络流、计数技术、递推关系与生成函数、组合电路和有限状态机等。
本书充分考虑到了初学者的需要，叙述浅显易懂，内容、例题、习题都进行了精心的挑选和组织，讲解细致，循序渐进。
本书可作为高等院校计算机专业或其他相关专业的离散数学教材或教学参考书，也可作为自学者的参考书。
精彩内容
译 者 序
Discrete Mathematics, Fifth Edition
计算机从其诞生至今短短的几十年间，得到了令人瞩目的飞速发展，它在很多方面都深刻地改变了人类的活动方式和思维习惯。然而，现代数字计算机的理论模型依然是20世纪30年代提出的图灵机，这是一种“离散”的机器，可用来处理“离散”的对象。当然，正如大多数计算机的早期应用那样，通过近似计算等手段，计算机也可以处理“连续”的对象，但本质上，现代的数字计算机仍然是一种“离散”的机器。事实上，目前计算机已经越来越多地用于处理各种“离散”的对象。
离散数学研究离散对象的数量和空间关系，它包括多个数学分支，如本书所涉及的集合论、图论、组合数学、经典概率、自动机理论等，是计算机科学的理论基础，也是计算机应用的有力工具。18世纪以前的数学基本上都属于离散数学的范畴，之后，天文学、物理学等的发展极大地推动了连续数学（如微积分）的发展，直到20世纪中期，尤其是20世纪80年代以后，随着计算机日益渗透到现代社会的几乎各个方面，离散数学再次得到高度重视。当然，离散数学涉及的内容极其广泛，其应用全然不是仅局限于计算机科学，而是涉及我们生活的方方面面。
离散数学是计算机专业重要的必修课程之一，它是许多计算机专业课程的基础，国内外已经出版了大量的离散数学教科书和参考书，那么为什么还要引进出版这本书呢？
对大多数计算机专业的学生而言，囿于有限的数学素养，要学好这门课程不太容易。他们的困难主要表现在两个方面：一是看不懂或不理解某些内容；二是尽管看懂了有关的内容，但是不会应用，面对习题无从着手。另一个常常困惑学生的问题是：离散数学是否真的如教师所说的那样在计算机科学中起着关键的作用？本书针对这些问题进行了很好的处理。它不仅是一本很好的离散数学教材或参考书，还可以启发我们的思路，以便编写出更适合我国国情的教材。这就是我们要翻译此书、把它引荐给读者的原因。
本书充分考虑到计算机专业的学生和初学者的数学素养，对内容、例题、习题都进行了精心的挑选和组织，叙述方式力求深入浅出。对离散数学中出现的大量定义、定理和证明，不是简单地罗列，而是采用浅显易懂的语言娓娓道来，循序渐进地展开，并辅以足够的由易到难的例子，而且这些例子往往十分贴近日常生活或计算机应用。本书所提供的大量习题也是为了使读者在完成习题的过程中不知不觉地巩固和深化所学的知识和技能。本书的另一个特点是强调算法，这使读者很容易就把离散数学和计算机科学联系起来。
本书的作者John A. Dossey教授长期从事各个层次的数学教学研究和实践，著有大量数学教科书和科研论文，多次获得美国各种数学教学奖项，具有极其丰富的数学教学的理论和实践经验。本书凝聚了作者多年的研究成果和实践经验，是一本成功的离散数学入门教材，为美国众多大学所采用。事实上，它也是一本很好的自学教材。相信本书也一定会给国内的读者以莫大的帮助。
章炯民、王新伟和曹立曾经共同协作完成了本书第4版的翻译，在此基础上，第5版的翻译工作主要由章炯民完成。此外，万英杰、张钰、左文英等也参与了第5版的部分翻译工作。译者本着尊重原著的原则，力求准确、严谨地翻译，同时也更正了原著中的少量错误。由于译者水平所限，难免有错误和欠妥之处，敬请读者批评指正。
前 言
Discrete Mathematics, Fifth Edition
如今，数学的应用越来越多地涉及离散而非连续的模型，其主要原因是现代社会越来越多地用到计算机。本书适用于一学期的离散数学入门课程。
预备知识
虽然按照本书讲授的课程只要求很少的数学预备知识，但还是要求学生至少达到修读过两年高中数学所应具有的水平，包括解题和运算的技能以及抽象思维的能力。
方法
本书强调算法并以此贯穿全书。算法用文字表述，不需要具体编程语言的知识。
主题的选择
本书主题的选择基于多个专业组织的建议，包括MAA（美国数学协会）一年级和二年级离散数学课程制定工作组的建议、NCTM（National Council of Teachers of Mathematics，美国数学教师理事会）的“学校数学教育的原则与标准”和CBMS（Conference Board of the Mathematical Sciences，美国数学科学联合会）对数学教学的建议等。
灵活性
虽然本书是针对一学期的课程设计的，但是本书所包含的材料多于一个学期所能覆盖的内容。因此，教师可以根据学生的特定需求和兴趣方便地选择主题。本书以前的版本在从计算机科学专业的一年级课程到数学专业的高年级课程等许多课程中用过，并得到了良好的反映。现在的这个版本仍然为教师提供了灵活性，以适用于各种不同专业学生的课程。
第5版的变动
第5版的主要变动是新增了一章—第3章，讨论同余、欧几里得算法及相关的数论方面的内容、RSA公钥密码技术、检错码和纠错码（包括矩阵码）。本书其余内容与这一章不相关，所以可由教师根据需要进行取舍。学习矩阵码的内容要求熟悉矩阵，所以在学习编码理论这一章之前，不熟悉矩阵的学生需要先阅读附录B。（详见下面的“章节独立性”和“课程设置建议”。）
另外，新版本在表述的清晰性方面有所改进，对离散数学的新进展也给予了关注。
习题
本书的习题安排错落有致，灵活性强。每节后都有大量简单的计算题和算法题，其中大多数习题有助于学生针对离散数学的概念和算法进行全面练习，这对数学基础较弱的学生尤其重要；另一些习题拓展了正文中的材料，或者引入了正文中未论述过的新概念。带*号的习题是更具挑战性的问题。教师应根据课程和学生水平从中挑选。奇数号计算题的答案附在本书末尾。在每一章的末尾，有一组补充习题，用来温习各章最重要的概念和技术，以及探讨正文中未讨论的新概念。
章节独立性
在采用本书进行教学时，各章的顺序可以灵活地安排。下图显示了各章的依赖关系。其中，虚线表示第6章仅与第4章的前几节内容相关。本书只假定读者具有高中几何课程对于逻辑与证明的熟练程度，而对那些偏好更形式化处理的读者提供了一个附录（附录A），可以将它作为独立的单元在任何时候讲授，也可以与第9章一起讲授。仅在3.5～3.6节和第4章讨论邻接矩阵时，要求熟悉矩阵（附录B）。
第1章和第2章实质上是导论。第1章给出本书所处理的离散问题的样例，应很快讲授完。该章只是提出某些问题，而在本书的后面才给出解答。1.4节包含对复杂性的讨论，可以略过它，或者推迟到学生有更多算法经验时再讲授。在这一节中，教师可以只讲解与学生关系最密切的示例算法。
第2章复习各种基本主题，包括集合、关系、函数和数学归纳法。该章可以讲授得稍快些，这取决于学生的数学背景和课程的层次。对于数学背景较好的学生，第2章的很多内容应该可以让他们自学。如上图所示，除了第5章和第7章依赖于第4章，以及第6章与第4章前几节的内容相关外，其余各章均彼此独立。
为配合新的第3章，同余的内容从第2章中移出。与第4版一样，这个内容（见第5版的3.1节）可以在讲完2.2节（等价关系）以后的任何时候学习。
课程设置建议
下面的表格给出了三个课程设置范例。课程A的重点是图论及其应用，涵盖了第4～7章的大部分内容。课程B涉及图论较少，更强调计数技术。课程C的重点是计算机科学专业的学生所感兴趣的论题。
课程A课程B课程C
章课时数章课时数章课时数
141（跳过1.4节）314
252525
4646附录B1
575636
668846
749556
88附录A395
94附录A3
104
本书适用于各种层次的“离散数学”课程。比如，计算复杂性是一个很重要的主题，本书对许多算法的复杂性给予了关注。但是，这是一个较难的主题，其论述深度应当与课程的层次和学生的基础相吻合。
计算机题
各章结尾均给出一组计算机题，这些计算机题与该章的内容、算法等相关。本书刻意用普通的术语来叙述计算机题，以便适应使用各种计算系统和语言的学生。
致谢
我们衷心地感谢下列审阅本书的数学家：米勒斯维尔大学的Dorothee Blum、威斯康星大学麦迪逊分校的Richard Brualdi、佛罗里达州立大学的John L. Bryant、波特兰州立大学的 Richard Crittenden、乔治梅森大学的Klaus Fischer、东得克萨斯州立大学的Dennis Grantham、Clemson大学的William R. Hare、东密歇根大学的Christopher Hee、佛罗里达大西洋大学的Frederick Hoffman、佛罗里达靠前大学的Julian L. Hook、Broome社区学院的Carmelita Keyes、 Macalester学院的Richard K. Molnar、普度大学Calumet分校的Catherine Murphy、佛罗里达大学的Charles Nelson、迈阿密大学的Fred Schuurmann、Charles S. Mott社区学院的Karen Sharp和新汉普郡大学的Donovan H. Van Osdol。为本书第2版的改进提出有益意见的有我们的同事Saad El-Zanati、Michael Plantholt和Shailesh Tipnis, 本书的使用者，以及伯米吉州立大学的Elaine Bohanon、常青藤州立学院的George Dimitroff、威斯康星-怀特沃特大学的Richard Enstad、西密歇根大学的Donald Goldsmith、肯塔基教育网络的Thomas R. Graviss、威斯康星-怀特沃特大学的Gary Klatt、Kings学院的Mark Michael、Shepherd学院的Peter Morris、密苏里大学的Dix H. Pettey、Puget Sound大学的Matt Pickard、田纳西大学的Terry Walters、南密西西比大学的Porter Webster、Frostburg州立大学的Richard Weimer、威斯康星-伊奥克莱尔大学的Thomas Weininger和佛门大学的Mark Woodard。本书第3版进行了进一步改进，这得益于本书的使用者的意见，以及下列同行的评论意见：威斯康星-伊奥克莱尔大学的Veena Chadha、西密歇根大学的Gary Chartrand、东南路易斯安那大学的Tilak de Alwis、东华盛顿大学的Ron Dalla、 Evergreen 州立学院的George Dimitroff、佐治亚州立大学的Gayla S. Domke、得克萨斯大学阿灵顿分校的Jerome Eisenfeld、富劳斯特堡州立大学的Kathleen Elder、乔治梅森大学的Klaus Fischer、北弗吉尼亚社区学院的Donald A. Goral、南佛罗里达大学的Natasa Jonoska、 乔治梅森大学的Thomas Kiley、圣玛丽学院的Theresa D. Magnus、田纳西大学的Chris Mawata、北卡罗来纳A&T州立大学的Robert C. Mers、普度大学Calumet分校的Catherine M. Murphy、宾夕法尼亚爱丁堡大学的Anne Quinn、莱特州立大学的Steen Pedersen、密苏里大学哥伦比亚分校的Dix H. Pettey、Bemidji州立大学的James L. Richards、Washburn大学的A. Allan Riveland、中密歇根大学的Mohan Shrikhande和西密歇根大学的Allan Schwenk，以及我们的同事Roger Eggleton。
我们要对伊利诺伊州立大学的Michael Plantholt和Dean Sanders表示特别的感谢，他们独立地审核了第3版中所有算法的正确性和可读性，根据他们的建议对算法进行了实质性的修正和改进。
本书第4版的更改源于下列同行的评论意见：中西部州立大学的Mark Ferris、佐治亚州立大学的Johanne Hattingh、圣玛丽学院的Colleen Hoover、杜鲁门州立大学的Jason Miller和太平洋联合学院的Richard Rockwell。
本书第5版的更改源于下列审阅者的意见：旧金山城市学院的Glen Aguiar、The Citadel的Stephen Comer、黑鹰学院的Lowell Doerder、黑斯廷斯学院的Mark Hall、太平洋联合学院的George Hilton、布卢姆菲尔德学院的Kenneth Myers、弗吉尼亚工学院和州立大学的Charles Parry、大瀑布大学的Richard Schoyen、西密歇根大学的Allen Schwenk和伊利诺伊中**院的Fereja Tahir。
此外，在本书的出版过程中，我们还要感谢Jami Darby、Emily Portwood和Bill Hoffman出色的编辑工作，以及资深作者支持和技术专家Joe Vetere的大力协助。
John A. Dossey
Albert D. Otto
Lawrence E. Spence
Charles Vanden Eynden
致 学 生
Discrete Mathematics, Fifth Edition
本书讨论离散对象，即有限的过程以及元素可以列举的集合。这和微积分相反，微积分是关于无限的过程和实数区间的。
离散数学由来已久，近年来，随着计算机重要性的提高，离散数学得到了快速发展。数字计算机是一种复杂的但本质上有限的机器，在任意给定的时刻，都可以用一个很长但有限的0和1的序列来描述它，这个序列对应于其电子元件的内部状态。因此，离散数学对理解计算机和如何应用计算机极为重要。
算法是离散数学的一个重要组成部分，是进行某些计算的明确的指令。大家最早学习算法是在小学，因为算术中遍布着算法。例如，对长除法，小学生可能会写出诸如下面这种格式的算式：
其中，这些熟记在心的步骤是：在42中有3个13，3乘以13等于39，42减39等于3，把5抄写下来等。这些步骤就是算法。
算法的另一个例子是计算机程序。假设一家小公司想要找出所有欠款超过100美元，且拖欠至少3个月的顾客。尽管这家公司的计算机文件中包含这些信息，但这些信息只占所有数据的一小部分。所以，要写一个程序，筛选出公司想要知道的信息。这个程序由一组准确的计算机指令构成，并考虑到所有可能的情况，从而使之能将所要的顾客清单提取出来。
我们所举的两个例子在某一点上是相似的，即执行算法的实体并不需要理解算法为什么是有效的。小学生一般不知道为什么长除法会得出正确的答案，仅知道正确的步骤。当然，计算机也不理解任何东西，它只遵从指令（并且，如果指令错了，即程序错了，计算机也将“忠实”地得出错误的答案）。
如果你正在学习本书，那么你早已不是小学生了，而且你是人不是计算机，所以，你不仅要知其然，还要知其所以然。
我们会研究一些你以前可能从来没有见过的算法。例如，假设你打算开车从佛罗里达的迈阿密到华盛顿的西雅图。即使限定只走州际高速公路，也还是有数百条线路可以走。哪一条线路最近呢？你可能会拿出地图，一番斟酌后，找到一条你认为最近的线路，但是，你能肯定吗？
存在解决这个问题的算法，它可以给出正确的答案。更进一步，你还可以将这个算法在计算机上编程实现，用计算机找出最短的线路。本书将会阐述这个算法。
我们不仅对算法“如何”和“为什么”感兴趣
相关推荐
— 没有更多了 —
以下为对购买帮助不大的评价