“離散數(shù)學”中的OBDD案例教學研究

摘要:“離散數(shù)學”是計算機專業(yè)的核心課程，是研究計算機科學的數(shù)學理論基礎(chǔ)。有序二叉決策圖(OBDD-Ordered Binary Decision Diagram)是描述布爾函數(shù)的一種新的有效的數(shù)據(jù)結(jié)構(gòu)。文章提出在課本知識的講授過程中，引入OBDD來解析離散數(shù)學在計算機專業(yè)其他學科中的具體應(yīng)用，加深學生對所學知識點的理解，并激發(fā)學生的學習興趣和創(chuàng)新能力，從而引導(dǎo)學生充分認識離散數(shù)學在計算機專業(yè)中的重要作用。這對于提高“離散數(shù)學”課程的教學水平和質(zhì)量，以及學生對后續(xù)課程的學習和今后進一步的科學研究均具有現(xiàn)實意義。

關(guān)鍵詞:離散數(shù)學;OBDD;數(shù)據(jù)結(jié)構(gòu);教學

“離散數(shù)學”是現(xiàn)代數(shù)學的一個重要分支，是計算機專業(yè)必修的基礎(chǔ)課程之一。離散數(shù)學在數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計語言、數(shù)值與符號計算、操作系統(tǒng)、軟件工程、數(shù)據(jù)庫、人工智能與機器人、網(wǎng)絡(luò)、計算機圖形學以及人機交互等各個領(lǐng)域，都有著廣泛的應(yīng)用[1-2]。離散數(shù)學研究的是各種離散形式的對象和它們的結(jié)構(gòu)及其相互關(guān)系，其主要目標是培養(yǎng)學生掌握課程的基礎(chǔ)理論和培養(yǎng)學生的數(shù)學抽象能力與嚴密的邏輯推理能力。它的主要內(nèi)容包括數(shù)理邏輯、集合論、數(shù)論、圖論和代數(shù)結(jié)構(gòu)與布爾代數(shù)等。“離散數(shù)學”是一門概念多、理論性強、高度抽象、教學內(nèi)容跨度大的課程，它不像計算機專業(yè)中的Java程序設(shè)計、面向?qū)ο蟪绦蛟O(shè)計等應(yīng)用性課程那樣能被學生直接應(yīng)用于軟、硬件開發(fā)，而是一堆符號、公式、定義、定理，為此在教學過程中常遇到的問題就是學生的學習積極性普遍不高，認為該課程的學習對今后的學習以及能力的提高無任何作用。眾所周知，學生學習的動力來源于學習的興趣，因此筆者認為教師可以利用課堂教學有意識地補充一些有關(guān)離散數(shù)學在某個具體的應(yīng)用研究領(lǐng)域的研究成果，并將計算機專業(yè)知識融入“離散數(shù)學”教學中，來引導(dǎo)學生充分認識離散數(shù)學在計算機專業(yè)中的重要作用，從而激發(fā)學生對“離散數(shù)學”這門課程的學習興趣。

有序二叉決策圖(Ordered Binary Decision Dia- gram，OBDD)是描述布爾函數(shù)的一種新的有效的數(shù)據(jù)結(jié)構(gòu)[3-4]。基于OBDD可以完成布爾函數(shù)的有效表述和操作運算，OBDD在VLSI邏輯綜合和驗證的成功應(yīng)用引起了學術(shù)研究和工業(yè)應(yīng)用界的極大關(guān)注。在實際教學過程中，注重理論與實際相結(jié)合。在傳承課本知識的同時，引入近年來的研究成果——OBDD來解析離散數(shù)學在計算機專業(yè)其他學科中的具體應(yīng)用，從而充實自己的教學素材，把基礎(chǔ)數(shù)學理論與計算機類專業(yè)課程緊密而有機的結(jié)合起來，加深學生對所學知識點的理解，有意識地引導(dǎo)學生運用所學理論去分析、解決實際問題，激發(fā)學生的學習興趣和創(chuàng)新能力，從而引導(dǎo)學生充分認識離散數(shù)學在計算機專業(yè)中的重要作用。這對于提高“離散數(shù)學”課程的教學水平和質(zhì)量，以及對學生后續(xù)課程的學習和今后進一步的科學研究均具有現(xiàn)實意義。

1“離散數(shù)學”教學的現(xiàn)狀

縱觀目前的“離散數(shù)學”教學，其主要現(xiàn)狀體現(xiàn)在以下幾個方面:

作者簡介:徐周波(1976-):女，講師，碩士，研究方向為符號調(diào)度技術(shù)、符號模型檢驗、軟件測試;古天龍(1964-):男，教授，博士，研究方向為形式化方法、符號計算、協(xié)議工程等。

(1) 課程抽象難懂。“離散數(shù)學”具有邏輯性強、抽象度大，且內(nèi)容跨度大等特點，是一門既難教又難學的課程，這無疑給教師的教學和學生的學習帶來一定的難度。

(2) 教學模式單一。目前離散數(shù)學的教學模式大多數(shù)以課堂講授結(jié)合課后作業(yè)和習題課為主，而教師主要從純數(shù)學理論角度來教授基本內(nèi)容，不能充分體現(xiàn)專業(yè)基礎(chǔ)課的實用性，很容易使學生產(chǎn)生“學離散數(shù)學無用”的想法。

(3) 缺乏基本理論的應(yīng)用和與專業(yè)學科的結(jié)合。在“離散數(shù)學”的教學中，往往只重視理論教學，而很少注重基本理論的應(yīng)用和與專業(yè)學科的結(jié)合，結(jié)果導(dǎo)致課程學習效果不佳，從而抑制了學生的學習的積極性和主動性，難于激發(fā)學生積極思考，影響學生創(chuàng)新意識與創(chuàng)新能力的培養(yǎng)。

2“離散數(shù)學”教學的創(chuàng)新對策

本文擬用OBDD來解析離散數(shù)學在計算機專業(yè)其他學科中的具體應(yīng)用。為了便于說明問題，先對OBDD做一介紹。

2.1OBDD

OBDD是布爾函數(shù)的一種有效的圖形表示，是一種新的數(shù)據(jù)結(jié)構(gòu)。一個OBDD就是表示一簇布爾函數(shù)fi:{0，1}n#61614;{0，1}的一個有向無環(huán)圖，圖中的所有結(jié)點被分為終結(jié)點和內(nèi)結(jié)點兩類。一般用圓圈表示內(nèi)結(jié)點，用方框表示終結(jié)點。沒有射出邊的結(jié)點稱為終結(jié)點，且僅有兩個終結(jié)點，即0和1。除終結(jié)點外的其它結(jié)點稱為內(nèi)結(jié)點，由變量名var(v)標記，且有兩條射出邊，即0-邊和1-邊。0-邊是指該內(nèi)結(jié)點的標記變量取值0后的分支，在圖中一般用虛線表示。1-邊是指該結(jié)點的標記變量取值1后的分支，在圖中用實線表示。在OBDD中的任何一個結(jié)點，其0-邊所指向的結(jié)點不同于1-邊所指向的結(jié)點，且具有唯一性。圖中任意一條從根結(jié)點(沒有射入邊的結(jié)點)到終結(jié)點的路徑上，所有變量均按給定的變量順序出現(xiàn)。對于變量的一組賦值，所得到的函數(shù)值由根結(jié)點到一個終結(jié)點的一條路徑?jīng)Q定。這條路徑所對應(yīng)的分支由變量的這組賦值來決定，該分支的終結(jié)點所標識的值就是變量在這組賦值下所對應(yīng)的函數(shù)值。

例如，對于一個布爾函數(shù)f=(x1+x2)×x3，其中“+”表示布爾“或”運算，“#61655;”表示布爾“與”運算。布爾函數(shù)f的真值表如表1所示。

表1布爾函數(shù)f=(x1+x2)×x3的真值表

x1x2x3fx1x2x3f

00001000

00101011

01001100

01111111

對于布爾函數(shù)f=(x1+x2) #61655;x3的完全二叉樹及OBDD表示分別如圖1的(a)和(b)所示。

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

圖1布爾函數(shù)f=(x1+x2) #61655;x3的表示

2.2提高學生對離散數(shù)學的認識，培養(yǎng)學生興趣

“興趣是學習之母”。為了培養(yǎng)學生學習離散數(shù)學的興趣，在教學過程中，一定要精心準備每部分的導(dǎo)語，將每部分的離散數(shù)學知識是怎樣應(yīng)用到計算機科學中的說清楚，讓他們充分認識到離散數(shù)學在計算機科學中的重要性。比如，在講解數(shù)理邏輯部分時，可以將真值表部分的內(nèi)容運用到邏輯電路的設(shè)計上，在此基礎(chǔ)上，引入OBDD來表示真值表，進一步簡化邏輯電路的設(shè)計，并啟發(fā)學生運用這部分的知識設(shè)計一個簡單的自動售貨機等，這樣不僅激發(fā)了學生學習離散數(shù)學的積極性，而且還進一步加強了學生理論聯(lián)系實際的能力。

2.3基礎(chǔ)理論與學科應(yīng)用結(jié)合，激發(fā)學生創(chuàng)新能力

離散數(shù)學是研究計算機科學的數(shù)學理論基礎(chǔ)。在其教學方面不是簡單地傳授給學生離散數(shù)學知識，更重要的是能夠培養(yǎng)學生的邏輯思維能力、分析能力和創(chuàng)新能力。離散數(shù)學中的圖論為數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示理論奠定了數(shù)學基礎(chǔ)，也從算法角度為解決相關(guān)問題提供了一些方法。例如，對于布爾函數(shù)f=(x1+x2)×x3，

從數(shù)據(jù)結(jié)構(gòu)的角度來看，若用圖論中的完全二叉樹來存儲函數(shù)f，如圖1(a)所示，則存在大量重復(fù)的0和1終結(jié)點，由此可見，上述函數(shù)的存儲效率不是很高。對圖1(a)仔細觀察后發(fā)現(xiàn)，若從圖的同構(gòu)的角度看，所有終結(jié)點0均是同構(gòu)的，終結(jié)點1也是同構(gòu)的，且圖1(a)中的右邊3個x3表示的也是同一個結(jié)點。利用離散數(shù)學中圖的同構(gòu)性，將所有同構(gòu)的圖(子圖)只保留一個，如圖2(a)所示，這樣可以大大節(jié)省存儲空間。另外，由于n元命題公式P=(x1，…，xn)可視為含有n個布爾變量的布爾函數(shù)，而由命題公式的同一律p#61657;1#61659;p和排中律p#61658;#61656;p#61659;1，可知(xi#61658;#61656;xi)#61657;xj#61659;xj。故從圖中刪去左右分支相同的結(jié)點，如圖2(b)所示，并不影響原函數(shù)的性質(zhì)。基于上述規(guī)則，可以得到如圖1(b)所示的OBDD。由圖1(b)可見，用完全二叉樹來表示布爾函數(shù)f需存儲15個結(jié)點，而用OBDD來表示則只需存儲5個結(jié)點，由此可見用OBDD表示布爾函數(shù)更為緊湊、直接。通過此例，可以讓學生切實體會到離散數(shù)學在數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)表示中的重要性，這不僅拓寬了學生的知識視野，而且還激發(fā)了學生的學習興趣和創(chuàng)新能力。

(a) 合并規(guī)則(b) 刪除規(guī)則

圖2簡化規(guī)則

3結(jié)語

“離散數(shù)學”是計算機專業(yè)的核心、骨干課程，是研究計算機科學的數(shù)學理論基礎(chǔ)。學好該課程，對于學習計算機專業(yè)的其他課程以及培養(yǎng)學生的工作能力與創(chuàng)新能力是至關(guān)重要的。因此，教師應(yīng)在教學中，時常給學生提示該學科與計算機其他專業(yè)學科間的緊密聯(lián)系，并補充一些前沿性成果來拓寬學生的知識面。本文以O(shè)BDD為例來解析離散數(shù)學在計算機專業(yè)其他學科中的具體應(yīng)用，從而引導(dǎo)學生充分認識離散數(shù)學的重要性。總而言之，學好離散數(shù)學可為學生將來從事軟、硬件開發(fā)和應(yīng)用研究打下堅實的理論基礎(chǔ)，它是計算機專業(yè)學生必須掌握的理論基礎(chǔ)和數(shù)學工具。

參考文獻:

[1] 左孝凌，李為鑑，劉永才. 離散數(shù)學[M]. 上海:上海科學技術(shù)文獻出版社，2004.

[2] 陳光喜，丁宣浩，古天龍. 離散數(shù)學[M]. 北京:電子工業(yè)出版社，2008.

[3]Bryant R E . Symbolic boolean manipulation with ordered binary decision diagrams [J]. ACM Computing Surveys， 1992，24(3):293-318.

[4]Drechsler R， Sieling D. Binary decision diagrams in theory and practice [J]. International Journal on Software Tools for Technology Transfer，2001，3(2):112-136.

Discussion on Case Teaching of Discrete Mathematics Based on OBDD

XU Zhou-bo， GU Tian-long

(School of Computer Science， Guilin University of Electronic Technology， Guilin 541004， China)

Abstract: The discrete mathematics is a core curriculum of the computer specialty， and is the mathematic basis of computer science. OBDD is a new and effectively data structure for Boolean function representation. In the process of teaching the textual knowledge， OBDD is introduced to show the concrete procedure of discrete mathematics in other subjects of computer specialty， which can further deepen students understanding of knowledge points， and motivate students' interest effectively and foster their creative awareness and abilities， and guide students to recognize the importance of discrete mathematics in computer specialty. It can improve the teaching level and teaching quality of discrete mathematics， and have realistic meanings for students to study the subsequent courses and scientific research in the future.

Key words: discrete mathematics; OBDD; data structure; teaching

(編輯:彭遠紅)