計算機理論的壹個核心問題——從數學談起：
記得當年大壹入學，每周六課時高等數學，天天作業不斷(那時是六日工作制)。頗有些同學驚呼走錯了門:咱們這到底念的是什麽系？不錯，妳沒走錯門，這就是計算機科學與技術系。我國計算機科學系裏的傳統是培養做學術研究，尤其是理論研究的人（方向不見得有問題，但是做得不是那麽盡如人意）。而計算機的理論研究，說到底了，如網絡安全，圖形圖像學，視頻音頻處理，哪個方向都與數學有著很大的關系，雖然也許是正統數學家眼裏非主流的數學。這裏我還想闡明我的壹個觀點：我們都知道，數學是從實際生活當中抽象出來的理論，人們之所以要將實際抽象成理論，目的就在於想用抽象出來的理論去更好的指導實踐，有些數學研究工作者喜歡用壹些現存的理論知識去推導若幹條推論，殊不知其壹：問題考慮不全很可能是個錯誤的推論，其二：他的推論在現實生活中找不到原型，不能指導實踐。嚴格的說，我並不是壹個理想主義者，政治課上學的理論聯系實際壹直是指導我學習科學文化知識的航標（至少我認為搞計算機科學與技術的應當本著這個方向）。
其實我們計算機系學數學光學高等數學是不夠的（典型的工科院校壹般都開的是高等數學），我們應該像數學系壹樣學壹下數學分析（清華計算機系開的好像就是數學分析），數學分析這門科學，咱們學計算機的人對它有很復雜的感情。在於它是偏向於證明型的數學課程，這對我們培養良好的分析能力極有幫助。我的軟件工程學導師北工大數理學院的王儀華先生就曾經教導過我們，數學系的學生到軟件企業中大多作軟件設計與分析工作，而計算機系的學生做程序員的居多，原因就在於數學系的學生分析推理能力，從所受訓練的角度上要遠遠在我們之上。當年出現的怪現象是：計算機系學生的高中數學基礎在全校數壹數二(希望沒有冒犯其它系的同學)，教學課時數也僅次於數學系，但學完之後的效果卻不盡如人意。難道都是學生不努力嗎，我看未見得，方向錯了也說不壹定，其中原因何在，發人深思。
我個人的淺見是：計算機系的學生，對數學的要求固然跟數學系不同，跟物理類差別則更大。通常非數學專業的所謂“高等數學”，無非是把數學分析中較困難的理論部分刪去，強調套用公式計算而已。而對計算機系來說，數學分析裏用處最大的恰恰是被刪去的理論部分。說得難聽壹點，對計算機系學生而言，追求算來算去的所謂“工程數學”已經徹底地走進了誤區。記上壹堆曲面積分的公式，難道就能算懂了數學？那倒不如現用現查，何必費事記呢？再不然直接用Mathematics或是Matalab好了。 我在系裏最愛做的事情就是給學弟學妹們推薦參考書。中文的數學分析書，壹般都認為以北大張築生老師的“數學分析新講”為最好。萬壹妳的數學實在太好，那就去看菲赫金哥爾茨的“微積分學教程”好了--但我認為沒什麽必要，畢竟妳不想轉到數學系去。吉米多維奇的“數學分析習題集”也基本上是計算型的東東。書的名氣很大，倒不見得適合我們，還是那句話，重要的是數學思想的建立，生活在信息社會裏我們求的是高效，計算這玩意還是留給計算機吧。不過現在多用的似乎是復旦大學的《數學分析》也是很好的教材。
中國的所謂高等代數，就等於線性代數加上壹點多項式理論。我以為這有好的壹面，因為可以讓學生較早感覺到代數是壹種結構，而非壹堆矩陣翻來覆去。這裏不得不提南京大學林成森，盛松柏兩位老師編的“高等代數”，感覺相當舒服。此書相當全面地包含了關於多項式和線性代數的基本初等結果，同時還提供了壹些有用的又比較深刻的內容，如Sturm序列，Shermon-Morrison公式，廣義逆矩陣等等。可以說，作為本科生如能吃透此書，就可以算高手。國內較好的高等代數教材還有清華計算機系用的那本，清華出版社出版，書店裏多多，壹看就知道。從抽象代數的觀點來看，高等代數裏的結果不過是代數系統性質的壹些例子而已。莫宗堅先生的《代數學》裏，對此進行了深刻的討論。然而莫先生的書實在深得很，作為本科生恐怕難以接受，不妨等到自己以後成熟了壹些再讀。
正如上面所論述的，計算機系的學生學習高等數學：知其然更要知其所以然。妳學習的目的應該是：將抽象的理論再應用於實踐，不但要掌握題目的解題方法，更要掌握解題思想，對於定理的學習：不是簡單的應用，而是掌握證明過程即掌握定理的由來，訓練自己的推理能力。只有這樣才達到了學習這門科學的目的，同時也縮小了我們與數學系的同學之間思維上的差距。
概率論與數理統計這門課很重要，可惜大多數院校講授這門課都會少些東西。少了的東西現在看至少有隨機過程。到畢業還沒有聽說過Markov過程，此乃計算機系學生的恥辱。沒有隨機過程，妳怎麽分析網絡和分布式系統？怎麽設計隨機化算法和協議？據說清華計算機系開有“隨機數學”，早就是必修課。另外，離散概率論對計算機系學生來說有特殊的重要性。而我們國家工程數學講的都是連續概率。現在，美國已經有些學校開設了單純的“離散概率論”課程，幹脆把連續概率刪去，把離散概率講深些。我們不壹定要這麽做，但應該更加強調離散概率是沒有疑問的。這個工作我看還是盡早的做為好。
計算方法學（有些學校也稱為數學分析學）是最後壹門由數理學院給我們開的課。壹般學生對這門課的重視程度有限，以為沒什麽用。不就是照套公式嘛！其實，做圖形圖像可離不開它，密碼學搞深了也離不開它。而且，在很多科學工程中的應用計算，都以數值的為主。這門課有兩個極端的講法：壹個是古典的“數值分析”，完全講數學原理和算法；另壹個是現在日趨流行的“科學與工程計算”，幹脆教學生用軟件包編程。我個人認為，計算機系的學生壹定要認識清楚我們計算機系的學生為什麽要學這門課，我是很偏向於學好理論後用計算機實現的，最好使用C語言或C++編程實現。向這個方向努力的書籍還是挺多的，這裏推薦大家高等教育出版社（CHEP）和施普林格出版社(Springer)聯合出版的《計算方法（Computational Methods）》,華中理工大學數學系寫的（現華中科技大學），這方面華科大做的工作在國內應算是比較多的，而個人認為以這本最好，至少程序設計方面涉及了：任意數學函數的求值，方程求根，線性方程組求解，插值方法，數值積分，場微分方程數值求解。李慶揚的那本則理論性過強，與實際應用結合得不太緊。
每個學校本系裏都會開壹門離散數學，涉及集合論，圖論，和抽象代數，數理邏輯。不過，這麽多內容擠在離散數學壹門課裏，是否時間太緊了點？另外，計算機系學生不懂組合和數論，也是巨大的缺陷。要做理論，不懂組合或者數論吃虧可就太大了。從理想的狀態來看，最好分開六門課：集合，邏輯,圖論，組合，代數，數論。這個當然不現實，因為沒那麽多課時。也許將來可以開三門課：集合與邏輯，圖論與組合，代數與數論。（這方面我們學校已經著手開始做了）不管課怎麽開，學生總壹樣要學。下面分別談談上面的三組內容。
古典集合論，北師大出過壹本《基礎集合論》不錯。 數理邏輯，中科院軟件所陸鐘萬教授的《面向計算機科學的數理邏輯》就不錯。現在可以找到陸鐘萬教授的講課錄像，/html/Dir/2001/11/06/3391.htm自己去看看吧。總的來說，學集合/邏輯起手不難，普通高中生都能看懂。但越往後越感覺深不可測。 學完以上各書之後，如果妳還有精力興趣進壹步深究，那麽可以試壹下GTM系列中的《Introduction to Axiomatic Set Theory》和《A Course of Mathematical Logic》。這兩本都有世界圖書出版社的引進版。妳如果能搞定這兩本，可以說在邏輯方面真正入了門，也就不用再浪費時間聽我瞎侃了。
據說全中國最多只有三十個人懂圖論。此言不虛。圖論這東東，技巧性太強，幾乎每個問題都有壹個獨特的方法，讓人頭痛。不過這也正是它魅力所在：只要妳有創造性，它就能給妳成就感。我的導師說，圖論裏面隨便揪壹塊東西就可以寫篇論文。大家可以體會裏面內容之深廣了吧！國內的圖論書中，王樹禾老師的“圖論及其算法”非常成功。壹方面，其內容在國內教材裏算非常全面的。另壹方面，其對算法的強調非常適合計算機系(本來就是科大計算機系教材)。有了這本書為主，再參考幾本翻譯的，如Bondy & Murty的《圖論及其應用》，人民郵電出版社翻譯的《圖論和電路網絡》等等，就馬馬虎虎，對本科生足夠了。再進壹步，世界圖書引進有GTM系列的“Modern Graph Theory“。此書確實經典！國內好象還有壹家出版了個翻譯版。不過，學到這個層次，還是讀原版好。搞定這本書，也標誌著圖論入了門。
離散數學方面我們北京工業大學實驗學院有個世界級的專家，叫邵學才，復旦大學概率論畢業的，教過高等數學，線性代數，概率論，最後轉向離散數學，出版著作無數，論文集新加坡有壹本，堪稱經典，大家想學離散數學的真諦不妨找來看看。這老師的課我專門去聽過，極為經典。不過妳要從他的不經意的話中去挖掘精髓。在同他的交談當中我又深刻地發現壹個問題，雖說邵先生寫書無數，但依他自己的說法每本都差不多，我實在覺得詫異，他說主要是有大綱的限制，不便多寫。這就難怪了，很少聽說國外寫書還要依據個什麽大綱（就算有，內容也寬泛的多），不敢越雷池半步，這樣不是看誰的都壹樣了。外版的書好就好在這裏，最新的科技成果裏面都有論述，別的先不說，至少是“緊跟時代的理論知識”。
組合感覺沒有太適合的國產書。還是讀Graham和Knuth等人合著的經典“具體數學”吧，西安電子科技大學出版社有翻譯版。 抽象代數，國內經典為莫宗堅先生的“代數學”。此書是北大數學系教材，深得好評。然而對本科生來說，此書未免太深。可以先學習壹些其它的教材，然後再回頭來看“代數學”。國際上的經典可就多了，GTM系列裏就有壹大堆。推薦壹本談不上經典，但卻最簡單的，最容易學的：puter science(計算機科學的數學基礎)，也就是理論計算機科學。原來在東方大學城圖書館中曾經看過壹本七十年代的譯本（書皮都沒了，可我就愛關註這種書），大概就叫《計算機數學》。那本書若是放在當時來講決是壹本好書，但現在看來，涵蓋的範圍還算廣，深度則差了許多，不過推薦大壹的學生倒可以看壹看，至少可以使妳的計算數學入入門。
最常和理論計算機科學放在壹起的壹個詞是什麽？答：離散數學。這兩者的關系是如此密切，以至於它們在不少場合下成為同義詞。（這壹點在前面的那本書中也有體現）傳統上，數學是以分析為中心的。數學系的同學要學習三四個學期的數學分析，然後是復變函數，實變函數，泛函數等等。實變和泛函被很多人認為是現代數學的入門。在物理，化學，工程上應用的，也以分析為主。
隨著計算機科學的出現，壹些以前不太受到重視的數學分支突然重要起來。人們發現，這些分支處理的數學對象與傳統的分析有明顯的區別：分析研究的問題解決方案是連續的，因而微分，積分成為基本的運算；而這些分支研究的對象是離散的，因而很少有機會進行此類的計算。人們從而稱這些分支為“離散數學”。“離散數學”的名字越來越響亮，最後導致以分析為中心的傳統數學分支被相對稱為“連續數學”。
離散數學經過幾十年發展，基本上穩定下來。壹般認為，離散數學包含以下學科：
1) 集合論，數理邏輯與元數學。這是整個數學的基礎，也是計算機科學的基礎。
2) 圖論，算法圖論；組合數學，組合算法。計算機科學，尤其是理論計算機科學的核心是算法，而大量的算法建立在圖和組合的基礎上。
3) 抽象代數。代數是無所不在的，本來在數學中就非常重要。在計算機科學中，人們驚訝地發現代數竟然有如此之多的應用。
但是，理論計算機科學僅僅就是在數學的上面加上“離散”的帽子這麽簡單嗎？壹直到大約十幾年前，終於有壹位大師告訴我們：不是。D.E.Knuth(他有多偉大，我想不用我廢話了)在Stanford開設了壹門全新的課程Concrete Mathematics。 Concrete這個詞在這裏有兩層含義：
首先：對abstract而言。Knuth認為，傳統數學研究的對象過於抽象，導致對具體的問題關心不夠。他抱怨說，在研究中他需要的數學往往並不存在，所以他只能自己去創造壹些數學。為了直接面向應用的需要，他要提倡“具體”的數學。在這裏我做壹點簡單的解釋。例如在集合論中，數學家關心的都是最根本的問題--公理系統的各種性質之類。而壹些具體集合的性質，各種常見集合，關系，映射都是什麽樣的，數學家覺得並不重要。然而，在計算機科學中應用的，恰恰就是這些具體的東西。Knuth能夠首先看到這壹點，不愧為當世計算機第壹人。其次，Concrete是Continuous(連續)加上discrete(離散)。不管連續數學還是離散數學，都是有用的數學！
理論與實際的結合——計算機科學研究的範疇
前面主要是從數學角度來看的。從計算機角度來看，理論計算機科學目前主要的研究領域包括：可計算性理論，算法設計與復雜性分析，密碼學與信息安全，分布式計算理論，並行計算理論，網絡理論，生物信息計算，計算幾何學，程序語言理論等等。這些領域互相交叉，而且新的課題在不斷提出，所以很難理出壹個頭緒來。想搞搞這方面的工作，推薦看中國計算機學會的壹系列書籍，至少代表了我國的權威。下面隨便舉壹些例子。
由於應用需求的推動，密碼學現在成為研究的熱點。密碼學建立在數論(尤其是計算數論)，代數，信息論，概率論和隨機過程的基礎上，有時也用到圖論和組合學等。很多人以為密碼學就是加密解密，而加密就是用壹個函數把數據打亂。這樣的理解太淺顯了。
現代密碼學至少包含以下層次的內容：
第壹，密碼學的基礎。例如，分解壹個大數真的很困難嗎？能否有壹般的工具證明協議正確？
第二，密碼學的基本課題。例如，比以前更好的單向函數，簽名協議等。
第三，密碼學的高級問題。例如，零知識證明的長度，秘密分享的方法。
第四，密碼學的新應用。例如，數字現金，叛徒追蹤等。
在分布式系統中，也有很多重要的理論問題。例如，進程之間的同步，互斥協議。壹個經典的結果是：在通信信道不可靠時，沒有確定型算法能實現進程間協同。所以，改進TCP三次握手幾乎沒有意義。例如時序問題。常用的壹種序是因果序，但因果序直到不久前才有壹個理論上的結果....例如，死鎖沒有實用的方法能完美地對付。例如,......操作系統研究過就自己去舉吧！ 如果計算機只有理論，那麽它不過是數學的壹個分支，而不成為壹門獨立的科學。事實上，在理論之外，計算機科學還有更廣闊的天空。