崔艷榮,陳 勇,黃艷娟

(長(zhǎng)江大學(xué)計(jì)算機(jī)科學(xué)學(xué)院,湖北荊州434023)

《離散數(shù)學(xué)》是計(jì)算機(jī)科學(xué)核心基礎(chǔ)課程,包含數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論4部分,這4部分從不同的角度出發(fā),研究各種離散量之間數(shù)與形的關(guān)系[1]。計(jì)算機(jī)科學(xué)解決的正是離散量的問(wèn)題,因而 《離散數(shù)學(xué)》在計(jì)算機(jī)科學(xué)發(fā)展中起作不可替代的作用。許多學(xué)生在學(xué)習(xí) 《離散數(shù)學(xué)》的時(shí)候,只把 《離散數(shù)學(xué)》當(dāng)成一門(mén)純數(shù)學(xué)來(lái)對(duì)待,不了解其與計(jì)算機(jī)科學(xué)的關(guān)系。為此,筆者從數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論4個(gè)方面闡述 《離散數(shù)學(xué)》與計(jì)算機(jī)科學(xué)的聯(lián)系及其在計(jì)算機(jī)科學(xué)中的應(yīng)用。

1 數(shù)理邏輯在計(jì)算機(jī)科學(xué)中的應(yīng)用

數(shù)理邏輯是一門(mén)研究推理的邏輯學(xué)科,它為確定一個(gè)給出的論證是否有效提供各種法則和技巧,在計(jì)算機(jī)科學(xué)里用來(lái)檢驗(yàn)程序的正確性和證明定理,同時(shí)在計(jì)算機(jī)科學(xué)的計(jì)算理論、算法分析與設(shè)計(jì)、程序設(shè)計(jì)、人工智能、計(jì)算機(jī)硬件系統(tǒng)等方面有著重要作用[2]。具體包括如下幾方面:

1)為計(jì)算機(jī)模型和可計(jì)算性的研究提供依據(jù) 數(shù)理邏輯中的可計(jì)算謂詞和計(jì)算模型中的可計(jì)算函數(shù)是等價(jià)的,互相可以轉(zhuǎn)化,計(jì)算可以用函數(shù)演算來(lái)表達(dá),也可以用邏輯系統(tǒng)來(lái)表達(dá)。邏輯系統(tǒng)能通過(guò)自身的無(wú)矛盾性保證這樣一種計(jì)算模型是合理的,這就為圖靈機(jī)及與它等價(jià)的計(jì)算模型提供了堅(jiān)實(shí)的邏輯基礎(chǔ)。

2)為計(jì)算機(jī)的設(shè)計(jì)與制造提供依據(jù) 計(jì)算機(jī)的各種運(yùn)算是通過(guò)數(shù)字邏輯技術(shù)實(shí)現(xiàn)的,而代數(shù)和布爾代數(shù)是數(shù)字邏輯的理論基礎(chǔ),布爾代數(shù)在形式演算方面雖然使用了代數(shù)的方法,但其內(nèi)容的實(shí)質(zhì)仍然是邏輯。

3)為計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言提供主要思想 計(jì)算機(jī)程序設(shè)計(jì)語(yǔ)言的理論基礎(chǔ)是形式語(yǔ)言、自動(dòng)機(jī)與形式語(yǔ)義學(xué),數(shù)理邏輯的代數(shù)為形式語(yǔ)言、自動(dòng)機(jī)和形式語(yǔ)義學(xué)提供了主要思想和方法,程序設(shè)計(jì)語(yǔ)言中的許多機(jī)制和方法,如子程序調(diào)用中的參數(shù)代換、賦值等都出自數(shù)理邏輯的方法。

此外,在語(yǔ)言的語(yǔ)義研究中,4種語(yǔ)義方法最終可歸結(jié)為代數(shù)和邏輯的方法,而且,程序的語(yǔ)義及其正確性的理論基礎(chǔ)仍然是數(shù)理邏輯或者進(jìn)一步的模型論。另外,在計(jì)算機(jī)體系結(jié)構(gòu)的研究中,像容錯(cuò)計(jì)算機(jī)系統(tǒng)、Transputer計(jì)算機(jī)、陣列式向量計(jì)算機(jī)、可變結(jié)構(gòu)的計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)及其計(jì)算模型等都直接或間接與邏輯及其代數(shù)密不可分。

2 集合論在計(jì)算機(jī)科學(xué)中的應(yīng)用

集合論包括集合、關(guān)系和函數(shù)3部分。

1)集合 集合不僅可以表示數(shù),而且可以像數(shù)一樣進(jìn)行運(yùn)算,還可以用于非數(shù)值信息的表示和處理,如數(shù)據(jù)的增加、刪除、排序以及數(shù)據(jù)間關(guān)系的描述,有些很難用傳統(tǒng)的數(shù)值計(jì)算來(lái)處理的問(wèn)題,卻可以用集合來(lái)處理。因此,集合論在程序語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫(kù)與知識(shí)庫(kù)、形式語(yǔ)言和人工智能等領(lǐng)域得到了廣泛應(yīng)用。

2)關(guān)系 關(guān)系也廣泛地應(yīng)用于計(jì)算機(jī)科學(xué)技術(shù)中,例如計(jì)算機(jī)程序的輸入和輸出關(guān)系、數(shù)據(jù)庫(kù)的數(shù)據(jù)特性關(guān)系和計(jì)算機(jī)語(yǔ)言的字符關(guān)系等,是數(shù)據(jù)結(jié)構(gòu)、情報(bào)檢索、數(shù)據(jù)庫(kù)、算法分析、計(jì)算機(jī)理論等計(jì)算機(jī)領(lǐng)域中的良好數(shù)據(jù)工具。另外,關(guān)系中劃分等價(jià)類(lèi)的思想也可用于求網(wǎng)絡(luò)的最小生成樹(shù)等圖的算法中。

3)函數(shù) 函數(shù)可以看成是一種特殊的關(guān)系,計(jì)算機(jī)中把輸入、輸出間的關(guān)系看成是一種函數(shù)。類(lèi)似地,在開(kāi)關(guān)理論、自動(dòng)機(jī)原理和可計(jì)算性理論等領(lǐng)域中,函數(shù)都有極其廣泛的應(yīng)用,其中雙射函數(shù)是密碼學(xué)中的重要工具。

3 代數(shù)系統(tǒng)在計(jì)算機(jī)科學(xué)中的應(yīng)用

代數(shù)系統(tǒng)是一種數(shù)學(xué)結(jié)構(gòu),代數(shù)的概念和方法是研究計(jì)算機(jī)科學(xué)的重要數(shù)學(xué)工具。在利用計(jì)算機(jī)科學(xué)解決實(shí)際問(wèn)題時(shí)都離不開(kāi)數(shù)學(xué)模型,而構(gòu)造一個(gè)現(xiàn)象或過(guò)程的數(shù)學(xué)模型就需要某種數(shù)學(xué)結(jié)構(gòu),而代數(shù)結(jié)構(gòu)就是最常用的數(shù)學(xué)結(jié)構(gòu)之一。如描述機(jī)器可計(jì)算的函數(shù)、研究算法計(jì)算的復(fù)雜性、刻畫(huà)抽象數(shù)據(jù)結(jié)構(gòu)、程序設(shè)計(jì)語(yǔ)言的語(yǔ)義學(xué)基礎(chǔ)、邏輯電路設(shè)計(jì)和編碼理論等都需要代數(shù)知識(shí)。代數(shù)系統(tǒng)中的群論在計(jì)算機(jī)安全領(lǐng)域得到廣泛關(guān)注,比如有名的橢圓曲線算法,半群在形式語(yǔ)言與自動(dòng)機(jī)中都有具體的應(yīng)用。另外,計(jì)算機(jī)科學(xué)中的有限自動(dòng)機(jī)理論、開(kāi)關(guān)網(wǎng)絡(luò)理論、計(jì)算機(jī)邏輯設(shè)計(jì)等領(lǐng)域都直接地應(yīng)用了布爾代數(shù)的結(jié)論。

4 圖論在計(jì)算機(jī)科學(xué)中的應(yīng)用

圖論在計(jì)算機(jī)科學(xué)中扮演中重要的角色,為計(jì)算機(jī)科學(xué)中的形式語(yǔ)言、數(shù)據(jù)結(jié)構(gòu)、分布式系統(tǒng)、操作系統(tǒng)、計(jì)算機(jī)網(wǎng)絡(luò)等提供了有力的數(shù)學(xué)工具。特別是圖論中的最小支撐樹(shù)、最短通路、最大匹配、網(wǎng)絡(luò)流、中國(guó)郵遞員問(wèn)題和旅行售貨員等問(wèn)題在計(jì)算機(jī)科學(xué)中都有著廣泛的應(yīng)用[3]。

5 結(jié) 語(yǔ)

數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論是 《離散數(shù)學(xué)》的4大部分,筆者分析了上述內(nèi)容在計(jì)算機(jī)科學(xué)中的應(yīng)用。在 《離散數(shù)學(xué)》的教學(xué)中,應(yīng)根據(jù)不同的知識(shí)點(diǎn),給學(xué)生分析與講解 《離散數(shù)學(xué)》在計(jì)算機(jī)科學(xué)中的重要作用,改變學(xué)生把 《離散數(shù)學(xué)》當(dāng)純數(shù)學(xué)學(xué)習(xí)的想法,進(jìn)一步地提高學(xué)生的學(xué)習(xí)興趣,從而取得良好的教學(xué)效果。

[1]傅彥,顧小豐,王慶先,等.離散數(shù)學(xué)及其應(yīng)用[M].北京:高等教育出版社,2007.

[2]傅彥,王麗杰,尚明生,等.離散數(shù)學(xué)實(shí)驗(yàn)與習(xí)題解析[M].北京:高等教育出版社,2007.

[3]周強(qiáng),孫樹(shù)樸.圖論及其在計(jì)算機(jī)科學(xué)中的應(yīng)用[M].北京:中國(guó)礦業(yè)大學(xué)出版社,1995.