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