离散数学与计算机应用结合的若干实例研究
数字技术与应用
技术前沿
离散数学与计算机应用结合的若干实例研究
聂雅琳1 王海军2
(1:洛阳理工学院计算机与信息工程系 河南洛阳 471023; 2:河南科技大学数学与统计学院 河南洛阳 471003)
[摘 要]挖掘离散数学在计算机中的应用实例,尝试教学中的理论与实践相结合,提高教学质量,激发学习兴趣。[关键词]离散数学 计算机应用 教学

[中图分类号]G642 [文献标识码]A [文章编号]1007-9416(2010)06-0066-01
离散数学是计算机等信息类专业的核心专业基础课,离散数学的教学直接决定了后续课程的教学质量,因此如何更好的开展离散数学教学,提高离散数学教学质量意义重大。特别的,大部分教师在教学的过程中都会碰到学生的这样一个问题:“老师,我们学这个有什么用?”。离散数学这门课程同样不能例外,如能回答好这个问题,则能激发学生的学习兴趣,培养学习动力;否则,会给学生造成学习无用的错觉。作者在针对计算机科学与技术、信息与计算科学等专业的离散数学教学实践中,挖掘整理出若干有关离散数学在信息科学中的应用,在本文中基于这些应用,对如何提高离散数学的教学质量加以探讨和研究。
方法2:任务可分为三个步骤1)a1=axorb,2)b2=a1xorb=axorbxorb,由于xor运算可结合,b2=axor(bxorb)=axor0=a,步骤2完成后b内存放的是原始a的值;3)a3=a1xorb2=(axorb)xora,由于xor运算可交换并且可结合,a3=bxor(axora)=bxor0=b,步骤3完成后a内存放的即为原始b的值。(这里ai,bi为步骤i赋值完成后a和b的值,i=1,2,3)。
为间接证法。即假设有一组前提
H1,H2,L,Hm,要推出结论C,即证
H∧H2∧L∧Hm C,间接证法只要证明 H1,H2,L,Hm与 ¬C是不可满足的。人工
智能消解原理是将前提谓词公式
H1,H2,L,Hm与结论否定 ¬C的合取公式转化为不包含量词的简单子句集,基于少量的消解推理规则,若能证明该子句集不可满足,则利用Skolem定理能够得出 H1,H2,L,Hm与 ¬C是不可满足的,即 H∧H2∧L∧Hm C,从而完成计算机
2 等价类等概念在软件工程中的应用
软件测试的关键在于测试用例的设计,在实际的软件测试中要做到穷举测试(即把系统的所有可能的输入以及预期输出做成测试用例)是不可能的,因此需要有选择性的选取部分测试样例来尽可能地检测出尽可能多的错误。
假设T表示所有测试用例的集合, a,b∈T,定义关系R:
的一次推理[5]。
4 结语
离散数学与计算机的应用显然远不止这些,例如各种离散数学教材上均有所涉及,本文在这些教材之外,额外挖掘了一些离散数学在计算机应用中的若干实例。在实际的教学中,当讲到这些应用的时候,学生表现出极大的兴趣和学习热情,并积极地分析思考,取得了较好的教学效果。因此,继续挖掘离散数学理论与实践的结合点,并以通俗的语言呈现给学生,是每一位离散数学教师的一项长久持续的工作,从而促进教学质量的不断提高。
1 数理逻辑在计算机编程中的应用
在不少软件公司的面试题目中都出现过这样一道题目:不借助第三方变量,请交换两个变量a和b的值。
方法1:任务可分为三个步骤1)a=a+b, 2)b=a-b, 3)a=a-b,经过这三步赋值操作后,即能实现题目所要求的操作。但这种解法存在隐患,因为在步骤1中将a与b的和赋值给a有可能因为数据类型的问题而产生溢出,从而导致在后续的步骤2)和3)中达不到预期的变量交换效果。此时离散数学中数理逻辑章节所牵)运算符
[1]
aRb当且仅当a,b测试同一类错误
因为R自反、对称和传递关系,从而是等价关系。基于等价关系将所有的等价类做成商集T/R,则商集T/R将所有可能的测试用例依据等价类划分为若干子集,每个等价类中的测试用例均是测试同一类错误,则只需从商集的每个等价类中选取少数具有代表性的测试用例即可取得较好的测试结果。这种测试方法也称为等价类划分法
[2-4]
[参考文献]
[1]左孝凌,李为鑑,刘永才.离散数学.上海:上海科学技术文献出版社,1982.
[2]屈婉玲,耿素云,张立昂.离散数学.北京:高等教育出版社,2008.
[3]A. D. 亚历山大洛夫 等.数学—它的内容,方法和意义. 王元, 万哲先等译. 北京: 科学出版社,2001.
[4]张海藩.软件工程导论.北京:清华大学出版社,2008.
[5]蔡自兴,徐光佑.人工智能及其应用.北京:清华大学出版社,2003.
。例如,现有一个系统的输入是
学生的成绩:输入有效范围是0至100的正整数,而系统可能的输入为任意的正整数,若系统分为两类错误:输入有效情况下的错误和输入无效情况下的错误,则可根据等价关系R得出所有测试用例T的一个划分,即由两个等价类所构成的商集T/R,其对应的输入分别为{0, 1, 2, 3,…… , 99, 100}和{101, 102, 103, ……}。
的运算表如表1所
示。
观察运算表的第一、三行能够发现对于任意x (x=0,1),;观察最后两行能够发现当0与x (x=0,1)做异或运算时,结果仍然为a。基于这一特性,构造两个二进制数a和b的按位异或运算xor。基于该运算,可实现问题要求且能避免产生溢出,如下所述方法2。
表1 运算表
3 逻辑推理在人工智能中的应用
人工智能的一大主要学派:符号主义学派,也称为逻辑学派,认为人工智能起源于数理逻辑。人工智能这一术语最早即是由逻辑学派提出。消解是逻辑学派在子句集上重要的推理规则。
离散数学数理逻辑章节中介绍了推理理论的若干证法,其中一种重要的证法即
[注]
洛阳理工学院青年基金2008QZ11;洛阳理工学院教研项目:09-JY062;河南科技大学青年基金2008QN025;河南科技大学教研项目2009N-039
66数字技术与应用
《离散数学》课程在计算机学科中的作用及其应用_...2。1 数理逻辑的应用 数理逻辑是用数学方法研究思维... 其中群是一种特殊的代 数系统,具有可结合、有...
计算机科学与技术的理论技术,又称为计算机数学。 它是以研究离散性的结构和相互... 我们应该在讲解分析理论基础上 结合计算机学科应用, 以提高学生的学习兴趣和对 ...
随着离散数学知识和计算机理论的进一步结合, 数据挖掘, 模式识别, 神经网络等分支...无论计算机科学本身,还是与计算机科学及其 应用密切相关的现代科学研究领域, 都...
(福州大学数学与计算机科学学院,福建福州350002) 摘要...若干课程之间有着密不可分的关系,且离散数学的应用...以案例为先导的理论课教学,并结合生活实例或应用实例...
离散数学在其他学科及现实生活中的应用一、离散数学概论 离散数学是现代数学的一个重要分支, 也是计算机专业课程体系中地位极为重要的专业 基础课之一。 它以研究...
离散数学把计算机科学中所涉及到的研究离散量的数学综合在一起,进行较系 统的...再按该频度大小插入余下未参与结合的频度值中。 如此继续进行 ,直到全部频度...
科学的研究起着重要的作用,本文笔者结合自己的教学...在计算机科学中的一个重要应用是用离散数学研究纠错...2.5 在计算机科学中离散数学的应用实例分析 在...
关系在计算机科学中的应用 49页 免费 离散数学在...图论实例 图论实例—— Huffman压缩算法 压缩算法 10...疑点: 疑点: 在计算机科学的研究中,始终围绕着两个...
该课程结合计算机学科的特点, 主要研究离散量结构及相互关系,是一门理论性较强,应用性较广的课程。 掌握集合论、数理逻辑和图论等离散数学的基本概念和基本原理,为...
热门文档