“离散数学”中的OBDD案例教学研究

摘要:“离散数学”是计算机专业的核心课程,是研究计算机科学的数学理论基础。有序二叉决策图(OBDD-Ordered Binary Decision Diagram)是描述布尔函数的一种新的有效的数据结构。文章提出在课本知识的讲授过程中,引入OBDD来解析离散数学在计算机专业其他学科中的具体应用,加深学生对所学知识点的理解,并激发学生的学习兴趣和创新能力,从而引导学生充分认识离散数学在计算机专业中的重要作用。这对于提高“离散数学”课程的教学水平和质量,以及学生对后续课程的学习和今后进一步的科学研究均具有现实意义。

关键词:离散数学;OBDD;数据结构;教学

“离散数学”是现代数学的一个重要分支,是计算机专业必修的基础课程之一。离散数学在数据结构、程序设计语言、数值与符号计算、操作系统、软件工程、数据库、人工智能与机器人、网络、计算机图形学以及人机交互等各个领域,都有着广泛的应用[1-2]。离散数学研究的是各种离散形式的对象和它们的结构及其相互关系,其主要目标是培养学生掌握课程的基础理论和培养学生的数学抽象能力与严密的逻辑推理能力。它的主要内容包括数理逻辑、集合论、数论、图论和代数结构与布尔代数等。“离散数学”是一门概念多、理论性强、高度抽象、教学内容跨度大的课程,它不像计算机专业中的Java程序设计、面向对象程序设计等应用性课程那样能被学生直接应用于软、硬件开发,而是一堆符号、公式、定义、定理,为此在教学过程中常遇到的问题就是学生的学习积极性普遍不高,认为该课程的学习对今后的学习以及能力的提高无任何作用。众所周知,学生学习的动力来源于学习的兴趣,因此笔者认为教师可以利用课堂教学有意识地补充一些有关离散数学在某个具体的应用研究领域的研究成果,并将计算机专业知识融入“离散数学”教学中,来引导学生充分认识离散数学在计算机专业中的重要作用,从而激发学生对“离散数学”这门课程的学习兴趣。

有序二叉决策图(Ordered Binary Decision Dia- gram,OBDD)是描述布尔函数的一种新的有效的数据结构[3-4]。基于OBDD可以完成布尔函数的有效表述和操作运算,OBDD在VLSI逻辑综合和验证的成功应用引起了学术研究和工业应用界的极大关注。在实际教学过程中,注重理论与实际相结合。在传承课本知识的同时,引入近年来的研究成果――OBDD来解析离散数学在计算机专业其他学科中的具体应用,从而充实自己的教学素材,把基础数学理论与计算机类专业课程紧密而有机的结合起来,加深学生对所学知识点的理解,有意识地引导学生运用所学理论去分析、解决实际问题,激发学生的学习兴趣和创新能力,从而引导学生充分认识离散数学在计算机专业中的重要作用。这对于提高“离散数学”课程的教学水平和质量,以及对学生后续课程的学习和今后进一步的科学研究均具有现实意义。

1“离散数学”教学的现状

纵观目前的“离散数学”教学,其主要现状体现在以下几个方面:

作者简介:徐周波(1976-):女,讲师,硕士,研究方向为符号调度技术、符号模型检验、软件测试;古天龙(1964-):男,教授,博士,研究方向为形式化方法、符号计算、协议工程等。

(1) 课程抽象难懂。“离散数学”具有逻辑性强、抽象度大,且内容跨度大等特点,是一门既难教又难学的课程,这无疑给教师的教学和学生的学习带来一定的难度。

(2) 教学模式单一。目前离散数学的教学模式大多数以课堂讲授结合课后作业和习题课为主,而教师主要从纯数学理论角度来教授基本内容,不能充分体现专业基础课的实用性,很容易使学生产生“学离散数学无用”的想法。

(3) 缺乏基本理论的应用和与专业学科的结合。在“离散数学”的教学中,往往只重视理论教学,而很少注重基本理论的应用和与专业学科的结合,结果导致课程学习效果不佳,从而抑制了学生的学习的积极性和主动性,难于激发学生积极思考,影响学生创新意识与创新能力的培养。

2“离散数学”教学的创新对策

本文拟用OBDD来解析离散数学在计算机专业其他学科中的具体应用。为了便于说明问题,先对OBDD做一介绍。

2.1OBDD

OBDD是布尔函数的一种有效的图形表示,是一种新的数据结构。一个OBDD就是表示一簇布尔函数fi:{0,1}n{0,1}的一个有向无环图,图中的所有结点被分为终结点和内结点两类。一般用圆圈表示内结点,用方框表示终结点。没有射出边的结点称为终结点,且仅有两个终结点,即0和1。除终结点外的其它结点称为内结点,由变量名var(v)标记,且有两条射出边,即0-边和1-边。0-边是指该内结点的标记变量取值0后的分支,在图中一般用虚线表示。1-边是指该结点的标记变量取值1后的分支,在图中用实线表示。在OBDD中的任何一个结点,其0-边所指向的结点不同于1-边所指向的结点,且具有唯一性。图中任意一条从根结点(没有射入边的结点)到终结点的路径上,所有变量均按给定的变量顺序出现。对于变量的一组赋值,所得到的函数值由根结点到一个终结点的一条路径决定。这条路径所对应的分支由变量的这组赋值来决定,该分支的终结点所标识的值就是变量在这组赋值下所对应的函数值。

例如,对于一个布尔函数f=(x1+x2)×x3,其中“+”表示布尔“或”运算,“”表示布尔“与”运算。布尔函数f的真值表如表1所示。

表1布尔函数f=(x1+x2)×x3的真值表

x1 x2 x3 f x1 x2 x3 f

0 0 0 0 1 0 0 0

0 0 1 0 1 0 1 1

0 1 0 0 1 1 0 0

0 1 1 1 1 1 1 1

对于布尔函数f=(x1+x2) x3的完全二叉树及OBDD表示分别如图1的(a)和(b)所示。

(a) 完全二叉树 (b) OBDD

图1布尔函数f=(x1+x2) x3的表示

2.2提高学生对离散数学的认识,培养学生兴趣

“兴趣是学习之母”。为了培养学生学习离散数学的兴趣,在教学过程中,一定要精心准备每部分的导语,将每部分的离散数学知识是怎样应用到计算机科学中的说清楚,让他们充分认识到离散数学在计算机科学中的重要性。比如,在讲解数理逻辑部分时,可以将真值表部分的内容运用到逻辑电路的设计上,在此基础上,引入OBDD来表示真值表,进一步简化逻辑电路的设计,并启发学生运用这部分的知识设计一个简单的自动售货机等,这样不仅激发了学生学习离散数学的积极性,而且还进一步加强了学生理论联系实际的能力。

2.3基础理论与学科应用结合,激发学生创新能力

离散数学是研究计算机科学的数学理论基础。在其教学方面不是简单地传授给学生离散数学知识,更重要的是能够培养学生的逻辑思维能力、分析能力和创新能力。离散数学中的图论为数据结构和数据表示理论奠定了数学基础,也从算法角度为解决相关问题提供了一些方法。例如,对于布尔函数f=(x1+x2)×x3,

从数据结构的角度来看,若用图论中的完全二叉树来存储函数f,如图1(a)所示,则存在大量重复的0和1终结点,由此可见,上述函数的存储效率不是很高。对图1(a)仔细观察后发现,若从图的同构的角度看,所有终结点0均是同构的,终结点1也是同构的,且图1(a)中的右边3个x3表示的也是同一个结点。利用离散数学中图的同构性,将所有同构的图(子图)只保留一个,如图2(a)所示,这样可以大大节省存储空间。另外,由于n元命题公式P=(x1,…,xn)可视为含有n个布尔变量的布尔函数,而由命题公式的同一律p1p和排中律pp1,可知(xixi)xjxj。故从图中删去左右分支相同的结点,如图2(b)所示,并不影响原函数的性质。基于上述规则,可以得到如图1(b)所示的OBDD。由图1(b)可见,用完全二叉树来表示布尔函数f需存储15个结点,而用OBDD来表示则只需存储5个结点,由此可见用OBDD表示布尔函数更为紧凑、直接。通过此例,可以让学生切实体会到离散数学在数据结构和数据表示中的重要性,这不仅拓宽了学生的知识视野,而且还激发了学生的学习兴趣和创新能力。