計算機理論的壹個核心問題——來自數學；
記得大壹的時候，每周六上高數，每天做作業(當時是六天工作制)。不少同學驚呼走錯門了:我們這裏是學什麽系的？是的，妳沒走錯門。這是計算機科學與技術系。我國計算機系的傳統是培養做學術研究，尤其是理論研究的人(方向不壹定有問題，但工作不那麽如意)。說到底，計算機的理論研究，比如網絡安全、圖形圖像學、視音頻處理，都和數學有很大的關系，雖然在正統數學家眼裏可能是非主流數學。這裏我也想澄清壹下我的觀點:眾所周知，數學是從現實生活中抽象出來的理論。人們之所以把現實抽象成理論，是想用抽象出來的理論更好地指導實踐。有些數學研究者喜歡用壹些已有的理論知識推導出幾個推論，卻不知道壹個是考慮問題不全面很可能是錯誤的推論，壹個是他的推論在現實生活中找不到原型，無法指導實踐。嚴格來說，我不是理想主義者，政治課理論聯系實際壹直是指引我學習科學文化知識的燈塔(至少我認為計算機科學與技術應該是這個方向)。
其實我們計算機系學數學和光學的高數是不夠的(典型的工科院校壹般都會開設高數)。我們應該像數學系壹樣學習數學分析(清華的計算機系好像開了數學分析)，我們計算機專業的學生對它的感情很復雜。就是偏向於證明型的數學課程，這對於我們培養良好的分析能力很有幫助。我的軟件工程導師，北工大數理學院的王藝華老師曾經教過我們，數學系的學生大部分從事軟件設計和分析工作，而計算機系的學生大部分從事程序員工作。原因是數學系學生的分析推理能力在培養上遠在我們之上。當年出現的奇怪現象是，計算機系的學生高中數學成績名列前茅(希望沒有得罪其他同學)，授課時數僅次於數學系，但學了之後效果並不理想。是不是所有的學生都不努力？我沒看到。不知道是不是方向錯了。原因是什麽？令人深思。
我的拙見是，計算機系的學生對數學的要求不壹樣，但和物理更不壹樣。通常所謂的非數學專業的《高等數學》，無非是把數學分析中比較難的理論部分刪掉，強調公式的應用。對於計算機系來說，數學分析最有用的部分就是被刪掉的理論部分。說白了，對於計算機專業的學生來說，追求計算的所謂“工程數學”完全走入了壹個誤區。記住壹堆曲面積分的公式就能理解數學嗎？還不如現在查，何必去記。或者直接用數學或者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三次握手幾乎沒有意義。比如時間問題。常見的秩序是因果秩序，但因果秩序直到最近才有壹個理論結果...例如，沒有實用的方法可以完美地處理死鎖。舉個例子，.....如果操作系統學過，自己提！
如果計算機只有理論，那麽它只是數學的壹個分支，而不是壹門獨立的科學。其實除了理論，計算機科學還有更廣闊的天空。
我壹直認為四年的時間是不夠學習計算機基礎知識的，因為範圍太廣了。......
在這方面，我想談談我們系各個學校普遍開設的“計算機基礎”。高校開設計算機基礎課程是我國高等教育部門規定的所有專業的必修課要求。主要內容是使學生掌握計算機發展史，學會簡單使用操作系統、文字處理、表格處理和初步的網絡應用功能。但是計算機系教這門課的目標壹定不能和這個壹致。計算機科學課程的目標應該是:讓學生充分了解計算機科學的發展，明確把握計算機科學的研究方向，發展的前沿是各門課程在整個學科體系中的地位。搞清楚每門學科的學習目的，學習內容，應用領域。使學生在學科學習初期對整個學科有壹個整體的了解，從而明確知道以後要學什麽，怎麽學。計算機應用基礎技能的位置應該放在第二位甚至更靠後，因為這個系的學生應該有這個探索能力。這壹點非常重要。推薦壹本書:機械工業出版社的《計算機科學新視角》。看完這本書，我深深地意識到，我還是壹個計算機科學的初學者，我對什麽是計算機科學已經有了透徹的了解。此外，廈大趙老師的《計算科學導論》壹書中的許多經典理論，在同類書籍中也很難找到。看看他，也許妳會明白壹個最基本的問題:為什麽計算機科學比計算科學更準確。這本書也可以成為世界名著。
壹個壹流計算機系的優秀學生，絕不應該只是壹個編程高手，而首先必須是壹個編程高手。大學的時候，第壹門專業課是C語言編程。從某種角度來說，相當壹部分讀計算機的人是靠寫程序過日子的。在北工大實驗學院計算機系(甚至在今天的CSDN上)壹直有這樣壹個爭論，到底應該用哪壹種作為第壹編程語言。個人認為，最後壹節屬於哪種語言，關鍵在於養成良好的編程習慣。當時老師告訴我們，打好基礎後只需要壹個星期就能學會壹門新的語言。現在我覺得根本用不了壹周，前提是先打好基礎。不要猶豫，學吧，等妳做出選擇的時候，別人已經會幾種語言了。
匯編語言和微機原理是兩門特別討厭的課程。妳的數學/理論基礎再好，也不能占便宜。這兩道菜之間的順序也是先有雞還是先有蛋。不管妳先學哪門課，都會涉及到另壹門課的東西。所以，只能靜下心來慢慢想。這是典型的工科類，不需要太多的聰明和頓悟，需要循序漸進的開悟。關於這兩門課的書在電腦書店裏不難找到。拿幾本最新的書比較壹下。《組成原理》推薦清華大學王愛英教授寫的《計算機組成與結構》。匯編語言每個人都把8086/8088帶進壹個門，然後妳必須學習80x86匯編語言。很有實用價值，不落後，結構很好。寫高效的病毒，用高級語言嵌入壹點點匯編，進行低級開發，總是離不開他。推薦清華大學沈梅梅的IBM-PC匯編語言編程。有人說，不想了解計算機架構，不想做計算機，沒必要學計算機原理、匯編語言、接口等課程。這合理嗎？明顯不合理，這些東西遲早要掌握，必須接觸。而且這些都是計算機專業相對於其他專業為數不多的優勢。做項目的時候，了解這些很重要。不能說技術只是為了技術。只懂技術的人最多只能做個編碼工，永遠無法完全理解整個系統的設計。編碼工作者年齡越大，價值越低。關於構圖原理還有壹個教學問題。我在學這門課的時候，老師省略了CPU工作原理和微程序設計這壹塊。原因是我們國家的CPU技術不如其他國家，而且經過這麽長時間，我們終於出了壹個比英特爾差十萬八千裏的龍芯，建議不要學。我不認為這是所有學校的問題。如果真如他所說，中國可以在任何方向阻止計算機科學。美國有幾樣東西是可以做的，比如軟件、硬件、應用，其他的都做不到，那我們為什麽坐在這裏？教學觀念需要改變。
現在不僅計算機專業的學生不會處理模擬電路，電子專業的學生也大多害怕。如果妳真的想同時吃軟件和硬件，那麽我建議妳先看看邱關源的“電路原理”，也許再看看模擬電路。教材:康的《電子技術基礎》(高等教育出版社)還是不錯的(我校電子系用)。如果妳有興趣，也可以參考童的書。
數字電路比模擬電路好得多。我推薦妳看壹看北京工業大學劉應賢教授寫的《數字邏輯》。演出中的人說這本書很有參考價值(來自機械工業出版社)。原因很清楚，有很高的實用價值。聽她教的課程，是壹種“享受科學”的感覺。清華大學閻石的書也是壹本很好的教材，但遺憾的是，裏面少談集成電路。我很感興趣。再來看看大型數字系統的設計(北航的還是用的比較多)。
如何教授計算機系統結構在國際上仍有爭議。國內能找到的比較好的教材是Stallings的《面向性能的計算機組織與架構設計》(清華影印)
本)。世界上最流行的壹本是《計算機架構:水生途徑》，作者帕特森&；軒尼詩.
操作系統可以選擇《操作系統內核的設計與實現》和《現代操作系統》兩本書中的壹本。兩者都算得上經典，唯壹的缺點就是理論上不夠嚴謹。但是這個領域屬於硬核系統，理論上馬虎可以理解。如果想看理論，請推薦清華大學出版社的《操作系統》，高教部主任張堯學著，是我們用的教材。另外推薦壹本機械工業出版社出版的《Windows操作系統原理》。這本書是中國操作系統專家在微軟零距離考察半年後寫的，寫作歷時壹年多。幾乎所有教操作系統的專家都參與了，除了清華大學的張堯學(現高教部主任)。比爾·蓋茨親自寫了序言。不僅結合windows2000、xp、XP詳細介紹了操作系統的內核，後面還講了壹些windows編程基礎，很有壹種洋版書的味道，而且上面的壹些內容可以說國內外只有那本書對windows內核有詳細的介紹。
如果先學好形式語言，我覺得只需要學習編譯原理前端的四個算法:遞歸下降，最容易實現；最佳自頂向下算法LL(k)；最佳自底向上算法LR(k)；LR(1)的簡化單反(也許還有另壹個簡化的LALR)。後端完全是工程，自然是後話。
推薦教材:Kenneth C.Louden寫的《編譯原理與實踐》是《編譯原理與實踐》(機械工業出版社譯)。
學習數據庫要提醒大家，會用VFP、VB、PowerBuilder不等於會數據庫。世界上自以為懂數據庫的人太多了！數據庫設計是科學也是藝術，數據庫實現是典型的項目。所以從某種意義上說，數據庫是最典型的計算機課程——理工科結合，相互滲透。另外，我推薦妳學完軟件工程再去翻壹翻數據庫技術，會是壹種新的感受。推薦教材:《數據庫系統概念》亞伯拉罕·西爾伯沙茨等。作為知識的完備性，我也推薦大家看壹下機械工業出版社的《數據倉庫》翻譯。
計算機網絡的標準教材來自Tanenbaum的《計算機網絡》(清華大學譯)。還有謝希仁的《計算機網絡教程》(人民郵電出版社)的推薦，比較清晰，參考文獻也比較權威。但是網絡也屬於硬核體系，光看書是不夠的。建議多看RFC。妳可以在http://www.ietf.org/rfc.htm.從IP閱讀按編號下載RFC文檔。當妳能掌握10左右的常用協議，就沒幾個人敢小看妳了。我認為做網絡設計的工作會更好。