淺析離散數學在計算機科學中的應用

全文字數:2946

淺析離散數學在計算機科學中的應用

 [摘 要]：離散數學作為有力的數學工具,對計算機的發展,計算機科學的研究起著重大的作用.計算機科學中普遍地采用離散數學中的一些基本概念,基本思想,基本方法,使得計算機科學越趨完善與成熟.本文簡單介紹了離散數學在計算機科學的幾個不同領域中的應用,指出了離散數學在從事計算機及相關科學工作中的重要性 ．
 
 [關鍵詞]：  離散  編譯  關系演算  死鎖  遞歸
 
 離散數學是現代數學的一個重要分支,是計算機科學中基礎理論的核心課程.與我們以往接觸的連續數學的不同之處在于:離散數學研究的對象一般都是有限或可數個元素,并且是以研究離散量的結構和相互之間的關系為主要目標的①,因此,它充分描述了計算機科學的離散性特點.離散數學是隨著計算機科學的發展而逐步建立的,形成于20世紀70年代初.離散數學與計算機科學中的數據結構操作系統編譯理論算法分析,邏輯設計,系統結構,容錯診斷,機器定理證明等課程聯系緊密②.下面我們就從幾個不同的方面簡單分析一下離散數學在計算機科學中的應用．
 一、圖論在計算機科學中的應用。
 圖論是離散數學中引入的一個重要理論,由此引出了數據結構中兩個重要概念:圖和樹.改變了以往只能對線性結構對象加以分析處理的狀況;有了圖論做理論基礎,我們才可以在編譯程序中用樹來表示源程序語法結構,產生了自頂向下和自下向上這兩種不同的語法分析樹;也正因為有了圖論,在數據庫系統中,我們才可以用樹來組織信息,從而把各信息結點間的復雜關系用一種清晰直觀的方式表示出來;同樣,圖論在操作系統中也得到了充分應用,最典型的例子是我們可以用圖論中的回路來判斷并發進程中是否存在遞歸和死鎖現象,采用這種方法我們可以把一項本來很復雜的工作通過判斷一個有向圖中是否存在回路來加以解決,大大提高了工作效率.
    例 1.已知有四個進程:P1,P2,P3,P4和四個資源:R1,R2,R3,R4,其分配情況如下: 
       P1占有資源 R4且申請資源 R1
       P2占有資源 R1且 申請資源 R2及 R3
       P3占有資源 R2且申請資源 R3
       P4占有資源 R3且申請資源 R1及 R4
       試分析在該過程中有無死鎖現象發生 ．
    解：其資源分配圖為圖 1：
    由圖1當中存在的回路我們很容易得出該過程中有死鎖發生.
    1956年,N.喬姆斯基(Noam．Chomsky)提出 了一種文法的數學模型,該數學模型為有窮自動機奠定了理論基礎.有窮自動機是實現程序編譯過程的基礎核心部分,它的主要任務是準確識別正規集(即識別正規文法所定義的語言和正規式所表示的集合)③,而正規集(也就是我們常說的單詞)是編譯程序的基本組成部分,這一過程為編譯過程中的第一個步驟——詞法分析程序的自動構造找到了特殊的方法和工具,并為接下來編譯的其它五個步驟提供分析與操作對象.
 二、離散數學中的關系及關系運算在計算機科學中的應用。
關系及關系運算是數學領域中的一個基本概念,離散數學中所涉及到的關系及其運算對研究計算機科學中的許多問題如數據庫,數據結構,情報檢索等都是很好的分析工具.我們常見的關系數據