《離散數(shù)學(xué)》課程在計算機學(xué)科中的作用及其應(yīng)用

黃 震

（惠州學(xué)院 計算機科學(xué)系，廣東 惠州 516007）

《離散數(shù)學(xué)》課程在計算機學(xué)科中的作用及其應(yīng)用

黃 震

（惠州學(xué)院 計算機科學(xué)系，廣東 惠州 516007）

離散數(shù)學(xué)是計算機科學(xué)的核心基礎(chǔ)理論課，為后續(xù)課程提供必須的理論基礎(chǔ).分析了離散數(shù)學(xué)在計算機學(xué)科中與其他課程之間的關(guān)系，闡述了離散數(shù)學(xué)在計算機領(lǐng)域的實際應(yīng)用.

離散數(shù)學(xué)；計算機；應(yīng)用

離散數(shù)學(xué)是計算機學(xué)科的專業(yè)基礎(chǔ)課，不但為后續(xù)課程提供必須的理論基礎(chǔ)，而且可以培養(yǎng)學(xué)生的抽象思維能力和解決問題的能力.

離散數(shù)學(xué)的教學(xué)內(nèi)容與計算機硬件和軟件都有著密切的關(guān)系，具有鮮明的基礎(chǔ)特點，不僅是數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理、數(shù)字邏輯、編譯原理、人工智能、信息安全等課程的前續(xù)課程，同時以計算機導(dǎo)論和程序設(shè)計基礎(chǔ)作為離散數(shù)學(xué)的先導(dǎo)課程[1].

離散數(shù)學(xué)是計算機應(yīng)用的必不可少的工具.例如數(shù)理邏輯在數(shù)據(jù)模型、計算機語義、人工智能等方面的應(yīng)用，集合論在數(shù)據(jù)庫技術(shù)中的應(yīng)用，代數(shù)系統(tǒng)在信息安全中的密碼學(xué)方面的應(yīng)用，圖論在信息檢索、網(wǎng)絡(luò)布線、指令系統(tǒng)優(yōu)化等方面的應(yīng)用.

1 離散數(shù)學(xué)與其他課程的關(guān)系

1.1 離散數(shù)學(xué)與數(shù)據(jù)結(jié)構(gòu)的關(guān)系

離散數(shù)學(xué)與數(shù)據(jù)結(jié)構(gòu)的關(guān)系非常緊密，數(shù)據(jù)結(jié)構(gòu)課程描述的的對象有四種，分別是線形結(jié)構(gòu)、集合、樹形結(jié)構(gòu)和圖結(jié)構(gòu)，這些對象都是離散數(shù)學(xué)研究的內(nèi)容.線形結(jié)構(gòu)中的線形表、棧、隊列等都是根據(jù)數(shù)據(jù)元素之間關(guān)系的不同而建立的對象，離散數(shù)學(xué)中的關(guān)系這一章就是研究有關(guān)元素之間的不同關(guān)系的內(nèi)容；數(shù)據(jù)結(jié)構(gòu)中的集合對象以及集合的各種運算都是離散數(shù)學(xué)中集合論研究的內(nèi)容；離散數(shù)學(xué)中的樹和圖論的內(nèi)容為數(shù)據(jù)結(jié)構(gòu)中的樹形結(jié)構(gòu)對象和圖結(jié)構(gòu)對象的研究提供了很好的知識基礎(chǔ).

1.2 離散數(shù)學(xué)與數(shù)據(jù)庫原理的關(guān)系

目前數(shù)據(jù)庫原理主要研究的數(shù)據(jù)庫類型是關(guān)系數(shù)據(jù)庫.關(guān)系數(shù)據(jù)庫中的關(guān)系演算和關(guān)系模型需要用到離散數(shù)學(xué)中的謂詞邏輯的知識；關(guān)系數(shù)據(jù)庫的邏輯結(jié)構(gòu)是由行和列構(gòu)成的二維表，表之間的連接操作需要用到離散數(shù)學(xué)中的笛卡兒積的知識，表數(shù)據(jù)的查詢、插入、刪除和修改等操作都需要用到離散數(shù)學(xué)中的關(guān)系代數(shù)理論和數(shù)理邏輯中的知識.

1.3 離散數(shù)學(xué)與數(shù)字邏輯的關(guān)系

數(shù)字邏輯為計算機硬件中的電路設(shè)計提供了重要理論，而離散數(shù)學(xué)中的數(shù)理邏輯部分為數(shù)字邏輯提供了重要的數(shù)學(xué)基礎(chǔ).在離散數(shù)學(xué)中命題邏輯中的聯(lián)結(jié)詞運算可以解決電路設(shè)計中的由高低電平表示的各信號之間的運算以及二進制數(shù)的位運算等問題.

1.4 離散數(shù)學(xué)與編譯原理的關(guān)系

編譯原理和技術(shù)是軟件工程技術(shù)人員很重要的基礎(chǔ)知識，編譯程序是非常復(fù)雜的系統(tǒng)程序，包括詞法分析、語法分析、語義分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成、依賴機器的代碼優(yōu)化7個階段.離散數(shù)學(xué)中的計算模型[2]這一章的語言和文法、有限狀態(tài)機、語言的識別和圖靈機等知識點為編譯程序中的詞法分析和語法分析提供了基礎(chǔ).

1.5 離散數(shù)學(xué)與人工智能的關(guān)系[3]

離散數(shù)學(xué)中數(shù)學(xué)推理和布爾代數(shù)章節(jié)中的知識為早期的人工智能研究領(lǐng)域打下了良好的數(shù)學(xué)基礎(chǔ).謂詞邏輯演算為人工智能學(xué)科提供了一種重要的知識表示方法和推理方法.另外，模糊邏輯的概念也可以用于人工智能.

1.6 離散數(shù)學(xué)與信息安全的關(guān)系

信息安全應(yīng)用方面與離散數(shù)學(xué)也關(guān)系密切，離散數(shù)學(xué)中的代數(shù)系統(tǒng)和初等數(shù)論為密碼學(xué)提供了重要的數(shù)學(xué)基礎(chǔ)，例如凱撒密碼的本質(zhì)就是使用了代數(shù)系統(tǒng)中的群的知識，初等數(shù)論中的歐拉定理和費馬小定理為著名的RSA公鑰密碼體系提供了最直接的數(shù)學(xué)基礎(chǔ).

1.7 離散數(shù)學(xué)與其他課程的關(guān)系

表1 離散數(shù)學(xué)與后續(xù)課程的相關(guān)知識點

離散數(shù)學(xué)除了與以上課程關(guān)系密切，與其他課程也有著非常重要的關(guān)系，這里以表格的形式列出離散數(shù)學(xué)與后續(xù)課程相關(guān)聯(lián)的知識點，如表1所示.

2 離散數(shù)學(xué)的應(yīng)用

離散數(shù)學(xué)課程包括數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論幾個部分，下面分別介紹一下這幾個部分在計算機各方面的應(yīng)用.

2.1 數(shù)理邏輯的應(yīng)用

數(shù)理邏輯是用數(shù)學(xué)方法研究思維規(guī)律的一門學(xué)科，包括命題邏輯、謂詞邏輯和推理理論等知識點.

命題邏輯中的聯(lián)結(jié)詞廣泛應(yīng)用在大量信息的檢索、邏輯運算和位運算中，例如目前大部分網(wǎng)頁檢索引擎都支持布爾檢索，使用NOT、AND、OR等聯(lián)結(jié)詞進行檢索有助于快速找到特定主題的網(wǎng)頁；信息在計算機內(nèi)都表示為0或1構(gòu)成的位串，通過對位串的運算可以對信息進行處理，計算機字位的運算與邏輯中的聯(lián)結(jié)詞的運算規(guī)則是一致的，掌握了聯(lián)結(jié)詞的運算為計算機信息的處理提供了很好的知識基礎(chǔ).在計算機硬件設(shè)計中，使用了聯(lián)結(jié)詞完備集中的與非和或非，使用與非門和或非門設(shè)計邏輯線路，替代了之前的非門、與門和或門的組合，優(yōu)化了邏輯線路.

謂詞邏輯可以表示關(guān)系模型中的關(guān)系操作[4]，用謂詞邏輯表示關(guān)系操作的關(guān)系演算形式是：{s[<屬性表>]│R(s)}，其中R(s)指的是s用該滿足的謂詞，例如要查詢不及格的女同學(xué)的名字，關(guān)系演算的表達式為：{s│s∈student and s.sex=’w’and s.score<60}.

推理理論可以應(yīng)用到計算機語義的理解中，在推理理論中驗證某理論的邏輯正確性時首先需要將其形式化，這樣在邏輯推理時就直接使用邏輯規(guī)則進行推理而不需要理會其具體含義了，在計算機語義中，也可以將其形式化，借助推理理論的方法進行計算機語義的理解.

2.2 集合論的應(yīng)用

集合是由各種不同元素構(gòu)成的，并用統(tǒng)一的方法來處理的對象，集合論包括集合代數(shù)、關(guān)系和函數(shù)等知識點.

集合代數(shù)中的集合的性質(zhì)和集合的運算主要是為其他學(xué)科提供數(shù)學(xué)基礎(chǔ)，現(xiàn)實世界中的數(shù)字、符號、圖像、語音、視頻等各種信息都可以作為數(shù)據(jù)存放到計算機進行處理，這些數(shù)據(jù)就構(gòu)成集合.

關(guān)系是一種特殊的集合，它反映了研究對象之間的聯(lián)系與性質(zhì)，例如關(guān)系數(shù)據(jù)庫模型中，每個數(shù)據(jù)庫都是一個關(guān)系，在計算機程序中輸入和輸出就構(gòu)成一個二元關(guān)系.等價關(guān)系和偏序關(guān)系廣泛的存在于實際應(yīng)用中，例如利用偏序的知識可以解決調(diào)度中的最優(yōu)調(diào)度問題；在軟件工程的軟件測試方法中有一種等價類劃分的方法，即將所有待測試的數(shù)據(jù)構(gòu)成的集合劃分為符合軟件需求規(guī)格和設(shè)計規(guī)定的有效等價類和不符合的無效等價類，因為每個等價類中只需要取一個數(shù)據(jù)代表其所在等價類的其他數(shù)據(jù)進行測試，所以大大提高了軟件測試的效率.

函數(shù)的應(yīng)用比較廣泛，例如在密碼學(xué)中的應(yīng)用，公鑰系統(tǒng)中的原理是基于單向陷門函數(shù)，單向陷門函數(shù)滿足3個條件：（1）對于屬于定義域的任意一個x，可以很容易算出F(x)=y，（2）對于幾乎所有屬于值域的任意一個y，則在計算上除非獲得陷門，否則不可能求出x，使得x=F-1(y),（3）若有一額外數(shù)據(jù)z（稱為陷門），則可以很容易的求出x=F-1(z).單向陷門函數(shù)與單向函數(shù)的差異在于可逆與不可逆.若單向陷門函數(shù)存在，則任何單向陷門函數(shù)均可用來設(shè)計公開密鑰密碼系統(tǒng).同時，若單向函數(shù)滿足交換性，則單向函數(shù)也可能用來設(shè)計公開密鑰密碼系統(tǒng).

2.3 代數(shù)系統(tǒng)的應(yīng)用

代數(shù)系統(tǒng)研究的是集合、該集合中元素的運算和一些特殊元素，其中群是一種特殊的代數(shù)系統(tǒng)，具有可結(jié)合、有單位元、每個元素都有逆元等性質(zhì).凱撒密碼系統(tǒng)的原理是將字母表的字母右移n個位置，n即key，然后對字母表長度l作模運算，加密形式為：c=(m+n)mod l，解密形式為：m=(c-n)mod l，其實凱撒密碼就是建立在26個字母之上，字母與key運算的剩余模群.橢圓曲線加密算法是利用橢圓曲線離散對數(shù)問題，橢圓曲線離散對數(shù)問題定義如下：給定素數(shù)p和橢圓曲線E，對Q=kP,在已知P,Q的情況下求出小于p的正整數(shù)k，由于已知k和P計算Q比較容易，而由Q和P計算k則比較困難，至今沒有有效的方法來解決這個問題，這正是該加密算法的原理所在.

2.4 圖論的應(yīng)用

圖論在計算機領(lǐng)域的應(yīng)用廣泛，例如利用哈密頓圖求最短路徑問題和旅行商最優(yōu)問題，利用哈夫曼算法對指令系統(tǒng)優(yōu)化以及提高通信效率等問題[5].在計算機體系結(jié)構(gòu)中，指令系統(tǒng)的優(yōu)化非常重要，因為可以提高整個計算機系統(tǒng)的性能，指令系統(tǒng)的優(yōu)化方法很多，其中一種就是對指令的格式進行優(yōu)化，是指用最短的位數(shù)來表示指令的操作碼和地址碼，使程序中的指令的平均字長最短，可以使用哈夫曼算法對指令的格式進行優(yōu)化，利用哈夫曼算法可以構(gòu)造出最優(yōu)二叉樹，而二叉樹的權(quán)是最小的，即可以實現(xiàn)指令的平均字長最短.同樣的原理利用哈夫曼算法構(gòu)造最優(yōu)二叉樹可以解決通信中傳輸二進制數(shù)最優(yōu)效率的問題.

3 結(jié)束語

離散數(shù)學(xué)在計算機領(lǐng)域的作用非常重要，計算機科學(xué)中普遍采用離散數(shù)學(xué)中的一些基本概念、知識點和研究方法.離散數(shù)學(xué)課程不但為其他課程提供必要的理論基礎(chǔ)，在計算機學(xué)科中有著廣泛的應(yīng)用，而且通過學(xué)習(xí)離散數(shù)學(xué)的思想和方法也提高了學(xué)生的邏輯思維能力和創(chuàng)造性思維能力.為了更好的學(xué)習(xí)計算機學(xué)科的后續(xù)課程以及解決計算機科學(xué)中遇到的實際問題必須學(xué)好離散數(shù)學(xué)課程.

〔1〕朱家義，苗國義，等.基于知識關(guān)系的離散數(shù)學(xué)教學(xué)內(nèi)容設(shè)計[J].計算機教育,2010(18):98-100.

〔2〕Kenneth H.Rosen.離散數(shù)學(xué)及其應(yīng)用[M].北京：機械工業(yè)出版社，2006.

〔3〕陳敏，李澤軍.離散數(shù)學(xué)在計算機學(xué)科中的應(yīng)用[J].電腦知識與技術(shù),2009,5(1):251-252.

〔4〕龔靜，王青川.數(shù)理邏輯在計算機科學(xué)中的應(yīng)用淺析[J].青?？萍?2004(6):53-54.

〔5〕屈婉玲，耿素云，等.離散數(shù)學(xué)[M].北京：高等教育出版社，2008.

G642

A

1673-260X（2011）05-0264-02

惠州學(xué)院教研教改項目《離散數(shù)學(xué)課程結(jié)合實踐教學(xué)的教學(xué)模式研究》