《離散數學》課程在計算機學科中的作用及其應用

黃 震

（惠州學院 計算機科學系，廣東 惠州 516007）

《離散數學》課程在計算機學科中的作用及其應用

黃 震

（惠州學院 計算機科學系，廣東 惠州 516007）

離散數學是計算機科學的核心基礎理論課，為后續課程提供必須的理論基礎.分析了離散數學在計算機學科中與其他課程之間的關系，闡述了離散數學在計算機領域的實際應用.

離散數學；計算機；應用

離散數學是計算機學科的專業基礎課，不但為后續課程提供必須的理論基礎，而且可以培養學生的抽象思維能力和解決問題的能力.

離散數學的教學內容與計算機硬件和軟件都有著密切的關系，具有鮮明的基礎特點，不僅是數據結構、數據庫原理、數字邏輯、編譯原理、人工智能、信息安全等課程的前續課程，同時以計算機導論和程序設計基礎作為離散數學的先導課程[1].

離散數學是計算機應用的必不可少的工具.例如數理邏輯在數據模型、計算機語義、人工智能等方面的應用，集合論在數據庫技術中的應用，代數系統在信息安全中的密碼學方面的應用，圖論在信息檢索、網絡布線、指令系統優化等方面的應用.

1 離散數學與其他課程的關系

1.1 離散數學與數據結構的關系

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

1.2 離散數學與數據庫原理的關系

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

1.3 離散數學與數字邏輯的關系

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

1.4 離散數學與編譯原理的關系

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

1.5 離散數學與人工智能的關系[3]

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

1.6 離散數學與信息安全的關系

信息安全應用方面與離散數學也關系密切，離散數學中的代數系統和初等數論為密碼學提供了重要的數學基礎，例如凱撒密碼的本質就是使用了代數系統中的群的知識，初等數論中的歐拉定理和費馬小定理為著名的RSA公鑰密碼體系提供了最直接的數學基礎.

1.7 離散數學與其他課程的關系

表1 離散數學與后續課程的相關知識點

離散數學除了與以上課程關系密切，與其他課程也有著非常重要的關系，這里以表格的形式列出離散數學與后續課程相關聯的知識點，如表1所示.

2 離散數學的應用

離散數學課程包括數理邏輯、集合論、代數系統和圖論幾個部分，下面分別介紹一下這幾個部分在計算機各方面的應用.

2.1 數理邏輯的應用

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

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

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

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

2.2 集合論的應用

集合是由各種不同元素構成的，并用統一的方法來處理的對象，集合論包括集合代數、關系和函數等知識點.

集合代數中的集合的性質和集合的運算主要是為其他學科提供數學基礎，現實世界中的數字、符號、圖像、語音、視頻等各種信息都可以作為數據存放到計算機進行處理，這些數據就構成集合.

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

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

2.3 代數系統的應用

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

2.4 圖論的應用

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

3 結束語

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

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

〔2〕Kenneth H.Rosen.離散數學及其應用[M].北京：機械工業出版社，2006.

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

〔4〕龔靜，王青川.數理邏輯在計算機科學中的應用淺析[J].青海科技,2004(6):53-54.

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

G642

A

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

惠州學院教研教改項目《離散數學課程結合實踐教學的教學模式研究》