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

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

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

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

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

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

作者簡(jiǎn)介:徐周波(1976-):女，講師，碩士，研究方向?yàn)榉?hào)調(diào)度技術(shù)、符號(hào)模型檢驗(yàn)、軟件測(cè)試;古天龍(1964-):男，教授，博士，研究方向?yàn)樾问交椒ā⒎?hào)計(jì)算、協(xié)議工程等。

(1) 課程抽象難懂?！半x散數(shù)學(xué)”具有邏輯性強(qiáng)、抽象度大，且內(nèi)容跨度大等特點(diǎn)，是一門既難教又難學(xué)的課程，這無疑給教師的教學(xué)和學(xué)生的學(xué)習(xí)帶來一定的難度。

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

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

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

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

2.1OBDD

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

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

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

x1x2x3fx1x2x3f

00001000

00101011

01001100

01111111

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

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

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

2.2提高學(xué)生對(duì)離散數(shù)學(xué)的認(rèn)識(shí)，培養(yǎng)學(xué)生興趣

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

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

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

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

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

圖2簡(jiǎn)化規(guī)則

3結(jié)語

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

參考文獻(xiàn):

[1] 左孝凌，李為鑑，劉永才. 離散數(shù)學(xué)[M]. 上海:上?？茖W(xué)技術(shù)文獻(xiàn)出版社，2004.

[2] 陳光喜，丁宣浩，古天龍. 離散數(shù)學(xué)[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

(編輯:彭遠(yuǎn)紅)