1986年ACM圖靈演講:電腦科學：一門學科的興起

圖靈獎演講電腦科學：一門學科的興起

電腦科學持續快速發展，需要擴展科學基礎並引進有才華的新研究人員。電腦已經改變了我們的思維和生活方式；現在它們將開始提升我們對世界的認知。

JOHN E. HOPCROFT

能夠榮獲 1986 年圖靈獎，我深感榮幸。除了獎項所帶來的榮譽，這次機會讓我得以發表這篇演講，不僅能對電腦科學家發言，也能對決策者和其他科學界的成員發言。我想先分享一些我在電腦科學領域的個人經歷，然後對這個學科的未來發展提出一些建議。

我於 1964 年開始我的電腦科學專業生涯，當時電腦科學才剛開始作為一門學術學科建立起來。身為電腦科學形成時期的學術社群一份子，我有幸觀察到它的演變、成熟和發展過程。我對這個領域懷有深厚的感情，並希望看到它持續繁榮發展。儘管電腦科學已經成為一門成熟的學科，但專業內部的有力領導和方向指引對於它充分貢獻於科學和社會仍然至關重要。

在我參與電腦科學的這些年裡，最讓我印象深刻的是參與者的投入程度。早期，我看到了強烈的個人投入。後來，我看到了機構與個人攜手合作，為電腦科學形成了強大的支持系統。今天，技術正在以前所未有的速度推動這個學科的發展，以至於個人和機構的共同投入已經不足以應對知識擴張帶來的挑戰。工業研究實驗室和學術機構對所需人才庫的需求遠遠超過目前的資源供給。為了從計算機的科學和技術進步中獲得最大的利益，必須做出並持續維護國家層面的承諾。

在進一步闡述這個需求之前，讓我們先回顧一下我職業生涯中將我帶到這個位置的一些事件。當我從 Stanford University 獲得電機工程博士學位時，我的教育只包含了一門計算機課程，由 David Huffman 教授。我在 Stanford 的最後一年恰逢 Huffman 在那裡的一年，正是從他那裡，我獲得了關於開關電路、邏輯設計和計算理論的基礎介紹。同年的春天，Edward McCluskey 正在為他在 Princeton 的數位系統實驗室招募教職員。碰巧的是，就在我經過 Bernard Widrow 辦公室時，他正在打電話給 Widrow 討論潛在的博士候選人。Widrow 看見我時，他招手讓我進到他的辦公室並遞給我電話，我們於是安排了我拜訪 Princeton。除了 Huffman 的課程外，我沒有正式的電腦科學教育背景，這並沒有阻礙 McCluskey。當時，很少有人具有計算機教育背景。拜訪之後，McCluskey 對電腦科學的投入以及他為我在計算科學這個發展中學科開始職業生涯提供的機會讓我印象深刻，以至於我一收到他的聘用邀約就接受了。這個決定極大地改變了我的職業規劃，因為在 McCluskey 打電話之前，我原本計劃在美國西岸教授電機工程。

電腦科學的轉變與自動機理論課程的建立

我於 1964 年秋天抵達 Princeton，當時計算機領域正發生著劇烈的變化。當時電腦科學的許多課程內容都集中在數位計算機的電路設計以及如何最小化構建這些電路所需的電晶體數量。然而，到了六十年代中期，技術已經進步到電晶體即將被每個晶片包含多達一百個元件的計算機晶片所取代。因此，最小化電晶體的數量不再重要。正如你所想像的，這對當時稱為電腦科學的學科產生了深遠的影響；現有的課程即將過時，必須開發新的課程。

Princeton 要求我開設一門自動機理論課程，以擴展課程範圍，超越當時提供的數位電路設計課程。由於當時沒有相關的課程或書籍，我請 McCluskey 推薦一些自動機理論的材料。他自己也不太確定，但他給了我一份包含六篇論文的列表，並告訴我這些材料可能會為學生提供良好的自動機理論基礎。McCluskey 的列表包括了 Warren McCulloch 和 Walter Pitts、John Backus 和 Peter Naur、Noam Chomsky、Michael Rabin 和 Dana Scott、Juris Hartmanis 和 Richard Stearns，當然還有 Alan Turing 的著作。

當時，我覺得人們在尚不完全了解課程內容的情況下就準備將其引入課程是很奇怪的。回想起來，我意識到那些相信一個主題未來、並感知其重要性的人，會在他們能界定其邊界之前很久就投入於這個主題。

電腦科學概念的多元起源

當我回顧早期自動機理論課程的材料時，我對這些來源的多樣性感到震驚。1943 年，在神經生理學領域工作的 McCulloch 和 Pitts 發表了一篇關於描述神經網絡中事件的邏輯演算論文。這些事件是一系列電脈衝，可以看作是零和一的字串。這篇論文提供了一種表示法來描述這些零和一的字串如何在神經元中組合產生新的零和一字串。這種表示法後來發展成為用於描述字串集合的正規表達式語言。

Rabin 和 Scott 是數學家，他們開發了一個具有有限記憶體的計算機模型。他們將這個模型稱為有限狀態自動機，並表明有限狀態自動機的可能行為正是可以由源自 McCulloch 和 Pitts 工作的正規表達式所描述的行為。來自兩個截然不同學科的思想匯聚，幫助早期電腦科學家確信正規表達式和有限自動機的重要性。

Chomsky 是一位語言學家，一直在研究自然語言的語法。在他的工作中，他發展了上下文無關文法的概念。大約在同一時間，兩位電腦科學家 Backus 和 Naur 正試圖開發用於描述程式語言的形式化方法。1960 年之前，程式語言通常通過冗長且往往不完整的口頭描述來定義。各種語言實現中的不一致性常常使得在系統之間轉移軟體變得困難。Backus 和 Naur 開發了一種形式化表示法來描述各種程式語言的語法。令人驚訝的是，他們的表示法與 Chomsky 開發的上下文無關文法是等價的。

Turing 早在 1936 年就引入了一個簡單的計算設備模型，現在稱為 Turing machine。這個設備足夠簡單，毫無疑問任何由它計算出來的函數都是可計算的。然而，Turing 進一步論證說，他的模型可以計算所有被認為是可計算的函數。簡單來說，任何可以執行的計算過程都可以在 Turing machine 上編程。今天，這個假設被普遍接受，並且 Turing machine 是現代可計算性理論的基礎。

Turing 的工作可能仍停留在數學和邏輯領域，如果不是數學家 Hartmanis 和 Stearns 發表的一篇關於演算法計算複雜度的開創性論文。他們通過執行所需步驟的數量來衡量演算法的複雜度，並用這種方法開發了複雜度類別理論。這篇論文激發了許多電腦科學家的想像，並促使複雜度理論成為這個學科不可或缺的一部分。

基礎研究的乘數效應與個人經歷

某些研究論文之所以重要，不僅因為其技術貢獻，更重要的是，它們提供了一個概念性的觀點或為研究確立了一個範式。Hartmanis 和 Stearns 的工作吸引了研究人員，並將注意力集中在複雜度這個主題上。由此產生的更重要的進展包括大多數主要數學理論的複雜度分類、許多組合問題的可歸約性、NP完全性的概念以及對隨機性等概念更深層次的理解。

因此，早期的自動機理論課程強調了電腦科學的兩個重要方面：它如何利用來自不同領域的眾多思想來發展和擴展，以及基礎研究如何複合和加速計算的進步。就個人而言，這門課程對我的職業生涯產生了巨大的影響。通過它，我認識了 Jeffrey Ullman 和 Alfred Aho，隨後與他們合作了多年。我與 Ullman 合著的《形式語言與自動機理論》也是從這門課程演變而來的。

1967 年春天，Princeton 要求我舉辦一系列研討會。如同往常一樣，研討會經費有限。原本打算邀請本地講者；然而，資金剛好夠邀請兩位來自 200 英里半徑範圍外的講者。基於我對自動機理論的興趣，我邀請了 Chomsky 和 Hartmanis，他們都同意發表演講。Hartmanis 的來訪對我的職業生涯產生了重大的影響。在他的來訪期間，他問我關於 Cornell 教職員職位的潛在博士候選人。那天晚上我們就計算科學科學基礎的重要性以及 Cornell 已經建立了一個獨立的電腦科學系所進行的討論，促使我問是否可以考慮我擔任其中一個職位，而不是一個新的博士候選人。拜訪 Cornell 後，我立即接受了他們的聘用邀約。

從自動機理論轉向演算法與資料結構

我第一次得知 Cornell 對電腦科學的承諾是從 Hartmanis 拜訪前一年——1966 年——出現的一篇新聞報導。當時，電腦科學系所正在迅速建立，其速度超過了補充教職員的供給。這篇報導討論了 Cornell 意識到這個問題以及他們為解決它所做的努力。三位來自數學和工程系的教授說服了 Sloan Foundation 捐贈一百萬美元來發展一個獨立的電腦科學系，以培養其他機構正在創建的電腦科學系所需的博士人才。

到我 1967 年抵達 Cornell 時，自動機理論和複雜度理論已經確立為電腦科學課程的一部分。因此，在更換機構後不久，我決定更換研究領域，開始研究演算法和資料結構。我相信理論電腦科學的方法可以用來為演算法設計建立一個科學基礎，這將對實踐者有用。

在 1960 年代，關於演算法的研究令人非常不滿意。一個研究人員會在期刊上發表一個演算法，並附上針對一小組樣本問題的執行時間，然後幾年後，第二個研究人員會提供一個改進的演算法，並附上針對同一組樣本問題的執行時間。新的演算法總是會更快，因為在 intervening years 中，計算機性能和程式語言都得到了改進。由於這些演算法在不同的計算機上運行，並使用不同的語言編程，這讓我對比較感到不舒服。很難排除計算機性能提升和實施者的程式設計技能的影響——去發現由於新演算法而非其實施而產生的效果。此外，第二個研究人員可能無意中將他或她的演算法調整到適合樣本問題。理論上，如果在另一組樣本問題上再次運行這兩個演算法，原始演算法可能表現得比新的演算法更好。

我開始證明，基於最差情況漸近效能的演算法設計理論，可以成為對實踐者有價值的幫助。首先，將一個大小與每個問題實例相關聯；然後通過計算計算時間隨問題大小增長的速率來衡量演算法的複雜度。由於估計輸入分布存在問題，採用了對給定大小的所有輸入進行最差情況分析作為複雜度衡量標準。

最差情況漸近複雜度存在一些問題。一些漸近最優的演算法在數值上不穩定；另一些則過於複雜，不太可能被程式設計。此外，對於實際輸入分布的預期時間將是一個更合理的複雜度衡量標準。但是，最差情況漸近複雜度的範式為衡量演算法的優劣提供了一個數學標準，使得可以提出「一個問題的最優演算法是什麼？」和「一個問題的內在複雜度是什麼？」等問題。這個想法遇到了很大的阻力。人們認為更快的計算機將消除對漸近效率的需求。然而，事實恰恰相反，因為隨著計算機變得更快，嘗試解決的問題規模也變得更大，從而使漸近效率變得更加重要。

與 Robert Tarjan 的合作及其影響

1970 年初，我在 Stanford University 度過了一個為期一年的學術休假，在那裡我遇到並與二年級研究生 Robert Tarjan 共用一個辦公室。1986 年圖靈獎所認可的研究正是在那段合作期間進行的。我們一起研究了許多圖演算法，包括圖連通性和平面性測試。我們採用了針對最差情況性能進行設計的理念，並證明了幾種簡單的技術可以用於在許多計算機應用領域構建高效的演算法。我們能夠證明我們的一些演算法在一個常數因子內具有最差情況最優性能，並且所產生的演算法的性能遠遠超過現有的演算法。我們的平面性演算法能夠在大約 10 秒內測試具有 1000 個頂點的圖——比現有演算法快兩個數量級。我們的研究結果吸引了許多研究人員，他們的努力創造了新的資料結構和設計技術。今天，這個領域已成為電腦科學不可或缺的一部分。再次強調，重要的不是某個特定的演算法，而是我們的工作激發了他人的想像。它還吸引了聰明的新一代研究人員，他們繼續將資料結構和演算法確立為一個重要的子學科。

電腦科學的未來：觀察與建議

我想對電腦科學的未來提出一些觀察和建議。在我的職業生涯中，我看到了隨著電腦科學的發展和擴張，個人和機構的承諾也在增長和擴張。然而，我相信，電腦科學能夠作為一門學科出現，很大程度上歸功於相對少數研究人員的奉獻和承諾，他們對計算的潛力懷有願景，並有毅力將這個願景變為現實。現在，我們的責任是制定一個新的願景，為下一代研究人員塑造目標。重要的是，電腦科學家要分享這個新的願景並將其變為現實。

今天，電腦幾乎滲透到了現代生活的各個方面。它們用於農業、通訊、教育、製造業和醫學。它們用於預測天氣、優化糧食生產、控制太空中的衛星、開發新藥以及製造節能汽車。在醫學領域，它們在斷層掃描中的應用可以對重要器官進行精確成像，輔助診斷和治療。在商業界，它們用於路由訊息、處理商業交易和訪問資料庫。它們正在物理學、化學和生物學領域推進知識的前沿。電腦也將在這個國家的經濟復興中發揮至關重要的作用。

電腦已經對我們的思維和生活方式產生了重大影響。然而，我預見會有更大的影響。如果充分探索和發展，電腦科學的潛力將把我們帶到更高層次的知識領域。電腦科學將幫助我們更深入地理解智力過程。它將增強我們對學習過程、思維過程和推理過程的了解。電腦科學將為認知科學提供模型和概念工具。正如物理科學在本世紀主導了人類的智力活動，因為研究人員探索物質的本質和宇宙的開端，今天我們正開始探索思想、知識結構和語言的智力宇宙。我預見將繼續取得重大的進展，這將極大地改變我們的生活。Tarjan 和我於 1970 年代開始的工作已經讓我們了解了資料結構以及如何操作它們。展望未來，我預見將能了解如何組織和操作知識。

在六十年代，技術的變化將電腦科學的範圍從電路設計擴展到了計算。今天地平線上計算能力的巨大增長將再次從根本上改變電腦科學。沒有人能預見具體的細節，但我們可以感知到理解語言語義、抽象和知識表示的潛力。正如早期的研究人員在完全理解細節之前願意投入精力於電腦科學一樣，我們也必須在完全辨識其形狀之前，承諾於電腦科學的未來。

今天，有跡象表明電腦科學正在轉向應用領域。隨著它將其模型、工具和技術貢獻給這些新領域，這些新領域反過來也將貢獻新的思想和方法論，極大地豐富和擴展電腦科學的範疇。潛在地，我們正處於科學新一輪增長浪潮的門檻上。然而，有兩個領域阻礙了我們跨過這個門檻。

科學基礎不足與研究人才短缺

首先是科學基礎的規模不足，以及缺乏足夠的研究人員來擴展它。儘管擁有相當可觀的知識、工具和技術體系，但電腦科學的科學基礎並沒有以應有的速度發展。隨著計算機技術的快速發展，很容易忽略發展計算機基礎科學基礎的重要性。將注意力簡單地集中在編寫軟體上，這個誘惑太大了。隨著我們構建越來越大、越來越複雜的系統，我們必須發展概念工具，以便能夠理解任務的本質，並開發構建完整系統所需的軟體工具。我們未能充分利用計算的益處，正是因為我們未能發展必要的科學基礎，以便快速且經濟地構建可靠且使用者友好的軟體系統。現有的程式語言不足以應對這項任務；它們似乎要求越來越高的技能水平。我們必須找到與計算機溝通的方式，以降低所需的技能水平，就像裝配線降低了生產過程中所需的技能水平一樣。將軟體生產力提高 100 倍，將使我們能夠在兩三天內而不是一年內設計、實施和安裝一個給定系統。這種改進取決於發展程式設計環境、軟體開發和人機介面的科學基礎。

顯然，早期研究人員建立的科學基礎已經帶來了益處。早期自動機理論課程中涉及的六篇論文，每一篇都為此做出了重要貢獻。例如，Backus 和 Naur 關於程式語言形式化描述工作的擴展，使我們能夠自動化編譯器語法分析部分的構建。早期的 Fortran 編譯器需要 20-50 人年精力。今天，我們將構建一種概念上比 Fortran 複雜得多的語言編譯器作為大學生期末專案，並看到它在學期內完成。這種巨大的改進歸功於形式語言科學基礎的發展。同樣的科學基礎使我們能夠構建編譯器編譯器，並根據特定需求定制語言。它允許化學家使用一種語言，其中的資料項是分子和化合價，而不是整數和字串。在資料庫、並行性、演算法、VLSI 設計工具等許多領域也做出了類似的貢獻。但是，必須做出更大的努力。

建立國家承諾的重要性

為什麼科學基礎落後於技術基礎呢？電腦科學領域爆炸性增長，比歷史上任何其他學科都快。它的獨特性在於它由來自不同背景的研究人員演變而來，而不是從現有學科中產生。其他領域，如分子生物學，受益於從更廣泛的學科中產生，這些學科可以貢獻各個年齡段的研究人員，以及資源和結構。電腦科學家來自許多背景，未能帶來母學科的支持結構。因此，電腦科學開始時沒有足夠數量的公認資深科學家，也沒有現有的支持結構來促進和引導其發展。

對電腦科學研究人員的需求不斷增加。即使在這個專業內部，研究人員之間也存在競爭。教育機構和研究實驗室對電腦科學家的需求增長速度快於該領域構建產生所需人才庫所需的基礎設施的速度。特別是電腦科學教職員的短缺，會產生嚴重的後果。除非投入足夠的資源為我們的教育機構提供足夠的研究人員，否則我們將在努力滿足這一不斷增長的對電腦科學家的需求方面進一步落後。

那些早期意識到電腦科學重要性並採取行動的大學，能夠建立最高質量的系所。總體而言，後起步的機構很難趕上。類似的情況正在國家層面出現。今天，全球正在為技術和經濟領導地位而奮鬥。計算機將在這場鬥爭中發揮關鍵作用。除非我們制定國家政策來支持電腦科學，否則我們將因自己的不作為，允許其他國家在計算領域建立我們無法克服的領先地位。

必須做出並持續維護對電腦科學的國家承諾。我們必須制定創新計劃，以提供充足的研究人才庫，更有效地利用現有的研究人員，並發展環境以促進計算各個方面的研究。我們必須提高公眾對電腦科學的認識。我們必須說服決策者，全面投入電腦科學的重要性。

CR 分類與主題描述: A.0 [一般文獻]: 一般—傳記~自傳; F.2.2 [演算法和問題複雜性分析]: 非數值演算法和問題; G.2.2 [離散數學]: 圖論; K.2 [計算環境]: 計算歷史—人物一般術語: 演算法, 設計, 效能, 理論額外關鍵詞和短語: John E. Hopcroft, Robert E. Tarjan, Turing Award 作者目前地址: John E. Hopcroft, Dept. of Computer Science, Cornell University, Ithaca, NY 14853.