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

關鍵詞：數(shù)學教育；計算機科學；離散數(shù)學；離散概率；組合數(shù)學

中圖分類號：G642文獻標識碼：B

1引言

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

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

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

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

CC2001所列DS的主要內容是：

DS1. Functions， Relations， and Sets；

DS2. Basic Logic；

DS3. Proof Techniques；

DS4. Basics of Counting；

DS5. Graphs and Trees；

DS6. Discrete Probability.

CC2001教學計劃的目標就是服務于計算機科學，而這些精選的內容實際上也都是在計算機科學中應用廣泛的數(shù)學知識。如數(shù)理邏輯(DS2)是計算機科學乃至整個計算機領域中最基礎的知識；又如進行復雜的算法分析就必須掌握基本的計數(shù)原理(DS4)。

從我們的教學經(jīng)驗上來看，若要總體把握這些內容必須緊扣“離散”二字。突出“離散”并不是為了標新立異，而是它確與“連續(xù)”有所區(qū)別。處理離散問題有一些特殊之處，因而需要補充專門針對離散問題的知識與技能。

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

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

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

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

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

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

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

我們在離散數(shù)學課程相關內容的教學中補充了這些不甚復雜的應用實例，不但引起了學生的興趣，而且能讓他們更加深入的理解所學內容。

4教學方案

針對教學實際情況，我們在離散數(shù)學課程中適當補充了離散概率和組合數(shù)學方面的知識，以期能為學生進一步學習計算機科學打下扎實、全面的基礎，也收到了良好的效果。當然，我們在教學中對于我國離散數(shù)學中的“常規(guī)”部分如邏輯、代數(shù)和圖論也給予了充分重視。

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

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

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

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

5結論

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

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

由于計算機科學仍在不斷發(fā)展，與其相關的數(shù)學教育問題還會遇到新的問題，這些都有待于我們在將來的教學中不斷探索、不斷創(chuàng)新。

參考文獻：

[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ù)學及其應用(第5版)[M]. 北京:機械工業(yè)出版社，2007.

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

[6] 謝勰. 程序設計中的邏輯分解技術[J]. 西安郵電學院學報，2007，12(3):98-100.

[7] William Feller. 胡迪鶴譯. 概率論及其應用[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. 史道濟 等譯. 概率與計算[M]. 北京:機械工業(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.