【文章內(nèi)容簡介】 什么樣的，數(shù)學家覺得并不重要。然而，在計算機科學中應用的，恰恰就是這些具體的東西。knuth能夠首先看到這一點，不愧為當世計算機第一人。其次，concrete是continuous(連續(xù))加上discrete(離散)。不管連續(xù)數(shù)學還是離散數(shù)學，都是有用的數(shù)學!理論與實際的結合——計算機科學研究的范疇前面主要是從數(shù)學角度來看的。從計算機角度來看，理論計算機科學目前主要的研究領域包括：可計算性理論，算法設計與復雜性分析，密碼學與信息安全，分布式計算理論，并行計算理論，網(wǎng)絡理論，生物信息計算，計算幾何學，程序語言理論等等。這些領域互相交叉，而且新的課題在不斷提出，所以很難理出一個頭緒來。想搞搞這方面的工作，推薦看中國計算機學會的一系列書籍，至少代表了我國的權威。下面隨便舉一些例子。由于應用需求的推動，密碼學現(xiàn)在成為研究的熱點。密碼學建立在數(shù)論(尤其是計算數(shù)論)，代數(shù)，信息論，概率論和隨機過程的基礎上，有時也用到圖論和組合學等。很多人以為密碼學就是加密解密，而加密就是用一個函數(shù)把數(shù)據(jù)打亂。這樣的理解太淺顯了?，F(xiàn)代密碼學至少包含以下層次的內(nèi)容：第一，密碼學的基礎。例如，分解一個大數(shù)真的很困難嗎?能否有一般的工具證明協(xié)議正確?第二，密碼學的基本課題。例如，比以前更好的單向函數(shù)，簽名協(xié)議等。第三，密碼學的高級問題。例如，零知識證明的長度，秘密分享的方法。第四，密碼學的新應用。例如，數(shù)字現(xiàn)金，叛徒追蹤等。在分布式系統(tǒng)中，也有很多重要的理論問題。例如，進程之間的同步，互斥協(xié)議。一個經(jīng)典的結果是：在通信信道不可靠時，沒有確定型算法能實現(xiàn)進程間協(xié)同。所以，改進tcp三次握手幾乎沒有意義。例如時序問題。常用的一種序是因果序，但因果序直到不久前才有一個理論上的結果例如，死鎖沒有實用的方法能完美地對付。例如操作系統(tǒng)研究過就自己去舉吧!如果計算機只有理論，那么它不過是數(shù)學的一個分支，而不成為一門獨立的科學。事實上，在理論之外，計算機科學還有更廣闊的天空。計算機學硬件的專業(yè)篇四每個學校本系里都會開一門離散數(shù)學，涉及集合論，圖論，和抽象代數(shù)，數(shù)理邏輯。不過，這么多內(nèi)容擠在離散數(shù)學一門課里，是否時間太緊了點?另外，計算機系學生不懂組合和數(shù)論，也是巨大的缺陷。要做理論，不懂組合或者數(shù)論吃虧可就太大了。從理想的狀態(tài)來看，最好分開六門課：集合，邏輯圖論，組合，代數(shù)，數(shù)論。這個當然不現(xiàn)實，因為沒那么多課時。也許將來可以開三門課：集合與邏輯，圖論與組合，代數(shù)與數(shù)論。(這方面我們學校已經(jīng)著手開始做了)不管課怎么開，學生總一樣要學。下面分別談談上面的三組內(nèi)容。古典集合論，北師大出過一本《基礎集合論》不錯。 數(shù)理邏輯，中科院軟件所陸鐘萬教授的《面向計算機科學的數(shù)理邏輯》就不錯。現(xiàn)在可以找到陸鐘萬教授的講課錄像，自己去看看吧。總的來說，學集合/邏輯起手不難，普通高中生都能看懂。但越往后越感覺深不可測。學完以上各書之后，如果你還有精力興趣進一步深究，那么可以試一下gtm系列中的《introduction to axiomatic set theory》和《a course of mathematical logic》。這兩本都有世界圖書出版社的引進版。你如果能搞定這兩本，可以說在邏輯方面真正入了門，也就不用再浪費時間聽我瞎侃了。據(jù)說全中國最多只有三十個人懂圖論。此言不虛。圖論這東東，技巧性太強，幾乎每個問題都有一個獨特的方法，讓人頭痛。不過這也正是它魅力所在：只要你有創(chuàng)造性，它就能給你成就感。我的導師說，圖論里面隨便揪一塊東西就可以寫篇論文。大家可以體會里面內(nèi)容之深廣了吧!國內(nèi)的圖論書中，王樹禾老師的“圖論及其算法”非常成功。一方面，其內(nèi)容在國內(nèi)教材里算非常全面的。另一方面，其對算法的強調(diào)非常適合計算機系(本來就是科大計算機系教材)。有了這本書為主，再參考幾本翻譯的，如bondy amp。 murty的《圖論及其應用》，人民郵電出版社翻譯的《圖論和電路網(wǎng)絡》等等，就馬馬虎虎，對本科生足夠了。再進一步，世界圖書引進有gtm系列的modern graph theory。此書確實經(jīng)典!國內(nèi)好象還有一家出版了個翻譯版。不過，學到這個層次，還是讀原版好。搞定這本書，也標志著圖論入了門。離散數(shù)學方面我們北京工業(yè)大學實驗學院有個世界級的專家，叫邵學才，復旦大學概率論畢業(yè)的，教過高等數(shù)學，線性代數(shù)，概率論，最后轉向離散數(shù)學，出版著作無數(shù)，論文集新加坡有一本，堪稱經(jīng)典，大家想學離散數(shù)學的真諦不妨找來看看。這老師的課我專門去聽過，極為經(jīng)典。不過你要從他的不經(jīng)意的話中去挖掘精髓。在同他的交談當中我又深刻地發(fā)現(xiàn)一個問題，雖說邵先生寫書無數(shù)，但依他自己的說法每本都差不多，我實在覺得詫異，他說主要是有大綱的限制，不便多寫。這就難怪了，很少聽說國外寫書還要依據(jù)個什么大綱(就算有，內(nèi)容也寬泛的多)，不敢越雷池半步，這樣不是看誰的都一樣了。外版的書好就好在這里，最新的科技成果里面都有論述，別的先不說，至少是“緊跟時代的理論知識”。組合感覺沒有太適合的國產(chǎn)書。還是讀graham和knuth等人合著的經(jīng)典“具體數(shù)學”吧，西安電子科技大學出版社有翻譯版。 抽象代數(shù)，國內(nèi)經(jīng)典為莫宗堅先生的“代數(shù)學”。此書是北大數(shù)學系教材，深得好評。然而對本科生來說，此書未免太深?？梢韵葘W習一些其它的教材，然后再回頭來看“代數(shù)學”。國際上的經(jīng)典可就多了，gtm系列里就有一大堆。推薦一本談不上經(jīng)典，但卻最簡單的，最容易學的：這本“introduction to linear and abstract algebra非常通俗易懂，而且把抽象代數(shù)和線性代數(shù)結合起來，對初學者來說非常理想，我校比較牛的同學都有收藏。數(shù)論方面，國內(nèi)有經(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)足夠，不需要再參考其它書。計算機學硬件的專業(yè)篇五今天開始認真地查資料，應該是有