結合計算機應用的離散數(shù)學教學研究

張劍妹 李艷玲 吳海霞

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

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

【中圖分類號】G642

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

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

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

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

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

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

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

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

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

2.程序設計中的數(shù)理邏輯

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

i

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

3.量詞在SQL語句的應用

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

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

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

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

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

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

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

1.集合在關系數(shù)據(jù)庫查詢中的應用

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

例1 完成下列SQL查詢.

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

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

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

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

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

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

II.SELECT S.SNAME FROM S WHERE DEP="數(shù)學系"

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

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

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

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

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

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

三、代數(shù)系統(tǒng)在計算機科學中的應用

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

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

明碼表 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個英文字母上的置換和置換的復合構成了置換群.

使用字母表替換密碼，通信雙方需要預先約定好共享的保密秘鑰（即字母表）.若由于某種原因（如，原秘鑰受到威脅）需要臨時改變秘鑰，秘鑰交換就成為一個至關重要的問題.置換群可以實現(xiàn)用戶的密鑰交換，為了便于理解，假定通信雙方之間傳輸?shù)男畔⒅挥蠥，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，并把結果發(fā)給用戶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，并把結果發(fā)給用戶A，本例中運算結果為{σ3，σ2，σ4，σ6}；

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

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發(fā)給自己的信息可得：

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）.

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

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

1.圖在計算機網(wǎng)絡設計中的應用

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

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

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

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

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

（2）利用統(tǒng)計結果構造哈夫曼樹；

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

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

五、結束語

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

【參考文獻】

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

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

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

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

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

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

[7] 薩師煊.數(shù)據(jù)庫系統(tǒng)概論[M]，北京：高等教育出版社，2010.

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

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

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