微积分学是大学理工科学生必修的基础数学课程，这门学科是以连续函数表述的连续量为研究对象，采用的主要方法是极限，进而引入微分、积分、级数等概念来描述函数的性质。像物理、力学、化学等诸多学科都无法离开微积分甚至更高等的数学而独立发展。对于一项工程的设计，离开微积分甚至高等数学也是不可想像的。这些已为人们所共识。与连续量相对应的是离散量，相关的基础性数学工具就是离散数学而不是微积分学。由于数字计算机软硬件结构决定了它仅适于处理离散型信息的存储与计算，因此离散数学便成为计算机科学与技术的基本数学工具。某些理论上的“先见之明”，将会给以后学科的发展带来巨大的影响。例如，Turing对可计算的研究所建立的Turing机是计算机的理论模型，随后这种理念导致了计算机的诞生。Boole的逻辑代数已成功地用于计算机的硬件分析与设计。谓词逻辑演算为人工智能学科提供了一种重要的知识表示方法和推理方法。这些都体现了离散数学的重要作用。对于离散数学的原理和方法，经常要求其在计算机上的可实现性；而一般的数学理论和方法有时仅给出存在性的结论，并不给出构造性的问题解答，因此难于满足实用性的要求。随着计算机技术的发展，离散数学作为计算机科学的一种数学工具，其作用显得更加重要。如果仅满足于学习程序设计语言，掌握一些编程技巧，那么不一定要学习更多的基础性知识，甚至有高中生的知识水平就足够了。但对于计算机科学与技术专业的本科生、研究生来说，应有更高的要求，而不能满足于仅仅学习程序设计。对于一种程序设计语言来说，我们需要了解一些相关的问题：为什么会提出这种语言？它能解决什么问题？优势是什么？存在什么问题？它的语法、语义怎么样？利用该语言编写的程序必然是正确的吗？更深入的分析就是，计算机到底能做些什么？不能做些什么？什么是可计算的，什么是不可计算的，以及计算的复杂性又怎样？只有懂得一些深刻的基础性数学知识，才能对这些问题给出较为准确的回答。国内正式出版的离散数学教材已有很多种，其内容主要包含数理逻辑、集合论、代数、图论、自动机和计算几何等，这些是用于分析与处理离散量所必须学习的内容。RichardJohnsonbaugh所著的DiscretedMathematics是一本有关离散数学的入门教材，书中包含了大量的数学基础知识，其内容简单易懂，适合自学。本书与国内出版的离散数学教材相比有如下特点：●大量的实例和习题●对问题求解的详细解释与说明●与计算技术结合密切，包括许多算法的描述、计算复杂性的阐述以及上机实现的要求本书由清华大学计算机系的石纯一教授、金博士、张新良博士共同翻译，并由石纯一教授对全书进行了审校。此外，还要感谢张双民博士、张伟博士和卢科博士对本书的翻译工作所提供的帮助。由于译者的英文水平和对概念的理解水平有限，译文的不当之处在所难免，敬请读者批评指正。石纯一2005年9月于清华园序言《离散数学》这本书是作者讲授离散数学的多年教学经验的凝结。本书可以作为一到两个学期的离散数学的入门教材。读者在学习本书时不必掌握很多的数学预备知识，不需要进行演算，同时也不需要了解计算机科学的预备知识。书中给出了例题、练习、图表、问题求解部分，各个章节还提供了问题求解要点、本节复习、注释、本章自测题以及上机练习等内容，可以帮助读者掌握离散数学的基本知识。此外，本书还提供了相关的教师参考手册（具体申请办法请参见书后的“教学支持说明”）与Web站点。20世纪80年代以前，几乎没有关于离散数学入门课程的合适教材。然而，实际上又需要这样一门课程来拓宽学生的数学基础与计算能力，从而讨论和解决包括抽象、组合、算法和图等有用的专题。本书的第一版（1984年出版）满足了这种需要，并且对离散数学课程的发展产生了深远的影响。此后，离散数学课程得到了许多组织（其中包括数学和计算机专业的人士）的认可。美国数学学会（MathematicalAssociationofAmerica，MAA）的一个专门小组赞同讲授一学年的离散数学课程。电子与电气工程师协会（InstituteofElectricalandElectronicsEngineers，IEEE）的教育委员会建议本科一年级新生开设离散数学课程。美国计算机学会（AssociationforComputingMachinery，ACM）和IEEE指定了离散数学课程的教学大纲。本书的第六版和前面的各个版本一样，都包括了算法、组合数学、集合、函数、数学归纳法等这些组织认可的教学内容；同时这一版强调了理解和证明，以提高读者的数学水平。与第五版的不同之处根据众多读者对本书前几版内容的评论和建议，第六版对前面的几版进行了修改，其中与第五版的主要不同之处包括：●第1章的逻辑和证明得到了很大的扩展。第五版中的量词一节被分为两节，第一节（1.3节）只讨论包含单个量词的语句，而第二节（1.4节）讨论嵌套量词。第五版中的数学归纳法一节被分为两节。其中第一节（1.7节）介绍的数学归纳法的归纳步为：设S（n），证明S（n+1）；这一节还加入了循环不变量。第二节（1.8节）介绍强数学归纳法和良序性。通过一个使用良序性的例子，我们证明了商和余数定理。本书对第一章的说明、例题和相关资源都进行了全面的扩充。除此之外，本章还加入了程序设计语言中有关逻辑（例如与、或、非和DeMorgan逻辑定律）的例题。为了更加清楚地进行说明，表示逻辑非的上划线“-”改为“隆薄Ｕ庖徽赂酉晗傅亟馐土顺浞痔跫捅匾跫略龅睦馑得髁俗匀挥镅院头怕呒墓叵怠１菊录尤肓烁嗟闹っ髅夂腿绾喂乖熘っ鞯睦猓馐*59个增加到90个，练习题数从391个增加到521个。●在第2章加入了很多例题，以说明如何运用第1章的知识，其中包括集合、函数、序列和串中的一些命题（例如如何证明一个给定的函数是一对一的）。●第4章在说明“大O”和相关记号之前，首先列举了几个算法的例子（4.1节和4.2节），然后对其进行了简要的介绍。我们提到了很多现代算法并不具有经典算法的所有特性（例如很多现代算法不是通用的，不是确定的，甚至不能是有限步完成的）。为了说明这一点，本章给出了一个随机算法的例子（例4.2.4）。●数论的介绍与第五版的一些内容（例如整数的表示、最大公约数）构成了新的一章（第5章），其中对一些专题（例如算法数论）进行了扩充。这一章既包含经典的理论（例如整除性、素数的不可数性、基础算术理论），也包含算法数论：求最大公约数的欧几里得算法、求幂的重复乘方算法、计算满足gcd（a，b）=sa+tb的s和t、计算一个整数模的逆。本章的主要应用是RSA公钥密码系统（5.4节），这一章前几节介绍的算法可以完成RSA公钥系统所需的计算。●很多章节之后增加了问题求解要点，特别是在前面的几章中。顾名思义，问题求解要点是为了帮助学生总结求解问题的技巧。在许多章节的结尾，还给出了问题求解要点回顾，重点总结了本节求解问题的技巧。●增加了函数和数论的问题求解部分。●第五版的伪代码是Pascal形式的，这一版改为Java形式（类似于C和C++）。学生通常对这种形式更加熟悉。此外，伪代码的描述放到了附录中（附录C），这样就可以更早地获得代码。●本书的参考文献中加入了一些新的专著和文章，新的版本中更新了对一些专著的引用。●这一版的例题数增加到近600个（第五版中约有500个）。●这一版练习题增加到近4000个（第五版中约有3500个）。内容与结构本书的主要内容包括：●逻辑（包括量词逻辑）、证明、归结证明和数学归纳法（第1章），例1.4.15介绍了二人交替行动的逻辑游戏，这是一种判断量化命题函数真值的方法。●集合、数列、函数、和与积的符号、串、关系（第2章和第3章），其中的例题包括Hash函数的介绍和伪随机数发生器（2.2节）、任务调度的部分排序的应用（3.1节）以及关系数据库（3.4节）。●算法、递归算法和算法分析的讨论（第4章）。此外，有关算法的内容将贯穿全书，算法以伪代码形式书写（本书不要求读者掌握计算机科学的预备知识，伪代码的描述在附录C中给出）。本书介绍的算法包括覆盖算法（4.4节）、计算最大公约数的欧几里得算法（5.3节）、RSA公共密钥算法（5.4节）、排列组合的生成（6.3节）、合并分类（7.3节）、Dijkstra最短路径算法（8.4节）、回溯算法（9.3节）、深度优先和广度优先算法（9.3节）、树的遍历（9.6节）、博弈树求值（9.9节）、搜索网络的最大流（10.2节）、寻找最小距点对（13.1节）、凸包计算（13.2节）等。●关于函数增长的“大O”、健的讨论（4.3节）。引入的符号可准确地描述函数的增长和算法复杂性。●数论的介绍（第5章）。●排列、组合、离散概率和鸽巢原理（第6章）。可选读的章节（6.4节和6.5节）中介绍了离散概率。●递归关系及其在算法分析中的应用（第7章）。●图的介绍，包括并行计算中图模型的覆盖、骑士旅行、Hamilton环、图的同构、平面图（第8章）。8.4.3节给出了Dijkstra算法正确性的简单有效的证明。●树，包括二叉树、树的遍历、最小生成树、决策树、最小时间排序、树的同构（第9章）。●网络，最大流算法、匹配（第10章）。●Boole代数，重点是Boole代数与组合电路的关系（第11章）。●强调建模与应用（第12章）的自动机方法。SR触发电路在例12.1.11中进行讨论，并使用特殊的语法描述了分形（包括vonKoch雪花，参见例12.3.19）。●计算几何的介绍（第13章）。●关于矩阵、基础代数和伪代码的附录。●强调各部分内容的交叉和相互关联。例如，数学归纳法与递归算法的密切关系（4.4节）；Fibonacci数列在欧几里得算法分析中的应用（5.3节）；书中有许多练习需要使用数学归纳法；我们给出了如何通过定义一组顶点上的等价关系来刻画图的元素（参见例8.2.13后面的讨论）；以及计算n顶点二叉树的个数（定理9.8.12）。●强调阅读和证明。多数定理证明带有插图注释。有专门的小节（问题求解部分）向学生讲解如何进行问题求解以及如何进行定理证明。一些章节结尾的问题求解要点总结了求解本节问题的主要技巧。●大量的应用，特别是在计算机科学中的应用。●利用图表描述概念、表示算法如何工作以及阐释定理，从而使相关的内容讲解更加生动。有的图用来表示定理的证明。有关图的专题对证明做了进一步的解释。●每节的练习。●注解，给出了学习建议和进一步阅读的文献资料。●每章复习。●每章的自测题。●上机练习。●159条参考文献。●本书的最后列出了相关的数学和算法符号。
鄂公网安备 42010302001612号 