結合計算機應用的離散數學教學研究

張劍妹 李艷玲 吳海霞

【摘要】結合計算機專業的離散數學教學實踐，對數理邏輯、集合論、代數系統和圖論四個部分在計算機科學中的應用進行了深入探討，并通過具體應用實例或練習闡述了如何將計算機應用與離散數學教學結合起來，以激發學生的學習興趣，提高教學效率.

【關鍵詞】離散數學；計算機應用；教學效率

【中圖分類號】G642

【基金項目】山西省高等學校教學改革重點項目（項目編號：J2012102），長治學院教學研究項目（項目編號：2011205）.

離散數學是研究離散量的結構及相互關系的數學學科，是計算機等信息類專業的專業基礎課.該課程的學習為數據結構、編譯原理、操作系統、數據庫原理和人工智能等后續課程的學習打下了堅實的數學基礎，同時也有利于提高學生的抽象思維、邏輯思維和計算思維能力，為學生后續的學習和工作奠定了基礎.鑒于離散數學在計算機科學中的重要性，中國計算機科學與技術學科教程2002和教育部高等學校計算機科學與技術教學指導委員會都將其列為計算機科學與技術學科教育的核心基礎課程.

離散數學具有內容廣、概念多、邏輯性與理論性強、高度抽象等特點，對計算機專業的學生來講，他們更注重于計算機應用技能的獲得，認識不到離散數學與其專業的相關性，把離散數學作為一門純粹的數學課學習，導致一些學生失去學習熱情，嚴重影響教學效果.另一方面，純數學的教學方法也不能滿足應用性人才培養的需求.為了解決這個問題，很多教師離散數學教學中增加相應實驗內容，并且設計了切實可行的實驗項目.但這些實驗項目大多是對離散數學中的一些基本算法進行實現，其目的在于鞏固學生所學的基本概念、原理和方法.筆者認為影響離散數學教學效率的一個最根本的原因是學生不明白離散數學與所學專業的關系，如何將離散數學與計算機應用相結合起來成為提高離散數學教學效率的重要環節.本文深入探討了離散數學在計算機科學中的應用，并給出了必要的應用實例，旨在引導廣大教師將更多的計算機應用相關的實例引入離散數學課堂教學中，使學生認識到離散數學的實用性，從而激發學生的學習興趣，提高教學效率.

一、數理邏輯在計算機科學中的應用

數理邏輯是以數學的方法研究形式邏輯中的推理，一般包括命題邏輯和謂詞邏輯兩部分內容，它廣泛地應用于人工智能、程序理論、數據庫理論和計算機硬件電路設計等研究中.在課堂教學中，如果教師僅用這些概括性的結論強調數理邏輯在計算機科學中的應用，恐怕會適得其反，為了突出應用，吸引學生的注意力，教師可以把如下幾個簡單的應用實例引入課堂教學.

1.數理邏輯在硬件電路設計中的應用

數理邏輯中的邏輯演算是數字邏輯的基礎，計算機系統中用高低電平來表示二進制數據中的1和0，計算機電路設計中用與、或、非門來實現數據的算術運算和邏輯運算.離散數學教學中我們引入一位全加器的設計作為數理邏輯在硬件電路設計中的應用實例.教師首先闡述邏輯電路設計的基本步驟（若還未開設數字邏輯課，教師可以詳細講解，否則，則是簡單地復習已有知識），然后要求學生寫出邏輯表達式.

假設Ai，Bi為兩位操作數，Ci-1為低位的進位，Si為本位和，Ci為本位向高位的進位，根據加法的意義，學生很容易寫出如下真值表：

當學生根據真值表寫出邏輯表達式時，教師只要稍加引導，學生就會發現寫出的邏輯表達式恰好是主析取范式，主析取范式與真值表的關系是書寫邏輯表達式最直接的理論依據.既然學生已經發現了數理邏輯在硬件電路設計中的應用，是否繼續畫邏輯電路已無關緊要了.對有余力的同學，教師還可以給出一些具體要求，讓學生設計一個表決器或者搶答器.

2.程序設計中的數理邏輯

數理邏輯可以用來驗證程序的正確性，同時，學生在自覺不自覺中已經將數理邏輯應用到程序設計中.為了使問題更加清晰，教師可以將如下實例引入離散數學課堂教學中.例，在數組StArr中查找“Jon”，使用方法StArr.size（）和StArr[i].getName（）寫出兩個循環條件并證明這兩個循環條件的等價性.學生很容易得出如下兩個循環條件并使用德摩根律證明兩個循環條件的等值性：

i

not （i>=StArr.size（） or StArr[i].getName（）=="Jon"

3.量詞在SQL語句的應用

數理邏輯的謂詞演算被引入到關系運算中，以此為基礎形成的關系數據庫查詢語言叫關系演算語言，如ALPHA語言，QEB語言等，關系數據庫的SQL查詢語句中也允許用戶使用全稱量詞和存在量詞.教師可以有意識地讓學生做SQL查詢方面的訓練.假如某學生管理數據庫中有如下三個數據表：學生表S（S#，SNAME，SEX，AGE，DEP），課程名表C（C#，CNAME，TEACHER），學生選課表SC（S#，C#，GRADE）；要求學生用帶量詞的SQL語句完成如下查詢并驗證其查詢結果是否正確.

①查詢至少選修一門課的學生的姓名；

②查詢選修全部課程的學生的姓名；

③查詢沒有學生選修的課程.

教師也可以給出相應的查詢語句并讓學生解釋，使其體會到離散數學與計算機應用之間的關系.

二、集合論在計算機科學中的應用

集合論一般包括集合代數、二元關系和函數三部分內容.集合是具有共同性質的、可確定的、可分辨一組事物組成整體，二元關系是由二元組作為元素構成的集合，函數是特殊的二元關系.由此可見，二元關系和函數都是集合.集合是構造離散結構的基礎，在數據庫技術、數據結構、軟件工程和程序設計中得到了廣泛的應用.

1.集合在關系數據庫查詢中的應用

一個關系數據庫表就是其行的集合，數據表中每個行就是由其數據項組成的一個n元組（表中有幾列就是幾元組），關系代數中選擇運算和投影運算及為二元關系中的限制運算和像運算，笛卡爾積運算可以使用SQL語句中的多表連接查詢來實現，SQL查詢中還允許使用普通的并、交、差、補等運算.在教學中，我們針對學生管理數據庫中的數據表設計了如下查詢，要求學生用連接運算和集合運算完成，并鼓勵學生在課外上機驗證，以激發學生的學習興趣.

例1 完成下列SQL查詢.

① 檢索數學系和計算機系的所有學生的姓名；

② 檢索既選修C2和C3課程的學生的姓名；

③ 檢索選修C2但不選修C3課程的學生的姓名；

④ 檢索沒有選修C2和C3課程的學生的姓名.

這個例子有助于學生很好的理解邏輯運算和集合運算之間的關系.如①的兩種SQL查詢語句分別如下：

I.SELECT S.SNAME FROM S WHERE DEP="數學系" and DEP="計算機系"

II.SELECT S.SNAME FROM S WHERE DEP="數學系"

UNIONSELECT S.SNAME FROM S WHERE DEP="計算機系"

例2 顯示下列SQL語句的執行結果，分析該結果的正確性及其原因.

SELECT S.SNAME，C.CNAME FROM S，C

該例子的查詢結果是表S和表C的笛卡爾積，無論學生與課程之間是否有選課關系，都會將學生名和課程名連接起來.

2.等價類在軟件測試中的應用

軟件測試是軟件開發的最后一個階段，其目的是通過運行程序，發現程序中潛在的錯誤.等價類劃分是黑盒測試最常用的方法，其基本思想是把輸入數據的可能取值劃分為若干個等價類，使每個等價類中的數據可以發現程序中的一類錯誤，這樣只需從每個等價類中選擇一個數據作為測試用例就可測試出這類錯誤，而不需要窮舉所有的數據.實際教學中，教師可以寫出一個簡單C語言程序要求學生使用等價類劃分法設計測試用例，如用戶登錄系統、輸入一個年月日計算這天為該年的第幾天等程序.這樣既有利于學生對等價關系、等價類、商集和劃分等概念的理解，也有利于學生理解離散數學在計算機科學中的應用，從而激發學生的學習興趣，變被動學習為主動學習.

三、代數系統在計算機科學中的應用

代數系統的研究方法和研究結果在構造可計算數學模型、研究計算復雜性、編碼理論、程序設計語言的語義學等方面有著重要的意義.代數系統中的群論在計算機安全領域得到廣泛關注，比如利用置換群實現秘鑰交換.在講解枯燥無味的群論時作者引入了如下應用實例.

計算機網絡安全中常用的數據加密技術有對稱加密和不對稱加密.凱撒密碼是一種古老的對稱加密體制，其基本思想是通過把字母移動一定的位數來實現加密和解密.凱撒密碼容易被破解，在實際應用中無法保證通信安全.為了使密碼具有更高的安全性，出現了單字母替換密碼.如，

明碼表 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

密碼表 Q W E R T Y U I O P A S D F G H J K L Z X C V B N M

即明文中的A替換成Q、B替換成W、C替換成E等，如果密碼表是明碼表的任意中重排，秘鑰就會增加到26！種，破解非常困難.很顯然，每個字母表就是一個置換，這樣，在26個英文字母上的置換和置換的復合構成了置換群.

使用字母表替換密碼，通信雙方需要預先約定好共享的保密秘鑰（即字母表）.若由于某種原因（如，原秘鑰受到威脅）需要臨時改變秘鑰，秘鑰交換就成為一個至關重要的問題.置換群可以實現用戶的密鑰交換，為了便于理解，假定通信雙方之間傳輸的信息只有A，B，C三個字母，三個字母上有6個不同置換，這樣用戶A，B的公共信息為置換群G={σ1，σ2，σ3，σ4，σ5，σ6}.運算表如下：

（1）用戶A從群G中構造一個序列SA={σ2，σ3，σ4，σ5}并向外界公布，用戶B從群G中構造一個序列SB={σ1，σ4，σ5，σ6}也向外界公布；

（2）用戶A在序列SA中選擇一個私鑰X，不妨設X-1=σ2σ3σ5=σ6，對SB中的元素進行共軛運算Xσ1X-1，Xσ4X-1，Xσ5X-1，Xσ6X-1，并把結果發給用戶B，本例中運算結果為{σ1，σ2，σ5，σ6}；

（3）用戶B在序列SB中選擇一個私鑰Y，不妨設Y=σ4σ5σ6=σ4，并對SA中的元素進行共軛運算Yσ2Y-1，Yσ3Y-1，Yσ4Y-1，Yσ5Y-1，并把結果發給用戶A，本例中運算結果為{σ3，σ2，σ4，σ6}；

（4）用戶A用自己的私鑰X和用戶B發給自己的信息可得：

X·YX-1Y-1=X·Y（σ2σ3σ5）Y-1=X·Yσ2Y-1·Yσ3Y-1·Yσ5Y-1=σ5σ3σ2σ6=σ6；

（5）用戶B用自己的私鑰Y和用戶A發給自己的信息可得：

XYX-1·Y-1=X（σ4σ5σ6）X-1·Y-1=Xσ4X-1·Xσ5X-1·Xσ6X-1·Y-1=σ2σ5σ6σ4=σ6.

用戶A和用戶B即得公共會話密鑰K=XYX-1Y-1=σ3=（1 3） （2 4）.

四、圖論在計算機科學中的應用

圖論是一個應用非常廣泛的數學分支.在圖論中用頂點表示事物，用頂點之間的邊表示事物的聯系，這樣，圖論就成為很自然的一種數據結構，這種數據結構為許多問題的解決提供了抽象和描述方法，廣泛地應用在計算機科學中.從圖的形式化定義看，圖中的頂點組成一個集合，邊是頂點集上的關系，這樣，圖論則是關系的圖形化表示.在離散數學中，為了激發學生的學習興趣，每個教師都會引入一些有趣的數學游戲和一些典型的應用，如關鍵路徑問題和最短路徑問題.除此之外，教師還可以引入一些計算機應用方面的實例，以突出圖論在計算機科學中的重要性.

1.圖在計算機網絡設計中的應用

在計算機網絡工程中，設計者總希望用盡可能少的網絡布線連接網絡站點，這樣，就不可能通過站點之間的連線來確定它們是否連通.使用圖可以有效地測試網絡站點之間的連通性.網絡結構可以用有向圖表示，其中圖中的節點表示網站，節點間的有向邊表示網站之間的鏈接.教師可以給定一個網絡結構圖，要求學生使用有向圖的鄰接矩陣計算是否可以從一個網站導航到另一個網站.事實上，如果把網絡節點之間的鏈接看成是一種關系的話，給定一組網絡站點，根據網絡站點之間的連接可以建立一個該節點集上的關系，這樣利用關系的傳遞閉包也可以判斷任意兩個網絡站點之間是否有網絡連接.通過這個例子，不僅可以使學生理解圖與計算機應用之間的關系，還可以使學生進一步理解關系與圖之間的關系，加深學生對圖的形式化定義的理解.

2.哈夫曼樹在文本文件壓縮中的應用

哈夫曼樹是一種最優二元樹，用哈夫曼樹產生的二元前綴編碼叫哈夫曼編碼.在離散數學教材上，通常會以例題的形式給出哈夫曼編碼在信息傳輸中的應用.事實上，這樣的例子足以說明樹在計算機科學中的應用，但是由于該例題的局限性，很多學生沒有認識到樹在計算機科學中的重要性.作者把這個例題稍做擴展后，將哈夫曼編碼在文件壓縮中的應用[10]引入到離散數學教學中.

壓縮分為有損壓縮和無損壓縮.視頻、音頻等多媒體信息經常進行有損壓縮，而本文只能采用無損壓縮，基于哈夫曼編碼的壓縮是一種無損壓縮.利用哈夫曼編碼壓縮文件的基本步驟如下：

（1）掃描原文件，統計各個字符出現的頻率.每個西文字符占一個字節，而且最高位為0；對于中文字符，將一個字符分為兩個字節，以字節為單位進行統計；

（2）利用統計結果構造哈夫曼樹；

（3）利用構造好的哈夫曼樹對各字符進行哈夫曼編碼；

（4）再次掃描原始文件，利用生成的哈夫曼編碼重新編碼原始文件，即得到一個壓縮文件.

五、結束語

通過將計算機應用與離散數學理論相結合的教學方法，使學生對離散數學與其專業的相關性有了充分的認識，激發了學生的學習興趣，提高了學生的學習積極性，有效地提高了離散數學的教學效率.未來，我們將在離散數學教學中增加更多的實用性內容，以滿足應用型人才培養的需求.

【參考文獻】

[1]中國計算機科學與技術學科教程2002研究組.中國計算機科學與技術學科教程2002 [ M ].北京：清華大學出版社，2002.

[2]教育部高等學校計算機科學與技術教學指導委員會.高等學校計算機科學與技術專業核心課程教學實施方案[M].北京：高等教育出版社，2009.

[3] 徐鳳生.離散數學及其應用[M].北京：機械工業出版社，2006.

[4] 藺永政，王新紅，李金屏.離散數學中實踐教學的探討[J].計算機教育，2006，10： 03-104.

[5] 徐鳳生.“離散數學”課程的教學改革與實踐[J].高等理科教育，2009，85（3）： 44-47.

[6] 沈來信，楊帆.離散數學的實驗教學探討[J].黃山學院學報，2009，11（3）：122-124.

[7] 薩師煊.數據庫系統概論[M]，北京：高等教育出版社，2010.

[8] Aditya P Mathur.軟件測試基礎教程[M].王峰，郭長國，陳振華，等譯.北京：機械工業出版社，2011.

[9]湯紹春.由群論中換位子實現的密鑰交換及其應用[J].韶關學院學報（自然科學版），2010，31（9）：27-30.

[10]薛向陽.基于哈夫曼編碼的文本文件壓縮分析與研究[J].科學技術與工程，10（23）： 5780-5781.