計(jì)算機(jī)科學(xué)中的數(shù)學(xué)教育

摘要：本文提出了一種新的教學(xué)思路，即以“離散”作為計(jì)算機(jī)科學(xué)中數(shù)學(xué)教育的主線，強(qiáng)調(diào)針對(duì)離散數(shù)學(xué)的知識(shí)與技能培養(yǎng)。既采用系統(tǒng)化的離散數(shù)學(xué)課程教學(xué)，又將數(shù)學(xué)思想滲透到具體課程中。教學(xué)實(shí)踐表明，這種以解決問(wèn)題為導(dǎo)向的教學(xué)方案收效良好。

關(guān)鍵詞：數(shù)學(xué)教育；計(jì)算機(jī)科學(xué)；離散數(shù)學(xué)；離散概率；組合數(shù)學(xué)

中圖分類(lèi)號(hào)：G642文獻(xiàn)標(biāo)識(shí)碼：B

1引言

計(jì)算機(jī)科學(xué)(Computer Science，CS)這個(gè)概念若僅從字面上看，可將其理解為研究計(jì)算機(jī)理論的學(xué)科，但它的覆蓋面絕不限于理論，這也是它與理論計(jì)算機(jī)科學(xué)(Theoretical Computer Science，TCS)的區(qū)別。ACM和IEEE聯(lián)合制定的Computing Curricula的總結(jié)報(bào)告認(rèn)為[1]，計(jì)算機(jī)科學(xué)不僅包括理論和算法，而且已經(jīng)延展到智能系統(tǒng)、計(jì)算機(jī)視覺(jué)、生物信息學(xué)等領(lǐng)域研究的前沿。從某種意義上說(shuō)，計(jì)算機(jī)科學(xué)為計(jì)算機(jī)學(xué)科提供思維的工具。

從歷史發(fā)展上看，數(shù)學(xué)在計(jì)算機(jī)科學(xué)的誕生與發(fā)展過(guò)程中發(fā)揮了巨大的作用——不夸張的說(shuō)，數(shù)學(xué)就是計(jì)算機(jī)科學(xué)的基石。事實(shí)上，早期的許多計(jì)算機(jī)科學(xué)系脫胎于數(shù)學(xué)系，而最早的計(jì)算機(jī)更是由Turing， John von Neumann等一大批數(shù)學(xué)家創(chuàng)建而成。時(shí)至今日，計(jì)算機(jī)科學(xué)的發(fā)展越發(fā)迅速，由此帶動(dòng)的計(jì)算機(jī)技術(shù)的發(fā)展更是給整個(gè)世界帶來(lái)革命性的變化。在此背景下，學(xué)習(xí)哪些數(shù)學(xué)知識(shí)，以及如何學(xué)習(xí)它們才能促進(jìn)對(duì)計(jì)算機(jī)科學(xué)的掌握，進(jìn)而更好的利用它來(lái)解決實(shí)際問(wèn)題，都是非常值得思考的問(wèn)題。

2“離散”的數(shù)學(xué)

在計(jì)算機(jī)系統(tǒng)中，最基本的假設(shè)就是它以二進(jìn)制來(lái)表示數(shù)據(jù)，即所有信息都要被轉(zhuǎn)換成0和1的組合。由于早期電子器件功能上的局限性，只有采用二進(jìn)制才能準(zhǔn)確的表示信息，但計(jì)算機(jī)發(fā)展到現(xiàn)在，二進(jìn)制已成為難以更改的標(biāo)準(zhǔn)。因此計(jì)算機(jī)自從誕生之日起，它就和連續(xù)型的數(shù)學(xué)劃清了界限。當(dāng)然，連續(xù)型的數(shù)學(xué)在計(jì)算機(jī)上只要被“翻譯”成二進(jìn)制，也就是連續(xù)量轉(zhuǎn)變成離散量后，即可被計(jì)算機(jī)理解和操作。所以作為計(jì)算機(jī)科學(xué)基石的數(shù)學(xué)，更確切地講，應(yīng)該是離散數(shù)學(xué)。在ACM和IEEE聯(lián)合制定的CC2005教學(xué)計(jì)劃的CS部分(即CC2001)中[1]，離散數(shù)學(xué)的內(nèi)容被稱(chēng)為Discrete Structures(簡(jiǎn)稱(chēng)DS)，它排在14個(gè)主要領(lǐng)域的首位，其重要性由此可見(jiàn)一斑。

CC2001所列DS的主要內(nèi)容是：

DS1. Functions， Relations， and Sets；

DS2. Basic Logic；

DS3. Proof Techniques；

DS4. Basics of Counting；

DS5. Graphs and Trees；

DS6. Discrete Probability.

CC2001教學(xué)計(jì)劃的目標(biāo)就是服務(wù)于計(jì)算機(jī)科學(xué)，而這些精選的內(nèi)容實(shí)際上也都是在計(jì)算機(jī)科學(xué)中應(yīng)用廣泛的數(shù)學(xué)知識(shí)。如數(shù)理邏輯(DS2)是計(jì)算機(jī)科學(xué)乃至整個(gè)計(jì)算機(jī)領(lǐng)域中最基礎(chǔ)的知識(shí)；又如進(jìn)行復(fù)雜的算法分析就必須掌握基本的計(jì)數(shù)原理(DS4)。

從我們的教學(xué)經(jīng)驗(yàn)上來(lái)看，若要總體把握這些內(nèi)容必須緊扣“離散”二字。突出“離散”并不是為了標(biāo)新立異，而是它確與“連續(xù)”有所區(qū)別。處理離散問(wèn)題有一些特殊之處，因而需要補(bǔ)充專(zhuān)門(mén)針對(duì)離散問(wèn)題的知識(shí)與技能。

例如 的 記號(hào)問(wèn)題，其結(jié)論在堆排序等許多算法的分析中都非常重要。此問(wèn)題雖然不甚復(fù)雜，但其處理方式比較特殊，在教學(xué)中若不單獨(dú)提出，學(xué)生難以自行證明。此外，如果再進(jìn)一步討論利用積分給出其上下界限，則可讓學(xué)生獲得處理這類(lèi)問(wèn)題一般性的方法。這種方法在微積分中不算很難的內(nèi)容，但它在漸進(jìn)分析中相當(dāng)重要，學(xué)生對(duì)其若有一定量的訓(xùn)練，可為今后的學(xué)習(xí)帶來(lái)相當(dāng)大的便利。

又如考察樹(shù)的計(jì)數(shù)時(shí)，需要具備組合數(shù)學(xué)中的生成函數(shù)等知識(shí)，這些在DS4(Basics of Counting)中都有體現(xiàn)。事實(shí)上，DS4不但提供了基本的組合知識(shí)，還給出了計(jì)數(shù)的一般性方法。在這些計(jì)數(shù)原則的指導(dǎo)下，既能快速得到結(jié)果，還能避免多算、少算等各種在計(jì)數(shù)中易犯的錯(cuò)誤?；趯?duì)組合數(shù)學(xué)地位的正確認(rèn)識(shí)，國(guó)外許多教材在內(nèi)容的取舍上已經(jīng)做出了表率。如Lovász等編寫(xiě)的Discrete Mathematics[2]就給組合數(shù)學(xué)分配了較大的篇幅，同時(shí)還就其在計(jì)算機(jī)科學(xué)中的應(yīng)用給出許多實(shí)例。姚期智先生在清華開(kāi)設(shè)“理論計(jì)算機(jī)科學(xué)”課程時(shí)，即將此書(shū)列為教材。

3按需定學(xué)，現(xiàn)學(xué)現(xiàn)用

雖然離散數(shù)學(xué)的范圍看上去比傳統(tǒng)數(shù)學(xué)要窄，但它包含的內(nèi)容卻相當(dāng)豐富，甚至可以用“龐雜”來(lái)形容。而CC2001教學(xué)計(jì)劃的安排充分體現(xiàn)了美國(guó)教育界“現(xiàn)學(xué)現(xiàn)用”的教學(xué)思想，精心挑選出在計(jì)算機(jī)科學(xué)中有著廣泛應(yīng)用的那些內(nèi)容。于是，詳細(xì)講解這些知識(shí)并緊扣其在計(jì)算機(jī)科學(xué)中的應(yīng)用，必將為學(xué)生在今后的學(xué)習(xí)中打下堅(jiān)實(shí)的基礎(chǔ)。

例如許多國(guó)外的離散數(shù)學(xué)教材中特別強(qiáng)調(diào)循環(huán)不變量(Loop Invariants)的使用[3， 4]，還以一些例子來(lái)證明某些程序的正確性。從我們的教學(xué)實(shí)踐來(lái)看，學(xué)生在編寫(xiě)程序時(shí)總會(huì)給出一些解決方案，但他們認(rèn)為自己“算法”的正確性是不言自明的。事實(shí)上，這些“新算法”大多是錯(cuò)的，這是由于他們對(duì)“證明”缺乏基本的理念。所以，要求學(xué)生進(jìn)行斷言式的程序正確性證明是相當(dāng)困難的。如果從循環(huán)不變量這個(gè)概念入手，先利用它證明一些簡(jiǎn)單的程序段，爾后則可逐步加深學(xué)生對(duì)程序正確性的理解。在講解快速排序算法的劃分步驟時(shí)，我們特別突出了Hoare在設(shè)計(jì)此算法時(shí)所遵循的循環(huán)不變量，學(xué)生對(duì)此反響甚好。對(duì)于更復(fù)雜的算法，我們著重以歸納法來(lái)統(tǒng)一算法的設(shè)計(jì)思路[5]，并以此證明其正確性。這種由淺入深的教學(xué)方式改善了教學(xué)效果：不但加深了學(xué)生對(duì)程序正確性的理解，而且也提高了他們對(duì)算法的認(rèn)識(shí)深度。

又如在程序設(shè)計(jì)時(shí)，若能使用所學(xué)到的數(shù)理邏輯知識(shí)，則可對(duì)程序進(jìn)行精簡(jiǎn)。下面這段程序針對(duì)不同的條件執(zhí)行相應(yīng)的函數(shù)：

可利用數(shù)理邏輯的知識(shí)將其化簡(jiǎn)為效率更高的形式[6]：

我們?cè)陔x散數(shù)學(xué)課程相關(guān)內(nèi)容的教學(xué)中補(bǔ)充了這些不甚復(fù)雜的應(yīng)用實(shí)例，不但引起了學(xué)生的興趣，而且能讓他們更加深入的理解所學(xué)內(nèi)容。

4教學(xué)方案

針對(duì)教學(xué)實(shí)際情況，我們?cè)陔x散數(shù)學(xué)課程中適當(dāng)補(bǔ)充了離散概率和組合數(shù)學(xué)方面的知識(shí)，以期能為學(xué)生進(jìn)一步學(xué)習(xí)計(jì)算機(jī)科學(xué)打下扎實(shí)、全面的基礎(chǔ)，也收到了良好的效果。當(dāng)然，我們?cè)诮虒W(xué)中對(duì)于我國(guó)離散數(shù)學(xué)中的“常規(guī)”部分如邏輯、代數(shù)和圖論也給予了充分重視。

從目前的研究現(xiàn)狀看，“隨機(jī)”這個(gè)概念已經(jīng)在計(jì)算機(jī)科學(xué)中占據(jù)了相當(dāng)重要的地位。它在算法設(shè)計(jì)、密碼學(xué)、計(jì)算理論、人工智能等領(lǐng)域中都有相當(dāng)豐富的應(yīng)用，CC2001特別列出了DS6即離散概率(Discrete probability)以突出其重要性。國(guó)內(nèi)開(kāi)設(shè)的概率論課程雖已包含了DS6的內(nèi)容，但側(cè)重于連續(xù)變量，并未系統(tǒng)討論離散變量。此外，對(duì)離散概率的講授若無(wú)一定的深度和廣度，還會(huì)對(duì)研究生的后續(xù)課程如概率算法等的學(xué)習(xí)產(chǎn)生一定的障礙。所幸，概率論權(quán)威Feller的名著《概率論及其應(yīng)用》[7]涵蓋了這方面的基本內(nèi)容。該書(shū)不僅包括了概率論的基本知識(shí)，更深入討論了隨機(jī)行走(Random walk)、馬爾可夫鏈和博弈問(wèn)題，這些內(nèi)容都是概率算法和算法博弈論必備的基礎(chǔ)知識(shí)。該書(shū)的最后一版雖于1970年出版，但時(shí)至今日依然是案頭必備的參考書(shū)。MIT的David Karger教授的話[8]給出了最好的注解——This book is fairly old but adorns the shelves of most theoretical computer scientists.

不過(guò)在實(shí)際教學(xué)中，我們發(fā)現(xiàn)離散概率的內(nèi)容相當(dāng)難處理：一是此部分應(yīng)用廣泛，由于學(xué)時(shí)所限不可能講授太多內(nèi)容；二是思想過(guò)于深刻，學(xué)生難以理解；三是有些內(nèi)容與概率論課程重復(fù)。事實(shí)上，國(guó)外的一些大學(xué)已經(jīng)單獨(dú)開(kāi)設(shè)了“概率與計(jì)算”這門(mén)課程[9， 10]，而且此課程已有成熟的教材[11]。對(duì)于離散概率的內(nèi)容，我們目前的處理方法是：系統(tǒng)復(fù)習(xí)、梳理離散變量的相關(guān)內(nèi)容；講解針對(duì)離散變量的基本處理技巧；選擇了一些應(yīng)用實(shí)例如Monte Carlo方法進(jìn)行分析；更深入的內(nèi)容則讓學(xué)生自學(xué)或改為研究生階段的課程。

需要特別指出的是，以組合數(shù)學(xué)作為線索，可以將DS4、DS5、DS6緊密結(jié)合起來(lái)，一方面組合與圖論本身就具備密切的聯(lián)系；另一方面以組合為基礎(chǔ)的概率空間正是離散概率的要義所在。從實(shí)踐的角度看，大多數(shù)算法都是組合優(yōu)化算法或圖論算法，還具有相當(dāng)強(qiáng)的實(shí)際背景，學(xué)生看到自己能解決實(shí)際問(wèn)題必然產(chǎn)生強(qiáng)烈的自豪感。這種激勵(lì)提高了學(xué)生學(xué)習(xí)的積極性，而且也讓他們獲得了更多的思考樂(lè)趣。

此外，密碼學(xué)已成為計(jì)算機(jī)科學(xué)中不可或缺的組成部分，而作為現(xiàn)代密碼學(xué)的基礎(chǔ)，數(shù)論知識(shí)的重要性更不言而喻。在教學(xué)中適當(dāng)加入一些初等數(shù)論的知識(shí)也很必要，但內(nèi)容的取舍需要視情況而定。由于離散數(shù)學(xué)的學(xué)時(shí)有限，內(nèi)容過(guò)多是教學(xué)的主要難題。此難題不僅存在于數(shù)論部分內(nèi)容的選擇，在抽象代數(shù)部分體現(xiàn)的尤為明顯。我們認(rèn)為，對(duì)于大多數(shù)學(xué)生來(lái)說(shuō)，學(xué)習(xí)計(jì)算機(jī)科學(xué)應(yīng)主要學(xué)習(xí)如何解決問(wèn)題(How to solve it)，換言之，計(jì)算機(jī)科學(xué)是關(guān)于算法的科學(xué)。關(guān)于這一點(diǎn)，著名計(jì)算機(jī)科學(xué)家Knuth早已有過(guò)明確定義——Computer science is the study of algorithms[12]。解決問(wèn)題也即尋求問(wèn)題的算法不僅實(shí)用，也相對(duì)易于理解。因此，CC2001中對(duì)于DS的內(nèi)容選擇是合適的，我們應(yīng)以這些內(nèi)容為主。而在后續(xù)的課程的教學(xué)中，教師可以列出一些面向計(jì)算機(jī)科學(xué)的數(shù)論和代數(shù)參考書(shū)，如文獻(xiàn)[13]就是一部相當(dāng)優(yōu)秀的著作。這種講授方式不僅節(jié)約了時(shí)間，而且有利于不同研究方向的學(xué)生進(jìn)行自由選擇。

5結(jié)論

離散數(shù)學(xué)是計(jì)算機(jī)科學(xué)的基石，掌握并運(yùn)用它是進(jìn)行計(jì)算機(jī)科學(xué)的學(xué)習(xí)和研究的必要條件。許多著名的計(jì)算機(jī)科學(xué)家如Knuth， Hoare， Karp等都出身于數(shù)學(xué)專(zhuān)業(yè)，這說(shuō)明數(shù)學(xué)方面的各種積累確實(shí)對(duì)計(jì)算機(jī)科學(xué)的學(xué)習(xí)和研究能起到積極的促進(jìn)作用。為此，我們認(rèn)真消化CC2001中關(guān)于DS部分的課程大綱并結(jié)合教學(xué)實(shí)踐，一方面通過(guò)系統(tǒng)的離散數(shù)學(xué)課程讓學(xué)生掌握必備的基礎(chǔ)知識(shí)，另一方面結(jié)合多樣的應(yīng)用實(shí)例將數(shù)學(xué)的思想滲透到專(zhuān)業(yè)課程的教學(xué)中。這種理論與實(shí)踐結(jié)合的教學(xué)方法不僅可以加深對(duì)數(shù)學(xué)理論的理解，更重要的是它能極大的促進(jìn)對(duì)計(jì)算機(jī)科學(xué)的學(xué)習(xí)。教學(xué)實(shí)踐表明，我們的方案不僅節(jié)約了寶貴的教學(xué)時(shí)間，還取得了相當(dāng)好的效果。

當(dāng)然，重視“離散”并不意味著在了解、掌握和應(yīng)用計(jì)算機(jī)的學(xué)習(xí)過(guò)程中可以置“連續(xù)”于不顧。恰恰相反，這些“連續(xù)”的數(shù)學(xué)如微積分、線性代數(shù)等課程，在培養(yǎng)學(xué)生的數(shù)學(xué)思維能力以及運(yùn)用數(shù)學(xué)知識(shí)解決問(wèn)題的意識(shí)方面，具有無(wú)可替代的基礎(chǔ)作用。此外，在數(shù)學(xué)基礎(chǔ)課程的教學(xué)過(guò)程中，若能經(jīng)常借助計(jì)算機(jī)開(kāi)展數(shù)學(xué)實(shí)驗(yàn)，更可收到“學(xué)用相長(zhǎng)”的效果。

由于計(jì)算機(jī)科學(xué)仍在不斷發(fā)展，與其相關(guān)的數(shù)學(xué)教育問(wèn)題還會(huì)遇到新的問(wèn)題，這些都有待于我們?cè)趯?lái)的教學(xué)中不斷探索、不斷創(chuàng)新。

參考文獻(xiàn)：

[1] Computing Curricula 2005 [EB/OL]. http://www.acm.org/education/curricula.html.

[2] L. Lovász， J. Pelikán， K. Vesztergombi. Discrete Mathematics [M]. Springer-Verlag， New York， 2003.

[3] Susanna S. Epp. Discrete Mathematics with Applications (3rd Edition)[M]. Brooks Cole，2003.

[4] Kenneth H. Rosen. 袁崇義譯. 離散數(shù)學(xué)及其應(yīng)用(第5版)[M]. 北京:機(jī)械工業(yè)出版社，2007.

[5] Udi Manber. Algorithms: A Creative Approach[M]. Addison Wesley，1989.

[6] 謝勰. 程序設(shè)計(jì)中的邏輯分解技術(shù)[J]. 西安郵電學(xué)院學(xué)報(bào)，2007，12(3):98-100.

[7] William Feller. 胡迪鶴譯. 概率論及其應(yīng)用[M]. 北京:人民郵電出版社，2006.

[8] David Karger. Randomized Algorithms Syllabus， MIT Course [EB/OL].

http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-856JRandomized-AlgorithmsFall2002/Syllabus/index.htm

[9] Probability and Computing， CMU Course 15-359 [EB/OL].http://www.cs.cmu.edu/~15359/

[10] Probabilistic Methods in Computer Science， Brown Course CS 155 [EB/OL].

http://www.cs.brown.edu/courses/cs155/

[11] Michael Mitzenmacher， Eli Upfal. 史道濟(jì) 等譯. 概率與計(jì)算[M]. 北京:機(jī)械工業(yè)出版社，2007.

[12] Donald E. Knuth. Computer Science and its Relation to Mathematics [J]. American Mathematical Monthly， 1974， 81(4): 323-343.

[13] Victor Shoup. A Computational Introduction to Number Theory and Algebra [M]. Cambridge University Press， 2005.