全文字?jǐn)?shù):2946

淺析離散數(shù)學(xué)在計(jì)算機(jī)科學(xué)中的應(yīng)用

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