离散数学的思想和方法与计算机科学技术的联系

摘要：

离散数学也被称为是传统的逻辑学，并且在集合论中，包括函数以及数论基础算法设计等，这些进行汇集起来，从而成为一门比较综合的学科，而离散数学的应用，主要是对这些技术来进行结合，从而对问题进行解决的一种方式。离散数学也可以称之为是计算机科学学习中的基础的学科，

离散数学也可以看作是在构筑数学与计算机之间桥梁的一个载体，因为离散数学离不开集合论以及论论等数学知识的运用，同时，又与计算机科学中的相关数据理论也有关，因此，这可以领导人们更加充满计算机的思维，从而出现计算机领域的发展。

关键词：逻辑学;集合论;数论基础;算法设计;组合分析;离散概率;关系理论;图论与树;抽象代数;布尔代数;计算模型

　一、绪论

伴随着信息时代的到来，工业革命时代已经开始以微积分为代表，从而开展数学方面的研究，一算书写的重要性也逐渐得到了人们的认识，离散数学课程中所传授的相关知识和方法也广泛的体现到了日常的计算机科学技术和相关专业的领域当中，从科学计算一直到信息处理，使得理论计算机科学一直到计算机应用技术得到了飞跃的发展，因此，无论是在计算机软件还是计算机硬件上，我们应该加强对于计算机技术的应用认识，并且象棋与数学进行解密联合从而能够处理更离散化的数量关系，因此无论计算机科学本身还是与计算机科学紧密相关的科学领域，都面临着对离散结构进行建立的模型，因此，我们应该通过连续数量的关系，来对数学模型离散化进行建立，从而进行计算机处理。

　(一）集合论

1、要想用计算机解决问题就要为它建立数学模型，即描述研究对象及对象与对象之间的联系。

2、集合论

集合及其运算、二元关系与函数、自然数及自然数集、集合的基数。在集合A上的二元关系f的关系矩阵；关系矩阵的乘法与合成关系；可达矩阵；集合A上的二元关系f的有向图；

二元关系的性质自反性：在A上的二元关系，对任意属于A的元素x，<x,x>都属于f，否则是非自反。反自反：在A上的二元关系，对任意属于A的元素x，<x,x>都不属于f，否则是非反自反。非反自反=非自反对称性：在A上的二元关系，对任意属于A的元素x,y，若<x,y>属于f，则<y,x>也属于f反对称：在A上的二元关系，对任意属于A的元素x,y，若<x,y>属于f，则<y,x>不属于f，除非x=y;可同时具有对称性和反对称性。传递性：在A上的二元关系，对任意属于A的元素x,y,z，若<x,y>,<y,z>属于f，那么<x,z>也属于f。二元关系R的闭包：本身具有（自反/对称/传递）的性质的二元关系，二元关系R包含于这个二元关系对于其他的有这些性质的（自反/对称/传递）的二元关系R‘，如果R包含于R’，则R的闭包也包含于R‘。即R的闭包是最小的，具有这些性质（自反/对称/ 传递）且包含R的二元关系。闭包的求法：自反闭包直接并上IA对称闭包并上自身的逆递闭包并上二次可达,三次可达….直到成为传递闭包为止。r（R）=IaU R s(R)=R-1UR t(R)=R U R2 U R3….等价关系：R是自反的、对称的和传递的二元关系。二元等价关系上的等价类：设R为A上的等价关系，对于任意的x属于A，在R上x（把它看成单元集合）的象，称为x关于R的等价类。由等价关系，等价类中元素的等价类都是一样的。商集：等价类的集合，R是定义在A上的二元关系，R是等价的，对任意的x属于A，都对应着一个等价类，这些等价类的集合就是A关于R的商集，等于说R把A分成了许多等价类。划分：划分是一个集族，它包含于A的幂集，就是说它的每一个元素都是A的子集。同块关系：同块关系是定义在A上的关于某划分A一个二元关系，若<x,y>属于同块关系，那么x,y必须同属于划分A的某一个元素。同块关系是一个等价关系。子集数：把n元集分成K个非空子集的分法数。（n，0）=0；（n，1）=1；（n，2）=2^(n-1)-1 先放一个球，区分两个子集，然后n-1个球有2^（n-1）种放法，最后减去全部球都在一个子集里的方法。（n，k）=k*（n-1，k）+（n-1，k-1）；放最后一个球的时候有两种情况，K个子集都有球了，所以有K种放法；只有K-1个子集有球，最后一个球占一个子集。一个集合A上有多少种等价关系=A上有多少种划分（分成一个非空子集、两个、三个…一直到|A|个。加细：两个划分之间的比较。偏序关系：定义在集合A上的二元关系R，若R是自反的，反对称的，传递的，则R为A上的偏序关系。偏序集：R是A上的偏序关系，则二元有序对<A,R>为偏序集。可比：x,y属于A，只要x,y同属于R种某一个二元有序对，则X,Y可比。严格小于：当<x,y>属于偏序关系R，且x！=y，那么x严格小于y。覆盖：x严格小于y，且不存在一个z，使得x严格小于z，z严格小于y。哈斯图:用顶点表示A种元素，仅当y覆盖x时，将y画在x上方并连线。全序关系：如果一个偏序关系R，A中任意的元素x,y均可比，则R就升级为全序关系，偏序集<A,R>就升级为全序集。拟序关系：定义在集合A上的二元关系R，若R是反自反、（反对称）、传递的，在R为A上的拟序关系。（反自反性和传递性可推出反对称性）。<A,R>为拟序关系。拟全序关系：如果一个拟序关系R，A中任意元素x,y均可比（x！=y）或者x=y时，或者可以用三歧性来表示（<x,y><y,x>,x=y三式有且只有一个成立），此时逆序关系就升级为拟全序关系，<A,R>升级为拟全序集。最大元最小元：B包含于A，y属于B，若y是B的最大元，那么对于任意属于B的元素x，都有<x,y>属于某偏序关系R。（他比别的都大）若y是B的最小元，那么<y,x>属于R。极大元极小元：若y是B的极大元，对于任意属于B且<y,x>属于R的元素x，x=y，这样就放松了对y的限制，y不需要与任意x均可比了。（没有比他大的）上界下界：y是B的上界，那么对任意x属于B，<x,y>属于偏序关系R。最小上界最大下界：上界的最小元和下界的最大元链：B包含于A，B如果是A中的链，任意的x,y属于B，x与y均可比；如果B是A中的反链，任意不想等的x,y属于B，x与y均不可比；A中最长链（长度为n)，一定存在极大元。对A来说，A存在n个划分块，使得每个划分块都是反链。|A|=mn+1,那么A中要么存在m+1的反链，要么存在n+1的链。良序：对全序关系或者拟全序关系，如果对于A中任意一个非空子集B，B均有最小元，那么这个全序关系或者拟全序关系就升级为良序关系.二元关系是离散数学中的主要内容之一,在数据结构、点集拓扑、近世代数、算法分析和信息检索等学科中具有非常广泛的应用。结合信息与计算科学专业特点和作者教学实践,通过强调应用价值、优化教学内容、丰富教学方法和改进考核方式等不同角度探讨二元关系的教学模式改革,从而帮助大家灵活应用二元关系中的知识解决相关问题。

代数结构与组合数学、数理逻辑序结构是一些能拼起来的有序对；代数结构是笛卡尔积的子集；拓扑结构是进行交并运算的子集.代数结构的好处是可以研究一些复杂的不直观的关系。所以我们研究代数结构的时候比较关心同态这种突出某些代数性质的概念。拓扑结构的好处是可以研究整体的性质。递归是用栈(stack)数据结构实现的。正如我们上面所说的，计算f(n)，需要f(n-1)；计算f(n-1)，需要f(n-2)……。我们在寻找到f(1)之前，会有许多空缺: f(n-1)的值什么？ f(n-2)的值是什么? …… f(2)的值是什么？f(1)的值是什么? 我们的第一个问题是f(n)是什么，结果，这个问题引出下一个问题，再下一个问题…… 每个问题的解答都依赖于下一个问题，直到我们找到第一个可以回答的问题: f(1)的值是什么?我们用栈来保存我们在探索过程中的疑问。C语言中，函数的调用已经是用栈记录离场情境和返回地址。递归是函数对自身的调用，所以很自然的，递归用栈来保存我们的“疑问” 。

结构是布尔巴基学派看待数学的一种观点，序结构、代数结构和拓扑结构是最主要的几大类结构.以实数为例。实数可以比较大小，也就是定义一个元素x小于或等于另一个元素y，比如记为xRy. 它满足一些公理：1、对任何x，xRx；2、由xRy和yRx可以推出x=y；3、xRy且yRz推出xRz. 满足这组公理的集合就被称为有序结构.同时，实数可以加减乘除（除数不为0），所以它们满足域公理，这就是代数结构还有，实数有邻域、开集等概念，由此可以引出极限、连续等等概念，这就是拓扑结构。有些集合只有一两个结构，比如：素数集合只有序结构；整数集合没有拓扑结构；矩阵只有代数结构.希尔伯特的几何公理也可以看成是根据结构分的，比如第二组公理就是序公理，第五组公理是拓扑公理.数理逻辑属形式逻辑形式上符号化、数学化的逻辑，本质上仍属于知性逻辑的范畴。数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。简单地说，就是如果在函数中存在着调用函数本身的情况，这种现象就叫递归。以阶层函数为例,如下, 在 factorial 函数中存在着 factorial(n – 1) 的调用，所以此函数是递归函数。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是基础数学的一个不可缺少的组成部分。进一步剖析「递归」，先有「递」再有「归」，「递」的意思是将问题拆解成子问题来解决，子问题再拆解成子子问题，…，直到被拆解的子问题无需再拆分成更细的子问题（即可以求解），「归」是说最小的子问题解决了，那么它的上一层子问题也就解决了，上一层的子问题解决了，上上层子问题自然也就解决了,….,直到最开始的问题解决,文字说可能有点抽象，那我们就以阶层 f(6) 为例来看下它的「递」和「归」。数学思维：是人脑和数学对象（空间形式、数量关系、结构关系）交互作用并按照一般思维规律认识数学内容的内在理性活动。数学思维主要表现在数学思维的运演方面，在数学的特点和操作方法。求解问题 f(6), 由于 f(6) = n * f(5), 所以 f(6) 需要拆解成 f(5) 子问题进行求解，同理 f(5) = n * f(4) ,也需要进一步拆分,… ,直到 f(1), 这是「递」，f(1) 解决了，由于 f(2) = 2 f(1) = 2 也解决了,…. f(n)到最后也解决了，这是「归」，所以递归的本质是能把问题拆分成具有相同性质的子问题。直到最后被拆解的子问题再也不能拆分，解决了最小粒度可求解的子问题后，在「归」的过程中自然顺其自然地解决了最开始的问题。我们在上一节仔细剖析了什么是递归，可以发现递归有以下两个特点一个问题可以分解成子问题，子子问题，换句话说这些问题都调动同一个函数经过层层分解的子问题最后一定是有一个不能再分解的固定值的（即终止条件）,如果没有的话,就无穷无尽地分解子问题了，问题显然是无解的。所以解递归题的关键在于我们首先需要根据以上递归的两个特点判断题目是否可以用递归来解。经过判断可以用递归后，接下来我们就来看看用递归解题的基本套路（四步曲）：先定义一个函数，明确这个函数的功能，由于递归的特点是问题和子问题都会调用函数自身，所以这个函数的功能一旦确定了，之后只要找寻问题与子问题的递归关系即可接下来寻找问题与子问题间的关系，这样由于问题与子问题具有相同解决思路，只要子问题调用步骤 1 定义好的函数，问题即可解决。所谓的关系最好能用一个公式表示出来，如果暂时无法得出明确的公式，用伪代码表示也是可以的, 发现递推关系后，要寻找最终不可再分解的子问题的解，即（临界条件），确保子问题不会无限分解下去。由于第一步我们已经定义了这个函数的功能，所以当问题拆分成子问题时，子问题可以调用步骤 1 定义的函数，符合递归的条件（函数里调用自身）将第二步的递推公式用代码表示出来补充到步骤 1 定义的函数中，最后也是很关键的一步，根据问题与子问题的关系，推导出时间复杂度,如果发现递归时间复杂度不可接受，数理逻辑就是精确化、数学化的形式逻辑。它是现代计算机技术的基础。新的时代将是数学大发展的时代，而数理逻辑在其中将会起到很关键的作用。

结论

我们可以将离散数学称之为计算机科学的理论基础学科，将其看作是数学与计算机科学之间的桥梁，因为离散数学的研究，同样离不开集合论以及图论等相关数学知识，同样也和计算机科学中的相关数据库理论也具有一定的关联，可以领导人们更快的进入到计算机科学领域中去，能够促进计算机科学领域的发展，同样，随着计算机科学领域的不断发展，组合数学的重要性也日益提高。因为在计算机科学的研究过程中，核心的内容是对离散的数据进行处理，离散教学不仅仅在基础教学研究中占有非常强的地位，同样在其他的学科中也有所应用，比如说计算机科学遗迹，物理，化学等相关学科的应用，这同样为近代的工业革命奠定了一定的基础，而组合数学的整体发展也奠定了工业革命，计算机革命的基础，计算机之所以被称之为电脑，是因为人们将计算机的程序进行编写进去，从而使得计算机的算法是根据离散的对象来进行计算的，而不只是简单的在做一些数值方面的运算，所以准确的来说，组合数学也就是计算机出现以后发展非常迅速的一门数学学科，主要包括离散对象的存在以及构造等方面问题，由于计算机软件的发展迅速从而使得组合数学已经成为了一门非常深奥的学科组合，数学的发展也奠定了本世纪计算机革命发展的重要基础，能够改变传统教学模式中所占据的领导地位。正是因为有了组合算法才使人感到，计算机好像是有思维的。我觉得首先是要学过一遍，对离散数学的内容有个基本的了解，这样你才能根据自己的实际情况来判断是否需要学好。这就是广度优先的学习方法的好处，先了解各种知识的存在和它们在体系中的位置，当工作和学习中遇到问题就知道往哪个方向去探索和寻找解决方案。离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

　　参考文献

中国多媒体与网络教学学报》作者：陈波红、张婷2018年105期

《离散数据拟合模型的研究和实现》作者：尹文怡、范通让2008年《journal6》

致谢

论文的写作，过程曲折漫长，有抓耳挠腮，也有快意欣慰，只有当论文付梓之时，才感受到这是一种享受。不愿为祝老师多添麻烦，但也总避免不了老师为我操心、关心、用心。感激之语难以言表，唯有今后勤恳努力，方能回报师恩。这段求学路来之不易,时间,在弹指一挥间悄然离去,但给予我的人生却是一辈子的财富。我们的导师,辛勤的园丁,拿着手里小斧头,不断的修正我们的点点滴滴,扶着我们一次次地往IE确的学术科研的道路不断前进,我们的任课老师,是良师亦是我们的益友,还有我亲爱的同学们,谢谢你们给了我继续前进的力量。我的家人,是我最坚实的后盾。在这里,都请接受我最真挚的感谢。还有我的好朋友们,谢谢你们支持和鼓励,让我倍感学生生活的充实。最后,我要衷心的感谢我的父母，,是你无私的爱,可以让我坚守自己的梦想,谢谢你这些年为我和家庭付出的一切。