“離散數學”中實踐教學的探討

摘 要 本文闡述了離散教學在教學中加入實踐環節的必要性，介紹了作者在離散數學教學中進行的實踐教學的嘗試，并結合了具體實例—— Warshall算法的實現指出了在離散數學教學中加入實驗環節的可能性，旨在對以后的教學起到一定的促進作用。

關鍵詞 離散數學 Warshall算法 閉包

1 引言

離散數學是以研究離散量的結構和相互間的關系為主要目標，充分體現了計算機科學離散性的特點。它所涉及到的一些概念、理論和方法被大量地應用于數字電路、 編譯原理、數據結構、操作系統、數據庫系統、算法的分析與設計、人工智能、計算機網絡等專業課程中。例如，數據結構和算法科學中有大量離散數學的內容；在形式說明、驗證、密碼學的學習中需要有理解形式證明的能力；圖論的概念被用于計算機網絡、操作系統和編譯原理等領域；集合論的概念被用在軟件工程和數據庫中。同時，該課程所提供的訓練也十分有益于學生的概括抽象能力、邏輯思維能力、歸納構造能力的提高，以及學生嚴謹、完整、規范等科學態度的培養。

然而，在離散數學的教學中，大多數院校往往只重視課堂教學， 僅僅注重對理論知識的講解，而很少開設或不開設上機試驗，忽略了對其基本理論的應用，結果導致這門課學起來抽象難懂，從而抑制了學生的學習積極性和主動性，難于激發學生積極思考，影響了學生創新意識和創新能力的培養。因此，在離散數學的教學中適當引入實踐環節已成當務之急。

2 教學中加入實踐環節的嘗試

為了改變離散數學教學中的上述狀況，培養學生自主分析問題、解決問題的能力，同時也加深他們對該課程在專業教學中地位的理解和認識，在離散數學的教學過程中，我們嘗試了以課堂教學為主，適當增加上機實驗題目的教學模式。

對于上機實驗內容的選擇，我們應該既要考慮到典型方法和基本技術，也要充分體現“基本概念、基本技能、基本理論”的三基原則。例如，我們設計了一個如下樣式的上機實驗內容。

編寫一個關于關系矩陣運算的程序（利用C語言），能夠實現下面功能：

（1）任意給定一個關系，能夠判斷這個關系是否具有自反性、對稱性、傳遞性。

（2）任意給定兩個關系R1， R2， 能夠進行復合運算R1*R2。

（3）任意給定一個關系，能夠求得其自反閉包r(R)、對稱閉包s(R)和傳遞閉包t(R)(要求利用Warshall算法)。

（4）求出一個關系R的tsr(R)之后，能夠判斷出這是否是一個等價關系，如果是，能夠給出等價類集合。

注意：所有上述運算，必須利用矩陣運算來實現。

要求：

程序首先要求輸入一個集合A={a， b， c， d， ...}，屏幕文字提示并等待，并能夠辨別出集合中元素的個數。

程序能夠讀入兩個關系R1，R2(其中有序對中的元素均是A中元素)，然后顯示兩個關系的矩陣形式，并能夠判定輸入的對錯。

程序能夠自動顯示這些關系的如下性質：

（1）是否具有自反性、對稱性和傳遞性（文字說明）。

（2）R1和R2的復合關系R1*R2（矩陣顯示和文字形式）。

（3）給出某關系R的自反、對稱和傳遞閉包(分別進行矩陣顯示和文字形式)。

（4）給出關系R的tsr(R)和等價類集合 (矩陣顯示和文字形式)。

該設計幾乎涉及到關系的所有性質，基本涵蓋了集合論的主要內容，對于圖的矩陣表示和運算也具有重要意義。

在圖論部分，還可以設計以下上機實驗：

（1）求圖的可達矩陣。

（2）求出任何兩個節點之間特定長度的路的數量。

（3）求出任何節點所在的強分圖，任何邊所在的單向分圖。

（4) 求得割點和割邊（如果去掉相應的點或邊，則圖不再連通）。

（5）判定歐拉圖并求得歐拉路，可以適當判定哈密頓圖并求得哈密頓路（必要條件）。

（6）適當判定一個平面圖（必要條件） 。

（7）對節點進行著色（Welch Powell方法）。

（8）求出最小生成樹。

3 Warshall算法的上機實現

下面給出一個具體實例——求解關系傳遞閉包的Warshall算法的上機實現過程。

先了解有關的幾個定義、定理。

定義1如果一個集合符合以下條件之一：

(1) 集合非空，且它的元素都是有序對

(2) 集合是空集

則稱該集合為一個二元關系，記作R，簡稱為關系。對于二元關系R，若＜x，y＞ ∈R，可記作xRy。

定義2設R是A上的關系， 若

則稱R在A上是傳遞的。

定義3設R是非空集合A上的關系，如果有另一個關系滿足：

(1) 是傳遞的

(2)

(3) 對A上的任何包含R的傳遞關系，均有

則稱關系為R的傳遞閉包，記作t(R)。

定理設R是含有n個元素的非空集合A上的關系，則存在一個正整數k≤n，使得

這個定理提供了求解關系傳遞閉包的一種方法，但當有限集A的元素較多時，對關系R的傳遞閉包進行矩陣運算非常繁瑣，為此Warshall在1962年提出了一個有效算法：

設R為n元集上的關系，M是R的關系矩陣，則

(1)置新矩陣N=M;

(2)置i=1;

(3)對j(1≤j≤n)，若N的第j 行第i 列處為1，則對k =1，2，…，n 做如下計算：

將N的第j 行k 列處元素與第i 行k 列處元素進行邏輯加，然后將結果放到第j 行k 列處，即

N [j，k]= N [j，k] + N [i，k] ;

(4) i=i+1;

(5) 若i≤n， 則轉到步驟 (3)，否則停止。

最終得到的矩陣N為關系R的傳遞閉包R挼墓叵稻卣蟆?對于此類算法，除了在理論上給學生講明白之外，最重要的是要求學生能夠利用所學的程序設計知識編程實現。用C語言編寫的具體代碼如下。

#define N 3

main()

{ int M[N][N]={{1，0，0}，{0，1，0}，{0，1，1}};/*此處可改為由用戶輸入*/

int i，j，k，s;

for(i=0;i＜N;i++)

for(j=0;j＜N;j++)

if (a[j][i])

for(k=0;k＜N;k++)

{ a[j][k] +=a[i][k];

if (a[j][k] ＞1) a[j][k] =1;

}

}

其中集合為{a，b，c}，關系R的關系矩陣本例中固定為M，實際運行時也可由用戶輸入，最后再添加上輸出語句即是一完整的程序了。

4 結束語

實驗技能是計算機學科的學生必備的專業技能之一，也是衡量優秀專業人才的標準之一。通過在離散數學的教學中增加實驗環節，可以使學生逐漸掌握“學習、思考、練習、實踐、總結”的五階段學習方法，有利于學生對后繼課程的學習。

為了培養學生的專業技能和動手能力，我們可以從基本功抓起，要求學生在教學過程中熟悉一些問題的求解方法，學會算法的編程實現。這必將大大提高學生學習的興趣和主動性，從而潛移默化地開發了學生的創造性思維能力和獨立解決問題的能力，促進他們向更高層次過渡和發展。

參考文獻

[1] 左孝凌.離散數學[M].上海科技文獻出版社，2003.

[2] (美)Kenneth H.Rosen.離散數學及其應用(原書第四版)[M].袁崇義譯.北京:機械工業出版社，2002.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文