每個學校本系里都會開一門離散數(shù)學,涉及集合論,圖論,和抽象代數(shù),數(shù)理邏輯。不過,這么多內容擠在離散數(shù)學一門課里,是否時間太緊了點?另外,計算機系學生不懂組合和數(shù)論,也是巨大的缺陷。要做理論,不懂組合或者數(shù)論吃虧可就太大了。從理想的狀態(tài)來看,最好分開六門課:集合,邏輯圖論,組合,代數(shù),數(shù)論。這個當然不現(xiàn)實,因為沒那么多課時。也許將來可以開三門課:集合與邏輯,圖論與組合,代數(shù)與數(shù)論。(這方面我們學校已經(jīng)著手開始做了)
不管課怎么開,學生總一樣要學。下面分別談談上面的三組內容。
古典集合論,北師大出過一本《基礎集合論》不錯。 數(shù)理邏輯,中科院軟件所陸鐘萬教授的《面向計算機科學的數(shù)理邏輯》就不錯?,F(xiàn)在可以找到陸鐘萬教授的講課錄像,自己去看看吧??偟膩碚f,學集合/邏輯起手不難,普通高中生都能看懂。但越往后越感覺深不可測。
學完以上各書之后,如果你還有精力興趣進一步深究,那么可以試一下GTM系列中的《Introduction to Axiomatic Set Theory》和《A Course of Mathematical Logic》。這兩本都有世界圖書出版社的引進版。你如果能搞定這兩本,可以說在邏輯方面真正入了門,也就不用再浪費時間聽我瞎侃了。
據(jù)說全中國最多只有三十個人懂圖論。此言不虛。圖論這東東,技巧性太強,幾乎每個問題都有一個獨特的方法,讓人頭痛。不過這也正是它魅力所在:只要你有創(chuàng)造性,它就能給你成就感。我的導師說,圖論里面隨便揪一塊東西就可以寫篇論文。大家可以體會里面內容之深廣了吧!國內的圖論書中,王樹禾老師的“圖論及其算法”非常成功。一方面,其內容在國內教材里算非常全面的。另一方面,其對算法的強調非常適合計算機系(本來就是科大計算機系教材)。有了這本書為主,再參考幾本翻譯的,如Bondy & Murty的《圖論及其應用》,人民郵電出版社翻譯的《圖論和電路網(wǎng)絡》等等,就馬馬虎虎,對本科生足夠了。再進一步,世界圖書引進有GTM系列的"Modern Graph Theory"。此書確實經(jīng)典!國內好象還有一家出版了個翻譯版。不過,學到這個層次,還是讀原版好。搞定這本書,也標志著圖論入了門。
離散數(shù)學方面我們北京工業(yè)大學實驗學院有個世界級的專家,叫邵學才,復旦大學概率論畢業(yè)的,教過高等數(shù)學,線性代數(shù),概率論,最后轉向離散數(shù)學,出版著作無數(shù),論文集新加坡有一本,堪稱經(jīng)典,大家想學離散數(shù)學的真諦不妨找來看看。這老師的課我專門去聽過,極為經(jīng)典。不過你要從他的不經(jīng)意的話中去挖掘精髓。在同他的交談當中我又深刻地發(fā)現(xiàn)一個問題,雖說邵先生寫書無數(shù),但依他自己的說法每本都差不多,我實在覺得詫異,他說主要是有大綱的限制,不便多寫。這就難怪了,很少聽說國外寫書還要依據(jù)個什么大綱(就算有,內容也寬泛的多),不敢越雷池半步,這樣不是看誰的都一樣了。外版的書好就好在這里,最新的科技成果里面都有論述,別的先不說,至少是“緊跟時代的理論知識”。
組合感覺沒有太適合的國產(chǎn)書。還是讀Graham和Knuth等人合著的經(jīng)典“具體數(shù)學”吧,西安電子科技大學出版社有翻譯版。 抽象代數(shù),國內經(jīng)典為莫宗堅先生的“代數(shù)學”。此書是北大數(shù)學系教材,深得好評。然而對本科生來說,此書未免太深??梢韵葘W習一些其它的教材,然后再回頭來看“代數(shù)學”。國際上的經(jīng)典可就多了,GTM系列里就有一大堆。推薦一本談不上經(jīng)典,但卻最簡
單的,最容易學的:這本“Introduction to Linear and Abstract Algebra"非常通俗易懂,而且把抽象代數(shù)和線性代數(shù)結合起來,對初學者來說非常理想,我校比較牛的同學都有收藏。
數(shù)論方面,國內有經(jīng)典而且以困難著稱的”初等數(shù)論“(潘氏兄弟著,北大版)。再追溯一點,還有更加經(jīng)典(可以算世界級)并且更加困難的”數(shù)論導引“(華羅庚先生的名著,科學版,九章書店重印,繁體的看起來可能比較困難)。把基礎的幾章搞定一個大概,對本科生來講足夠了。但這只是初等數(shù)論。本科畢業(yè)后要學計算數(shù)論,你必須看英文的書,如Bach的"Introduction to Algorithmic Number Theory"。
計算機科學理論的根本,在于算法。現(xiàn)在很多系里給本科生開設算法設計與分析,確實非常正確。環(huán)顧西方世界,大約沒有一個三流以上計算機系不把算法作為必修的。算法教材目前公認以Corman等著的"Introduction to Algorithms"為最優(yōu)。對入門而言,這一本已經(jīng)足夠,不需要再參考其它書。
計算機硬件學習心得篇2計算機科學和數(shù)學的關系有點奇怪。二三十年以前,計算機科學基本上還是數(shù)學的一個分支。而現(xiàn)在,計算機科學擁有廣泛的研究領域和眾多的研究人員,在很多方面反過來推動數(shù)學發(fā)展,從某種意義上可以說是孩子長得比媽媽還高了。但不管怎么樣,這個孩子身上始終流著母親的血液。這血液是the mathematical underpinning of computer science(計算機科學的數(shù)學基礎),也就是理論計算機科學。原來在東方大學城圖書館中曾經(jīng)看過一本七十年代的譯本(書皮都沒了,可我就愛關注這種書),大概就叫《計算機數(shù)學》。那本書若是放在當時來講決是一本好書,但現(xiàn)在看來,涵蓋的范圍還算廣,深度則差了許多,不過推薦大一的學生倒可以看一看,至少可以使你的計算數(shù)學入入門。
最常和理論計算機科學放在一起的一個詞是什么?答:離散數(shù)學。這兩者的關系是如此密切,以至于它們在不少場合下成為同義詞。(這一點在前面的那本書中也有體現(xiàn))傳統(tǒng)上,數(shù)學是以分析為中心的。數(shù)學系的同學要學習三四個學期的數(shù)學分析,然后是復變函數(shù),實變函數(shù),泛函數(shù)等等。實變和泛函被很多人認為是現(xiàn)代數(shù)學的入門。在物理,化學,工程上應用的,也以分析為主。
隨著計算機科學的出現(xiàn),一些以前不太受到重視的數(shù)學分支突然重要起來。人們發(fā)現(xiàn),這些分支處理的數(shù)學對象與傳統(tǒng)的分析有明顯的區(qū)別:分析研究的問題解決方案是連續(xù)的,因而微分,積分成為基本的運算;而這些分支研究的對象是離散的,因而很少有機會進行此類的計算。人們從而稱這些分支為“離散數(shù)學”。“離散數(shù)學”的名字越來越響亮,最后導致以分析為中心的傳統(tǒng)數(shù)學分支被相對稱為“連續(xù)數(shù)學”。
離散數(shù)學經(jīng)過幾十年發(fā)展,基本上穩(wěn)定下來。一般認為,離散數(shù)學包含以下學科:
1) 集合論,數(shù)理邏輯與元數(shù)學。這是整個數(shù)學的基礎,也是計算機科學的基礎。
2) 圖論,算法圖論;組合數(shù)學,組合算法。計算機科學,尤其是理論計算機科學的核心是
算法,而大量的算法建立在圖和組合的基礎上。
3) 抽象代數(shù)。代數(shù)是無所不在的,本來在數(shù)學中就非常重要。在計算機科學中,人們驚訝地發(fā)現(xiàn)代數(shù)竟然有如此之多的應用。
但是,理論計算機科學僅僅就是在數(shù)學的上面加上“離散”的帽子這么簡單嗎?一直到大約十幾年前,終于有一位大師告訴我們:不是。D.E.Knuth(他有多偉大,我想不用我廢話了)在Stanford開設了一門全新的課程Concrete Mathematics。 Concrete這個詞在這里有兩層含義:
首先:對abstract而言。Knuth認為,傳統(tǒng)數(shù)學研究的對象過于抽象,導致對具體的問題關心不夠。他抱怨說,在研究中他需要的數(shù)學往往并不存在,所以他只能自己去創(chuàng)造一些數(shù)學。為了直接面向應用的需要,他要提倡“具體”的數(shù)學。在這里我做一點簡單的解釋。例如在集合論中,數(shù)學家關心的都是最根本的問題公理系統(tǒng)的各種性質之類。而一些具體集合
的性質,各種常見集合,關系,映射都是什么樣的,數(shù)學家覺得并不重要。然而,在計算機科學中應用的,恰恰就是這些具體的東西。Knuth能夠首先看到這一點,不愧為當世計算機第一人。其次,Concrete是Continuous(連續(xù))加上discrete(離散)。不管連續(xù)數(shù)學還是離散數(shù)學,都是有用的數(shù)學!
理論與實際的結合——計算機科學研究的范疇
前面主要是從數(shù)學角度來看的。從計算機角度來看,理論計算機科學目前主要的研究領域包括:可計算性理論,算法設計與復雜性分析,密碼學與信息安全,分布式計算理論,并行計算理論,網(wǎng)絡理論,生物信息計算,計算幾何學,程序語言理論等等。這些領域互相交叉,而且新的課題在不斷提出,所以很難理出一個頭緒來。想搞搞這方面的工作,推薦看中國計算機學會的一系列書籍,至少代表了我國的權威。下面隨便舉一些例子。
由于應用需求的推動,密碼學現(xiàn)在成為研究的熱點。密碼學建立在數(shù)論(尤其是計算數(shù)論),代數(shù),信息論,概率論和隨機過程的基礎上,有時也用到圖論和組合學等。很多人以為密碼學就是加密解密,而加密就是用一個函數(shù)把數(shù)據(jù)打亂。這樣的理解太淺顯了。
現(xiàn)代密碼學至少包含以下層次的內容:
第一,密碼學的基礎。例如,分解一個大數(shù)真的很困難嗎?能否有一般的工具證明協(xié)議正確?
第二,密碼學的基本課題。例如,比以前更好的單向函數(shù),簽名協(xié)議等。
第三,密碼學的高級問題。例如,零知識證明的長度,秘密分享的方法。
第四,密碼學的新應用。例如,數(shù)字現(xiàn)金,叛徒追蹤等。
在分布式系統(tǒng)中,也有很多重要的理論問題。例如,進程之間的同步,互斥協(xié)議。一個經(jīng)典的結果是:在通信信道不可靠時,沒有確定型算法能實現(xiàn)進程間協(xié)同。所以,改進TCP三次握手幾乎沒有意義。例如時序問題。常用的一種序是因果序,但因果序直到不久前才有一個理論上的結果例如,死鎖沒有實用的方法能完美地對付。例如操作系統(tǒng)研究過就自己去舉吧!
如果計算機只有理論,那么它不過是數(shù)學的一個分支,而不成為一門獨立的科學。事實上,在理論之外,計算機科學還有更廣闊的天空。
更多詳細信息,請您微信關注“計算網(wǎng)”公眾號: