文章編號：1672-5913(2008)20-0129-02

摘 要：離散數(shù)學作為一門高度抽象的計算機專業(yè)課，為了激發(fā)學生的學習興趣，本文系統(tǒng)地介紹了其關(guān)系理論中的實驗設(shè)計，意在培養(yǎng)學生理解理論知識的同時鍛煉學生的思維構(gòu)架和計算機語言操作能力。

關(guān)鍵詞：離散數(shù)學；關(guān)系理論；實驗設(shè)計

中圖分類號：G642 文獻標識碼：A

1 引言

離散數(shù)學是計算機科學與技術(shù)專業(yè)的一門重要學科，它以研究離散量的結(jié)構(gòu)和相互間的關(guān)系為主要目標，所涉及到的一些概念、理論和方法被大量地應用于其他學科中。例如，數(shù)理邏輯在應用于人工智能理論研究的同時，著重培養(yǎng)了學生的概括抽象能力、邏輯思維能力、歸納構(gòu)造能力；圖論和集合論不僅為數(shù)據(jù)結(jié)構(gòu)和算法科學奠定了數(shù)學基礎(chǔ)，同時也為軟件工程和數(shù)據(jù)庫提供了抽象和描述的重要方法。

然而，由于這門課程具有概念多、理論性強、高度抽象等特點，學生普遍反應難于理解掌握，同時由于學生知識面的局限又導致學生認為該門課程對專業(yè)知識無用，致使學生學習興趣不高，教學效果不理想等現(xiàn)象。因此，激發(fā)學生的學習積極性和主動性，培養(yǎng)學生的創(chuàng)新意識和創(chuàng)新能力成了離散數(shù)學教學的當務(wù)之急。而在離散數(shù)學的教學過程中適當?shù)囊胍恍嶒炘O(shè)計，不僅是對離散數(shù)學的基本理論的很好驗證，也鍛煉了學生計算機語言的操作能力，同時也為其他課程的學習做了一個很好的鋪墊。

本文將以關(guān)系理論為基礎(chǔ)，深入探討離散數(shù)學實驗設(shè)計的可行性。

2 關(guān)系理論的實驗可行性

在離散數(shù)學中，關(guān)系理論是其一個重要的組成部分，它的知識點主要包括關(guān)系的性質(zhì)、關(guān)系的復合、逆運算和閉包運算、關(guān)系的劃分和覆蓋，以及等價關(guān)系、相容關(guān)系、序關(guān)系幾種特殊的關(guān)系，這些內(nèi)容都可以建立在矩陣的基礎(chǔ)上，因此本文以關(guān)系理論為基礎(chǔ)，設(shè)計了一個系統(tǒng)的模型，在加深學生對理論理解掌握程度的同時，也有效地鍛煉了學生的編程操作能力，激發(fā)了學生的學習興趣[1][2]。

3 設(shè)計模型

離散數(shù)學中關(guān)系的表示可以采用矩陣法，矩陣在計算機中可以以二維數(shù)組來存儲，而數(shù)組的建立和存儲在計算機語言中都有介紹，因此這一部分在本文中將不再贅述，而以算法的實現(xiàn)為討論的重點。這里，假定關(guān)系R1、R2均是集合X上的二元關(guān)系，其中X中有n個元素，將R1、R2的關(guān)系矩陣設(shè)為M1、M2。

3.1 關(guān)系性質(zhì)的算法設(shè)計

關(guān)系的性質(zhì)主要有自反性、對稱性、傳遞性、反自發(fā)性、反對稱性，其中除了傳遞性外，其它四個性質(zhì)的判別方法都比較簡單且易于實現(xiàn)[1[2]]，因此，這里主要給出傳遞性的判別方法。從矩陣關(guān)系圖上是不能直接得出的，因此可以通過求關(guān)系的傳遞閉包來實現(xiàn)傳遞性的判斷，而傳遞閉包的實現(xiàn)需要借助于關(guān)系的復合運算，因此可以先給出關(guān)系的復合運算和閉包運算的算法設(shè)計。

3.2 關(guān)系的復合運算算法設(shè)計

給定關(guān)系R1、R2，計算R1和R2的復合關(guān)系R的關(guān)系矩陣M：

(1) 置i=1， j=1；

(2) 按邏輯乘和邏輯加計算 ；

(3) j=j+1，若j≤n，轉(zhuǎn)(2)，否則轉(zhuǎn)(4)；

(4) i=i+1，若i≤n，轉(zhuǎn)(2)，否則停止。

3.3 關(guān)系的閉包運算算法設(shè)計

從關(guān)系的已知理論可以方便地計算出一個關(guān)系的自反和對稱閉包，因此我們這里重點給出傳遞閉包的算法設(shè)計。

若 ，則R具有傳遞性。這里， 表示R的i次復合運算。由此，可以通過調(diào)用關(guān)系的復合運算來實現(xiàn)。

(1) 置MR=M， M1=M， M2=M， i=1；

(2)，調(diào)用3.2中算法計算M，按邏輯加計算；

(3) 若 ， 置 ，轉(zhuǎn)(2)，否則轉(zhuǎn)(4)；

(4)為 的傳遞閉包，同時若 ，則 具有傳遞性，否則 不具有傳遞性。

3.4 等價關(guān)系與劃分的判定算法設(shè)計

由等價關(guān)系的定義可知，等價關(guān)系具有自反、對稱、傳遞性。其中，自反、對稱性的判定可以直接通過矩陣得出，傳遞關(guān)系可以通過調(diào)用3.3算法驗證。當驗證了一個關(guān)系是等價關(guān)系后，就可以由該關(guān)系得到相應的劃分。已知等價關(guān)系和劃分是一一對應性的，因此可以通過等價關(guān)系來判斷劃分。設(shè)集合 上有一個等價關(guān)系 ，把與 的固定元 有等價關(guān)系的元素放在一起做成一個子集 ，則所有這樣的子集就是由關(guān)系確定的一個劃分 。具體算法如下：

(1) 設(shè)X中有n個元素，xi是X中第i個元素，置i=1，；

(2) 令 ， ；

(3) 若 ，則 ；

(4) j=j+1，若i≤n，轉(zhuǎn)(3)，否則置 ，轉(zhuǎn)(5)；

(5) 若i≤n，則置i=i+1，轉(zhuǎn)(2)，否則結(jié)束；

3.5 相容關(guān)系與覆蓋的判定算法設(shè)計

相容關(guān)系具有自反、對稱性。因此一個關(guān)系是否是相容關(guān)系可以參照3.4中算法判定。

3.6 序關(guān)系中各個特殊元素的確定

一個偏序集合 ，且 是 一個非空子集，則 上一定有極大元、極小元，但最大元、最小元卻不一定存在。設(shè) 中有 個元素，下面給出這幾個元素的判定算法：

極小(大)元的判定：

(1) 設(shè)bi是B中第i個元素，置i=1；

(2) 令j=1；

(3.1)若 或( 且 )，則 ，轉(zhuǎn)(3.1)，否則轉(zhuǎn)(4.1)；

(3.2)若 或( 且 )，則 ，轉(zhuǎn)(3.2)，否則轉(zhuǎn)(4.2)；

(4.1)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中極小元。

(4.2)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中極大元。

最小(大)元的判定：

(1) 設(shè) 是 中第 個元素，置 ；

(2) 令 ；

(3.1)若 且 ，則 ，轉(zhuǎn)(3.1)，否則轉(zhuǎn)(4.1)；

(3.2)若 且 ，則 ，轉(zhuǎn)(3.2)，否則轉(zhuǎn)(4.2)；

(4.1)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中最大元。

(4.2)若 ，則 ，轉(zhuǎn)(2)，若 ，則 是 中最小元。

4 小結(jié)

本文以關(guān)系理論為基礎(chǔ)，重點討論了其各個知識點的算法設(shè)計并給出了具體的算法設(shè)計思想。通過本文的算法練習，可以培養(yǎng)學生的想象能力、探索能力和知識遷移能力，使學生的思維具有發(fā)散性，激發(fā)了學生的學習興趣，實驗設(shè)計的成功也給了學生一定的成就感，同時使得學生在練習計算機語言操作的同時加深了對離散數(shù)學中理論的理解，可謂一舉兩得。

參考文獻

[1] 涂建斌，周小強．離散數(shù)學課程教學改革初探[J]．數(shù)學理論與應用，2001，(11)，41-42.

[2] 何鋒．離散數(shù)學教學中的命題符號化難點討論[J]．計算機教育，2007，(9).38-40.

[3] 左孝凌．離散數(shù)學[M]．上?？茖W技術(shù)文獻出版社，1998.

[4] 徐鳳生．離散數(shù)學及其應用[M]．北京：機械工業(yè)出版社，2006.

Systemic Experiment Design of Relation Theory in Discrete Mathematics

YU Hong-bin

(School of Computer and Information technology， Henan Normal University ，Henan Xinxiang 453007)

Abstract: Discrete Mathematics is a height abstract of the calculator professional lesson， give tremendous pressure when student's study it. In order to string up student's interesting， a systemic experiment about relation theory is introduced in this paper introduced， to toughens student's thinking frame and develop the ability in operate computer language， at the time to train students’ comprehension of theories knowledge.

Keyword: Discrete Mathematics， relation theory， experiment designs

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”