崔艷榮,陳 勇,黃艷娟

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

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

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

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

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

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

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

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

2 集合論在計算機(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ù)值計算來處理的問題,卻可以用集合來處理。因此,集合論在程序語言、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫與知識庫、形式語言和人工智能等領(lǐng)域得到了廣泛應(yīng)用。

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

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

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

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

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

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

5 結(jié) 語

數(shù)理邏輯、集合論、代數(shù)系統(tǒng)和圖論是 《離散數(shù)學(xué)》的4大部分,筆者分析了上述內(nèi)容在計算機(jī)科學(xué)中的應(yīng)用。在 《離散數(shù)學(xué)》的教學(xué)中,應(yīng)根據(jù)不同的知識點(diǎn),給學(xué)生分析與講解 《離散數(shù)學(xué)》在計算機(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),孫樹樸.圖論及其在計算機(jī)科學(xué)中的應(yīng)用[M].北京:中國礦業(yè)大學(xué)出版社,1995.