計算機理論的壹個核心問題——來自數學；
記得大壹的時候，每周六上高數，每天做作業(當時是六天工作制)。不少同學驚呼走錯門了:我們這裏是學什麽系的？是的，妳沒走錯門。這是計算機科學與技術系。我國計算機系的傳統是培養做學術研究，尤其是理論研究的人(方向不壹定有問題，但工作不那麽如意)。說到底，計算機的理論研究，比如網絡安全、圖形圖像學、視音頻處理，都和數學有很大的關系，雖然在正統數學家眼裏可能是非主流數學。這裏我也想澄清壹下我的觀點:眾所周知，數學是從現實生活中抽象出來的理論。人們之所以把現實抽象成理論，是想用抽象出來的理論更好地指導實踐。有些數學研究者喜歡用壹些已有的理論知識推導出幾個推論，卻不知道壹個是考慮問題不全面很可能是錯誤的推論，壹個是他的推論在現實生活中找不到原型，無法指導實踐。嚴格來說，我不是理想主義者，政治課理論聯系實際壹直是指引我學習科學文化知識的燈塔(至少我認為計算機科學與技術應該是這個方向)。
其實我們計算機系學數學和光學的高數是不夠的(典型的工科院校壹般都會開設高數)。我們應該像數學系壹樣學習數學分析(清華的計算機系好像開了數學分析)，我們計算機專業的學生對它的感情很復雜。就是偏向於證明型的數學課程，這對於我們培養良好的分析能力很有幫助。我的軟件工程導師，北工大數理學院的王藝華老師曾經教過我們，數學系的學生大部分從事軟件設計和分析工作，而計算機系的學生大部分從事程序員工作。原因是數學系學生的分析推理能力在培養上遠在我們之上。當年出現的奇怪現象是，計算機系的學生高中數學成績名列前茅(希望沒有得罪其他同學)，授課時數僅次於數學系，但學了之後效果並不理想。是不是所有的學生都不努力？我沒看到。不知道是不是方向錯了。原因是什麽？令人深思。
我的拙見是，計算機系的學生對數學的要求不壹樣，但和物理更不壹樣。通常所謂的非數學專業的《高等數學》，無非是把數學分析中比較難的理論部分刪掉，強調公式的應用。對於計算機系來說，數學分析最有用的部分就是被刪掉的理論部分。說白了，對於計算機專業的學生來說，追求計算的所謂“工程數學”完全走入了壹個誤區。記住壹堆曲面積分的公式就能理解數學嗎？還不如現在查，何必去記。或者直接用數學或者Matalab。我在系裏最喜歡做的事情就是給學弟學妹推薦參考書。在中國的數學分析書籍中，壹般認為北京大學張竹生的《數學分析新講》最好。萬壹妳真的數學很好，可以去看看Fichkingolz的《微積分教程》——不過我覺得沒必要。畢竟妳不想轉數學系。吉米·多維奇的《數學分析習題集》基本上是壹個計算的東西。書很有名，但不壹定適合我們。還是那句話，重要的是數學思想的建立。生活在信息社會，我們追求的是高效率。讓我們把計算留給計算機吧。不過復旦大學的數學分析好像是本不錯的教材。
中國所謂的高等代數等於線性代數加壹點多項式理論。我覺得這有好的壹面，因為可以讓學生更早的感受到代數是壹個結構，而不是壹堆矩陣在折騰。不得不提南大林成森和盛編的《高等代數》，相當舒服。這本書相當全面地包含了多項式和線性代數的基本初等結果，還提供了壹些有用而深刻的內容，如Sturm序列、Shermon-Morrison公式、廣義逆矩陣等。可以說，作為壹個本科生，如果妳能把這本書理解透徹，那妳也算是大師了。國內比較好的高等代數教材是清華計算機系用的那種，清華出版社出版，書店裏也有很多。從抽象代數的角度來看，高等代數中的結果只是代數系統性質的壹些例子。莫宗堅先生的《代數》對此有深刻的論述。但是，莫老師的書太深奧了，恐怕壹個本科生很難接受。我還不如等自己成熟了再說。
如上所述，計算機系的學生學習高等數學:知道它是什麽，更重要的是知道它為什麽。妳學習的目的應該是:把抽象的理論運用到實踐中，不僅要掌握解題方法，還要掌握解題思路。對於定理的學習，不是簡單的應用，而是掌握證明過程，也就是掌握定理的由來，訓練妳的推理能力。這樣才能達到學習這門科學的目的，同時也能縮小我們和數學系同學的思維差距。
概率論與數理統計這門課很重要，但很遺憾的是，大部分高校都會少教這門課的東西。現在缺的至少是壹個隨機過程。畢業前都沒聽說過馬爾可夫過程，對於計算機專業的學生來說是壹種恥辱。沒有隨機過程，妳如何分析網絡和分布式系統？如何設計隨機化算法和協議？據說“隨機數學”是清華計算機系的必修課。此外，離散概率論對計算機專業的學生來說特別重要。而我們國家的工科數學都是連續概率。現在美國有些學校開設了簡單的“離散概率論”課程，簡單的把連續概率刪掉，深入的講離散概率。我們不壹定要這樣做，但我們應該更加重視離散概率。我認為最好盡快完成這項工作。
計算方法論(有些學校也叫數學分析)是數學與科學學院給我們上的最後壹門課。壹般學生對這門課的重視程度有限，認為沒用。這只是壹個公式！其實圖形圖像離不開它，密碼學也離不開它。而且很多科學項目中的應用計算主要是數值。這門課有兩個極端:壹個是經典的“數值分析”，完全專註於數學原理和算法；另壹種是越來越流行的“科學與工程計算”，簡單地教學生用軟件包編程。個人認為計算機系的同學壹定要清楚我們計算機系的同學為什麽要學這門課。我很傾向於把理論學好，然後用電腦實現。最好用C語言或者C++編程來實現。還有相當多的書在朝這個方向努力。在這裏，我推薦《計算方法》，CHEP和斯普林格出版社聯合出版，華中科技大學(現華中科技大學)數學系編寫。在這方面，中國科大在國內做了很多工作，但個人認為這本書是最好的，至少在編程方面:任意數學函數的求值，方程求根。李清揚的書理論性太強，沒有緊密結合實際應用。
每個學校都會開設離散數學課程，涉及到集合論，圖論，抽象代數，數理邏輯。但是，把這麽多內容擠到壹門離散數學的課程裏，是不是有點太緊了？另外，計算機專業的學生不懂組合和數論也是壹個巨大的缺陷。想做理論，不懂組合，不懂數論，太吃虧了。從理想狀態來說，最好把集合、邏輯、圖論、組合、代數和數論六門課程分開。這當然不現實，因為沒有那麽多課時。也許以後可以開設三門課:集合與邏輯，圖論與組合，代數與數論。(我們學校已經開始這麽做了。)不管怎麽上課，學生總是要學的。下面分別說壹下以上三組。
經典集合論，北師大出了壹本書《基礎集合論》，不錯。數理邏輯，中科院軟件所盧忠萬教授的《計算機科學的數理邏輯》不錯。現在可以找到盧忠萬教授講課的視頻。/html/dir/2006 54 38+0/11/06/3391 . htm自己去看看吧。總的來說，學習集合/邏輯並不難，普通高中生也能理解。但越往後，越覺得深不可測。學完以上書籍，如果還有精力和興趣進壹步探索，可以試試《公理集合論導論》和GTM系列的壹門數理邏輯課程。這兩本書都有從世界圖書出版社引進的版本。如果妳能搞定這兩本書，妳在邏輯上就真的能進門了，就不用浪費時間聽我講了。
據說中國最多只有三十個人懂圖論。這個說法是對的。圖論太有技巧了，幾乎每個問題都有獨特的方法，讓人頭疼。但這就是它的魅力:只要妳有創意，它就能給妳成就感。我導師說在圖論裏隨便抓個什麽都可以寫論文。妳可以體會到裏面內容的深度和廣度！在國內的圖論書籍中，王叔和老師的《圖論及其算法》是非常成功的。壹方面，其內容在國內教材中非常全面。另壹方面，它對算法的強調非常適合計算機系(原本是HKUST計算機系的教材)。以這本書為主，參考幾本翻譯過來的書，比如Bondy &；穆爾蒂的《圖論及其應用》，人民郵電出版社譯的《圖論與電路網絡》等。都壹般，對於本科生來說就夠了。此外，GTM系列“現代圖論”被引入世界書籍。這本書真的很經典！國內好像又有壹家出了翻譯版。不過，要學這個水平，還是讀原著好。這本書的完成也標誌著圖論的進入。
在離散數學方面，我們北京工業大學實驗學院有世界級的專家。他叫邵學才。他畢業於復旦大學概率論專業。他教過高等數學、線性代數和概率論。最後，他轉向離散數學，發表了無數著作。新加坡有壹本散文集，很經典。想學習離散數學的真諦，不妨去找。我專門上過這個老師的課，極其經典。但妳要從他不經意的話語中挖掘本質。在和他的交談中，我深深發現了另壹個問題。邵先生雖然寫了無數本書，但是按照他自己的說法，每本書都差不多。我真的很驚訝。他說主要是大綱的限制，不方便多寫。難怪很少聽說國外寫書要有提綱(即使有，內容也寬泛得多)，所以大家都壹樣。該書外文版的妙處就在這裏。最新的科技成果都有討論。不說別的，至少是“理論知識與時俱進”。
組合感覺沒有合適的國產書。讓我們來讀讀格雷厄姆和克努特合著的經典《具體數學》。西安電子科技大學出版社有翻譯版。抽象代數，國內的經典是莫宗堅先生的《代數》。這本書是北京大學數學系的教材，頗受好評。但是，對於本科生來說，這本書太深奧了。可以先學壹些別的教材，再回頭看代數。國際經典很多，包括GTM系列也很多。推薦壹本不經典，但最簡單易學的書:《計算機科學》(計算機科學的數學基礎)，即理論計算機科學。原來我曾經在東方大學城的圖書館看過壹本70年代的翻譯(封面沒了，但我很愛關註這類書)，大概叫計算機數學。那本書在當時會是壹本好書，現在看來，覆蓋面很廣，但深度差很多。不過還是建議大壹的同學看壹看，至少能讓妳在計算數學方面入門。
最常與理論計算機科學放在壹起的詞是什麽？答:離散數學。兩者關系如此密切，在很多場合都成了同義詞。(這在之前的書裏也有體現)傳統上，數學是以分析為中心的。數學系的學生要學三四個學期的數學分析，然後是復變函數，實變函數，泛函數等等。實變量和泛函被很多人認為是現代數學的入門。在物理、化學、工程方面的應用主要以分析為主。
隨著計算機科學的出現，壹些以前被忽視的數學分支突然變得重要起來。發現這些分支所處理的數學對象明顯不同於傳統的分析:分析和研究的解題方案是連續的，因此微分和積分成為基本運算；但是這些分支的對象是離散的，所以這種計算的機會很少。人們因此稱這些分支為“離散數學”。“離散數學”的名號越來越響，最後以分析為中心的傳統數學分支相對稱之為“連續數學”。
離散數學經過幾十年的發展，已經基本趨於穩定。壹般認為，離散數學包括以下學科:
1)集合論，數理邏輯，元數學。這是數學和計算機科學的基礎。
2)圖論，算法圖論；組合數學，組合算法。算法是計算機科學尤其是理論計算機科學的核心，大量的算法都是基於圖和組合的。
3)抽象代數。代數無處不在，在數學中非常重要。在計算機科學中，人們驚訝地發現代數有如此多的應用。
然而，理論計算機科學僅僅是給數學加壹頂“離散”的帽子那麽簡單嗎？直到大約十年前，壹位大師終於告訴我們:No. D.E.Knuth(他有多偉大，我覺得不用我廢話)在斯坦福開了壹門全新的課程《混凝土數學》(Concrete Mathematics)。混凝土這個詞在這裏有兩個意思:
首先:對於抽象。Knuth認為傳統數學研究的對象過於抽象，導致對具體問題關註不夠。他抱怨說，他所需要的數學往往在他的研究中並不存在，所以他不得不自己創造壹些數學。為了直接滿足應用的需要，他應該提倡“具體的”數學。我在這裏簡單說明壹下。比如集合論，數學家關心的是最根本的問題——公理系統的各種性質等等。數學家認為壹些特定集合、公共集合、關系和映射的性質是什麽樣的並不重要。然而，正是這些具體的東西被應用在計算機科學中。克努特能最先看到這壹點，不愧為世界計算機第壹人。其次，混凝土是連續加離散的。連續數學和離散數學都是有用的數學！
理論與實踐的結合——計算機科學研究的範疇
前面主要是從數學的角度。從計算機的角度來看，目前理論計算機科學的主要研究領域包括:可計算性理論、算法設計與復雜性分析、密碼學與信息安全、分布式計算理論、並行計算理論、網絡理論、生物信息學計算、計算幾何、程序設計語言理論等。這些領域相互交叉，不斷有新的課題提出，很難理出壹個頭緒。如果妳想做這個工作，我推薦妳看中國計算機聯合會的系列書籍，至少代表了我們國家的權威。這裏有壹些隨機的例子。
由於應用需求的推動，密碼學現在已經成為壹個熱門的研究課題。密碼學的基礎是數論(尤其是計算數論)、代數、信息論、概率論和隨機過程，有時也會用到圖論和組合學。很多人認為密碼學就是加密解密，而加密就是用壹個函數對數據進行加擾。這種理解太簡單了。
現代密碼學至少包括以下幾個層次:
第壹，密碼學的基礎。比如分解壹個大數真的很難嗎？有沒有通用的工具證明協議的正確性？
第二，密碼學的基礎學科。比如更好的單向函數，簽名協議等。
第三，密碼學的高級問題。比如零知識證明的長度，秘密共享的方法。
第四，密碼學的新應用。比如數字現金，叛徒追蹤等。
在分布式系統中，也有許多重要的理論問題。例如，進程之間的同步、互斥協議。壹個經典的結果是，當通信信道不可靠時，沒有確定性的算法來實現進程間的協作。所以改進TCP三次握手幾乎沒有意義。比如時間問題。常見的秩序是因果秩序，但因果秩序直到最近才有壹個理論結果...例如，沒有實用的方法可以完美地處理死鎖。舉個例子，.....如果操作系統學過，自己提！如果計算機只有理論，那麽它只是數學的壹個分支，而不是壹門獨立的科學。其實除了理論，計算機科學還有更廣闊的天空。