從第1臺電子計算機問世到現(xiàn)在已經(jīng)60年了,盡管計算機科學和技術繼續(xù)保持高速發(fā)展的態(tài)勢，但是計算機科學與技術不能再采用以往一樣的方式發(fā)展，需要革命性的突破。如果一直順著過去形成的慣性發(fā)展，計算機科學的路子可能會越走越窄。我們需要靜下心來，認真進行反思，總結經(jīng)驗和教訓，以便將來更快更好地發(fā)展。

一、計算機科學的迷途

1．計算機科學不應以把解決方案搞復雜為榮
    普遍認為，計算機科學是“算法的科學”。美國計算機學會（ACM）對計算機科學有如下的定義：Computer Science as the "systematic study of algorithmic processes that describe and transform information: their theory, analysis, design, efficiency, implementation and application"。算法研究應該是計算機科學的重要內容，但是從某些意義上講，計算機科學“成也算法，敗也算法”。計算機科學有兩個基礎：可計算性和計算復雜性?？上В壳皩W習可計算性的主要興趣在證明某些問題不可計算；學習計算復雜性的主要興趣在證明NP困難問題。在其他學科中很少見到科學家對不可解或實際上幾乎不可解的問題有這么大的興趣。電子工程科學真正幫助了電路設計，如芯片設計的EDA工具在集成電路產(chǎn)業(yè)發(fā)展中功不可沒。但計算機科學并沒有大大減輕編軟件的困難，軟件設計理論的確需要革命性的突破。
     上世紀70年代有一本書《計算機和不可解性（Computers and Intractability）》，作者是M. R. Garey和D. S. Johnson，很多學校都采用作為本科高年級或研究生教材，影響很大。這本書的扉頁上有一張漫畫，漫畫中一個人說：這個問題我不能解決，但是你也不能解決，因為它是NP完全問題。說話那個人表現(xiàn)出十分得意的樣子。這幅漫畫影響了計算機界幾十年，從事計算機科學研究的人對解決不了實際需要攻克的困難問題一般不會有任何內疚，因為這是大家都解決不了的NP問題。這種導向對計算機科學已產(chǎn)生了不好的影響。我們真正需要的不是發(fā)現(xiàn)一些理論上復雜的問題，而是要在用戶滿意的前提下盡可能有效地解決實際存在的復雜問題。計算機科學不應以把解決方案搞復雜為榮，盡可能用簡單方法處理復雜問題是信息技術的生存之道。

2．應當重視確定可有效求解的問題邊界
     我們做的研究工作多數(shù)是改進前人的算法或理論模型，至于沿著已開辟的方向究竟還有多大改進的余地卻很少考慮，很可能這一方向已到了可有效求解的問題邊界，而另一方向有很廣闊的改進空間我們反而沒有觸及。15年前，美國紐約大學的施瓦茨（Schwartz）教授在智能中心做過一個報告。他說，數(shù)學上已知的（knowable）問題邊界極不規(guī)則（如圖1所示）。就像油田開采一樣，在某個位置鉆井有油，偏離一點就沒有油。問題的可解性也很類似，某個問題在某些條件下是易解的，但是如果條件稍微改變一點點就很難解甚至不可解了。確定可有效求解的問題邊界，應該是計算機科學的重要內容。

圖1  數(shù)學上已知的問題邊界極不規(guī)則
3．并行處理不是萬能藥
      并行計算的成功與逐步普及容易使人產(chǎn)生錯覺，只要是單機難以解決的問題就想求助于并行計算機，但并行計算并不是萬能藥。計算機算法大致上可分成三類：（1）線性或幾乎是線性復雜性的算法，如分類（sorting）、商務處理等；（2）多項式或較低的指數(shù)復雜性算法，如矩陣運算等；（3）指數(shù)復雜性算法，如各種模式轉換、規(guī)劃（planning）等。第一類算法一般可用微機或服務器實現(xiàn)；第二類算法和問題規(guī)模大或有實時要求的第一類算法需要并行計算機。已知的第二類算法幾乎都是科學計算。超級計算對第三類算法幫助不大，加速100萬倍也只能稍稍擴大求解問題規(guī)模，需要尋找新的思路。線性提高并行處理能力不可能對付指數(shù)增長的組合爆炸問題（NP問題）。解決人工智能等問題的非確定算法（如搜索算法）在并行處理中，會出現(xiàn)加速比遠遠超過處理機數(shù)的異常現(xiàn)象（好的異常），但我的博士論文《組合搜索的并行處理（Parallel Processing for Combinatorial Search）》已經(jīng)證明，好的異常和壞的異常（并行不如串行）要么都存在，要么都不存在。除非能開發(fā)出指數(shù)增長的并行處理能力，否則用生物計算機的所謂海量并行也不可能有效地解決組合爆炸問題。解決人工智能等組合爆炸問題的根本出路在于對所求解問題本身的深入理解。

二、計算機科學不僅要研究復雜性，還要研究“簡單性”

1．復雜性與簡單性
      大多數(shù)理論計算機科學家熱衷于發(fā)現(xiàn)人為的難題，而不是尋求有效的方法解決實際問題。我們不僅需要刻畫問題困難程度的“復雜性理論”，計算機科學可能更需要建立“簡單性理論”，即如何發(fā)現(xiàn)最簡單的方法去解決實際問題。由于易解問題的邊界極不規(guī)則，我們特別需要一種理論指導算法設計者選擇努力的方向，需要知道往某一方向努力理論上還有多大的改進空間。
例如，熱力學中有一個著名的卡諾循環(huán)（Carnot Cycle），其理論表述很簡單：
卡諾效率（Carnot Efficiency） = 1 – Tc/Th
Tc和Th分別代表熱機工作環(huán)境的低溫和高溫。這一極簡單的定律對熱機的設計起到非常大的作用。但是，在計算機科學里似乎從未見過這樣簡潔的對實際設計有指導意義的公式。

2．駕馭復雜性是信息技術創(chuàng)新的基本問題
    人工智能領域權威學者布魯克斯（Brooks）說過：“復雜性是致命的敵人?！毕到y(tǒng)復雜性研究已成為21世紀最重要的科學內容，但計算機領域的科研人員對這一最活躍的領域似乎關注不夠。在錢學森等老科學家的倡導下，我國學者在復雜巨系統(tǒng)和定性定量相結合的研究上已取得不少成果，有些成果應對計算機科學家有重要借鑒意義。信息技術發(fā)展的歷史證明：信息技術發(fā)展遵循簡單性法則，過于復雜的技術往往被淘汰或變成脫離主流的技術，如Ada語言、數(shù)據(jù)流計算機、B-ISDN（寬帶綜合業(yè)務數(shù)字網(wǎng)絡）技術等?；ヂ?lián)網(wǎng)成功的原因之一在于KISS原則（Keep It Simple and Stupid）。我們應認真總結計算機的發(fā)展史，從中發(fā)現(xiàn)駕馭復雜性的規(guī)律，為計算機領域的技術創(chuàng)新導航。

三、計算機科學要為技術實現(xiàn)“化難為易”提供科學指南
      以往的計算機科學為技術實現(xiàn)“化難為易”已經(jīng)提供了一些科學指南，但是做得還不夠。作為一門具有指導意義的科學，計算機科學應該做得更好一些。在“化難為易”方面，下面幾個問題值得我們深思。

1．降低問題復雜性的關鍵是選擇合適的問題表述
      我剛從美國回國工作時，有感于國內不重視不同于“計算方法”的算法研究，曾呼吁過國內要大力開展真正的算法研究，現(xiàn)在我感到要強調問題的另一面。一類問題的復雜性取決于它的問題表述（問題復雜性可能是計算機科學中很少有的不變量），只要問題表述沒有改變，解決某一類問題的算法復雜性的下限就不可能改變。我們花了很多功夫優(yōu)化算法，但卻很少花功夫尋找合適的問題表述，可能是撿了芝麻丟了西瓜。有些所謂NP困難問題并不反映實際問題的本質“簡單性”，比如識別人臉對人腦而言可能就是一個簡單問題。我們不應研究人如何“繞過”了指數(shù)爆炸，而是要研究我們采用的人臉識別表述方法如何把我們引入了指數(shù)爆炸的歧路，我們需要做的事情是選擇對人臉數(shù)據(jù)的簡單描述的模式。

2．改變問題分解的途徑可大幅度提高問題求解效率。
      我在美國做博士論文研究時，常常采用把一個問題分解成許多子問題的途徑來解決復雜問題，這是計算機科學里最常用的Divide and Conquer方法。最近我的導師Benjamin Wan教授告訴我，對有些問題，他現(xiàn)在采用分解限制條件的辦法比傳統(tǒng)的子問題分解，求解效率可高出上千倍。有些實際問題，像機場的實時調度，可能有上千種限制條件。傳統(tǒng)的求解方法是通過問題分解去縮小問題規(guī)模，如先分解到部門一級再綜合。這樣分解后的每一個子問題的復雜性并沒有減少。但如果對限制條件進行分解，分解后的每個小問題只包含很少的限制，這樣的小問題就極其簡單，實際的求解效率可大大提高。

3．虛擬化是化繁為簡的關鍵技術
      一部計算機發(fā)展的歷史可看作計算機技術不斷虛擬化的歷史。上世紀70年代，IBM 370首先使用虛擬計算機概念。1992年布特勒·蘭普森在獲得圖靈獎時引用別人的話說過：“計算機科學中的任何問題都可以通過另外一個層次解決?！庇嬎銠C產(chǎn)業(yè)的發(fā)展不可能完全做到先提出完美的頂層設計再按既定的標準發(fā)展，標準往往是在競爭中形成的。為了解決發(fā)展過程中互操作和兼容等問題，常常通過虛擬機的思路在更高的層次隱藏下一層的技術細節(jié)。我們要把虛擬機的思想理論化，使之成為計算機科學的重要內容。

四、計算機科學應重點突破技術發(fā)展的限制

1．一味提高速度不是明智的選擇。
      這些年來，計算機技術的高速發(fā)展得益于摩爾（Moore）定律，所以不少人言必稱摩爾定律。其實，計算機技術的發(fā)展也受害于摩爾定律。CPU和計算機性能的不斷提高，確實緩解了某些過去不容易解決的困難，但也掩蓋了計算機科學中的一些基本矛盾，許多問題都指望通過計算機性能提高來解決?，F(xiàn)在，芯片和計算機性能的提高已遇到功耗、可靠性和成本三面高墻，計算機科學應重點突破這些技術發(fā)展的限制。例如，像現(xiàn)在這樣無限制地擴大芯片面積和集成度，一個芯片里集成幾億甚至幾十億個晶體管，造成功耗很大，成本不斷增加，可靠性降低。近來許多專家都指出，一味地從提高芯片和計算機的速度上找出路不是一個明智的選擇。
     芯片器件的復雜性每年增長68％，到2018年單芯片內晶體管數(shù)預計將超過140億個，而芯片設計能力（每個人月設計的晶體管數(shù)）每年只增長21％（CPU內大量的芯片面積只能用來做增值不高的緩存）。集成電路產(chǎn)業(yè)的瓶頸在芯片設計，若不能有效掌控芯片的復雜性，即使有了10納米的新工藝，潛在的芯片能力也發(fā)揮不出來。怎樣才能把芯片所能提供的能力盡量發(fā)掘出來，需要在計算機科學上有所突破。

2．吸取工業(yè)化進程的教訓
      我們應該從過去工業(yè)化的進程中吸取教訓。幾十年前，不管是化工還是鋼鐵，我們的前輩在實現(xiàn)工業(yè)化的過程中，并沒有認識到他們的做法有什么不對?，F(xiàn)在，到了我們這一代，我們發(fā)現(xiàn)有很多不合理的地方：沒有給我們留下一個美好的環(huán)境，污染嚴重，浪費資源等等。我擔心再過50年，我們的后人說，21世紀初有那么一批很蠢的計算機科學家，他們搞的信息化造成很多問題，浪費了很多資源，對人類文明也是一種浪費。我想，與其將來被別人批判，還不如我們自己批判自己，走一條更加符合人類社會發(fā)展規(guī)律的道路。我們需要反思：計算機科學技術是不是也走了一些彎路，是否應該探索革命性的突破？

五、計算機科學要尋求大的突破。
     計算機科學的發(fā)展已經(jīng)到了相對成熟的階段，如何繼續(xù)向前發(fā)展是每一位計算機科學家需要認真思考的問題。我們需要擺脫過去已經(jīng)取得的成就的拖累，提出新的發(fā)展思路。
1．重新發(fā)明網(wǎng)絡和操作系統(tǒng)
     最近，美國國家自然基金會（NSF）在計算機和通信網(wǎng)絡領域提出了新的研究方向，如投入3億美金的GENI項目，值得我們注意。美國NSF網(wǎng)絡和計算機領域的主管官員趙偉教授告訴我，他的基本思想是要reinvention, 一個是要發(fā)明新的網(wǎng)絡，另一個是要發(fā)明新的操作系統(tǒng)。他們認為，改進互聯(lián)網(wǎng)應該是思科等公司的事，NSF不必為大公司賺錢操心。當網(wǎng)絡帶寬達到10Tbps時，分組交換可能已不能有效地工作?，F(xiàn)在的互聯(lián)網(wǎng)只相當于郵政系統(tǒng)，NSF應致力于發(fā)明相當Express快件系統(tǒng)的新網(wǎng)絡。在操作系統(tǒng)方面，NSF不應再支持研究Unix或Linux，而是要創(chuàng)造新的操作系統(tǒng)。
     NSF的科研布局使我想起了美國麻省理工學院（MIT）的“不為”原則：“不做只要努力一定能成功的課題”，即要做沒有成功把握的研究。我國863計劃中有不少工程性很強的項目，要求一定成功是無可非議的。但即使是基金和973項目中，帶有reinvention 性質的項目也不多。今后，我們需要做一些目前還不能保證成功的研究。

2．內容處理已成為必須突破的核心技術
      當前，內容處理已成為網(wǎng)絡瀏覽檢索、軟件集成（Web服務）、網(wǎng)格等計算機應用的瓶頸，語義處理也是下一代操作系統(tǒng)的核心技術。形形色色的軟件技術最終都卡在語義上，語義處理已成為需要突破的關鍵技術。人工智能、模式識別等技術已有相當進展，但內容處理還處于重大技術突破的前夜，究竟什么時候能真正取得突破性的進展現(xiàn)在還難以預見。
      馮·諾依曼的最大貢獻是提出了在單臺計算機上把程序視同為數(shù)據(jù)的程序存儲式計算機模型，而語義研究的目標是在整個網(wǎng)絡上實現(xiàn)將程序視同為數(shù)據(jù)。目前的瀏覽器已能做到不區(qū)分本地和遠程的數(shù)據(jù)，將來可能實現(xiàn)的基于語義的操作系統(tǒng)應做到不區(qū)分本地和遠程的程序。也就是說，我們的目標是實現(xiàn)廣義的馮·諾依曼計算機，即聯(lián)網(wǎng)的計算機真正變成一臺計算機，在全球網(wǎng)絡上實現(xiàn)程序等同于數(shù)據(jù)。這是計算機科學家夢寐以求的理想，我們要持之以恒地追求。

六、計算機科學要成為提高辦事效率與質量的“事理學”

1．計算機科學本質上是“事理學”
      相對于研究物質結構原理的物理學，計算機科學本質上是研究做事效率和成本的“事理學”。所謂做事包括科學工程計算、事務處理、信息服務等各種人類想做的事情。辦事就要講求章法、講求系統(tǒng)、講求組織，不僅僅是算法。蓋一幢大樓，包括土木、水電、供暖等各種子系統(tǒng)，建筑公司可以做到相互配合井井有條；但編制大型軟件失敗的項目比比皆是，原因多半出在各部件和子系統(tǒng)無法協(xié)調配合。我們應不應該反思：計算機科學究竟缺了些什么？這里面可能有些根本性的規(guī)律我們沒有掌握，怎么把一個事情做成功、做好，不僅僅是一個算法優(yōu)化問題。

2．關注服務科學
      最近，IBM公司提出一個新的目標，叫做服務科學（Service Sciences）。專家們認為，服務科學可以將計算機科學、運籌學、產(chǎn)業(yè)工程、數(shù)學、管理學、決策學、社會學和法律學在既定領域內融合在一起，創(chuàng)建新的技能和市場來提供高價值的服務。促進技術和商務更緊密結合需要新的技能和技能組合，這些技能和應用方法必須從大學起開始教授，創(chuàng)建“服務科學”學科的想法從此誕生。
      在美國，整個服務行業(yè)創(chuàng)造的價值已占全部GDP的70%以上，服務也需要科學做指導。IBM提出的服務科學全稱是SSME，即服務科學、管理和工程，將服務看成科學、管理和工程的結合，把計算機和商務緊密聯(lián)系起來了。美國很多學校已經(jīng)開設了服務科學課程，將來培養(yǎng)出來的就是美國的行業(yè)工程師。若干年前，當有人從計算機硬件軟件中提煉出計算機科學時，不少人奚落嘲笑；現(xiàn)在服務科學剛剛出現(xiàn)地平線上，我們不應當挑剔它的幼稚，要以敏銳的洞察力捕捉先機。

七、計算機科學應成為跨領域的二元或多元科學

1．尋找被打斷的“溝通鏈條”
      近代科學學科劃分過細、條塊分割，反而模糊了人們對事物的總體性、全局性的認識。德國著名的物理學家普朗克認為：“科學是內在的整體，它被分解為單獨的部分不是取決于事物本身，而是取決于人類認識能力的局限性。實際上存在從物理到化學，通過生物學和人類學到社會學的連續(xù)的鏈條，這是任何一處都不能被打斷的鏈條”。早在100多年前，馬克思在《經(jīng)濟學--哲學手稿》中曾預言：“自然科學往后將會把關于人類的科學總括在自己下面，正如同關于人類的科學把自然科學總括在自己下面一樣，它將成為一個科學?！泵鎸χ絹碓綇碗s的問題，許多研究者開始探索從整體出發(fā)的研究方法，試圖尋找那條被打斷的“溝通鏈條”。

2．形成跨領域的二元或多元計算機科學
      計算機科學需要強調與自然科學、社會科學的交叉，應該成為跨領域的二元或多元科學。將計算機學科分成科學與工程已不合時宜，南加州大學不再按照體系結構作分界線區(qū)分計算機科學和計算機工程，而是按分析與綜合分類的新框架做區(qū)分，以分析為主的叫科學，以綜合為主的叫工程，計算機科學主要內容是跨學科的分析，計算機工程主要從事面向系統(tǒng)的綜合。計算機科學要大大加強與物理學、生命科學及社會科學的交叉研究，形成計算物理學、計算生物學、社會計算等新學科，還可以形成“計算機+生命+物理”、“計算機+生命+社會”等三元交叉科學。這些交叉學科不僅僅是計算機的應用擴展，而是我們需要高度重視的計算機科學的未來主流方向。
      要做好這些交叉學科研究，必須加強以超級計算機為基礎的計算機模擬與仿真。我們不能認為在Computer+X的交叉學科中，計算機只不過是一個工具。實際上這是若干新的科學，它既不是傳統(tǒng)的計算機科學，也不是原來的X學，而是把這兩方面或幾方面融合起來的新科學。計算機的發(fā)展對未來人類社會也將有重大影響。計算機科學家不但要和其他領域的自然科學家合作，還需要和社會學、經(jīng)濟學、新聞傳播等方面的社會科學家更密切地合作?？傊?，今后計算機科學的研究，不能完全像過去一樣走越分越細的以歸約還原為主的道路，應當考慮走一條強調綜合集成的新道路。

八、對計算機學科教育的反思
      和美國NSF信息學部主任趙偉教授的一次對話引起我一些反思，趙偉教授認為，美國學科教育的發(fā)展有不同模式，有些封閉保守，有些開放包容。美國較好的學科教育發(fā)展模式可能是醫(yī)學院和法學院，所有相關的知識都吸納在本學院里，其他的學院一般不教醫(yī)學和法律課程。工程學科也有較好的吸納性，其他學院一般不會開設電路設計課。但計算機學科是發(fā)散的學科，其他學院可開設各種與計算機有關的課程。計算機科學會不會像數(shù)學一樣把相關的知識都推出去，只剩下很少的內容？計算機學院將來教什么課？
我國一些計算機教育專家也發(fā)現(xiàn)了同樣的問題，他們擔心計算機科學將逐步變成與現(xiàn)在數(shù)學差不多成為一門公共課。其實，如上所述，計算機科學方興未艾，還有許多計算機科學應該重視的內容尚沒有我們進入我們的視野，尤其是計算機科學與自然科學、社會科學的交叉將會大大充實計算機科學的內涵。我們真應當好好梳理一下，不要懵懵懂懂把計算機科學引入了很窄的死胡同。

致謝
本文有些觀點是在與美國NSF信息學部主任趙偉教授及其他學者討論中形成的，在此一并表示感謝。

2005年12月發(fā)表于《中國計算機學會通訊》