約翰·霍潑克洛夫特

霍潑克洛夫特1939年10月7日生於西雅圖。1961年在西雅圖大學獲得電氣工程學士學位以後，進入斯坦福大學研究生院深造，1962年獲得碩士學位，1964年獲得博士學位，也就是說只用了3年時間他就拿下了2個學位，霍潑克洛夫特的勤奮和聰穎由此可見。學成以後，霍潑克洛夫特曾先後在普林斯頓大學、康乃爾大學、斯坦福大學著名學府工作，也曾任職於NSF(美國科學基金會)和NRC(美國國家研究院)，從事對科學研究的規劃和行政管理工作，但時間不長。

霍潑克洛夫特成為著名的計算機科學家起源於一個十分偶然的機會。霍潑克洛夫特學習的專業是電氣工程，原先對計算機科學沒有多少知識，只學過一門“開關電路和邏輯設計”算多少有些關係。因此他原打算畢業後去西海岸的一所大學執教電氣工程方面的課程。

但就在畢業以前，有一次他偶然經過他的導師、研究神經網路的先驅和著名學者威德羅(BernardWidrow)辦公室的門口，當時，普林斯頓大學的麥克盧斯基教授(EdwardMcCluskey，曾任IEEE計算機協會主席)正為籌建數字系統實驗室打電話給威德羅，請他推薦博士生去那裡工作。威德羅一眼瞥見從門口走過的霍潑克洛夫特，覺得勤奮好學，悟性又高的這位得意門生正是一個值得推薦的人才，當即把霍潑克洛夫特叫進辦公室，並把電話聽筒遞給了他。霍潑克洛夫特在電話里聽了麥克盧斯基對普林斯頓大學擬建數字系統實驗室的情況介紹，以後又前去面談了一次，實地了解一番以後，對這一新的學科產生了興趣，欣然接受了普林斯頓的聘任，從而改變了他一生的道路。

年青的霍潑克洛夫特來到普林斯頓之後接受的第一項任務是開設一門新課：自動機理論。這對他來說是富有挑戰性的，因為他之前並未接觸過這個課題。面對挑戰，他以極大的熱情收集、鑽研和消化了大量有關材料，加以分析、綜合和比較。這樣，在霍潑克洛夫特的努力下，有關自動機理論的一些分散、複雜的材料第一次被全面地條理化、系統化，因此他的講課理所當然地受到了學生極大的歡迎。後來，霍潑克洛夫特和厄爾曼(J.D.Ullman)又合作編寫了《形式語言及其與自動機的關係》 (《FormalLanguageandTheirRelationtoAutomata》，Addison-Wesley,1969)一書，這本書被認為是自動機理論中有代表性的一部著作。

然而，霍潑克洛夫特更感興趣的課題是演演算法。當時，演演算法複雜性理論雖已由哈特馬尼斯(J.Hartmanis)、斯坦恩斯(R.Stearns,這兩人是1993年圖靈獎獲得者)和布魯姆(M.Blam，1995年圖靈獎獲得者)等人奠定了基礎，但對具體演演算法的效率和優劣的判斷尚未建立起客觀和明確的準則，因此，往往出現下述情況：有人公布了一個演演算法，給出對若干樣本問題的執行時間；過了一段時間，另外一個人發布“改進演演算法”，給出對相同樣本問題的執行時間(當然比前者少)。而實際上，這很可能是由於機器性能提高或(和)語言改進所致，所謂“改進演演算法”其實不見得比原演演算法高明。霍潑克洛夫特對這種情況很不滿意，決心加以解決。經過反覆研究，他終於提出了一種稱為“最壞情況漸近分析法”(Worst-caseasymptoticanalysisofalgorithm)，這種方法先確定問題和大小尺度，然後把計算時間當作問題大小尺度的一個函數去算出計算時間的增長率，以此衡量演演算法的效率和優劣。這個方法由於與機器性能及所用語言無關，成為測量演演算法好壞的數學準則，被學界所廣泛認同和接受。

但是導致他和塔揚共同獲得圖靈獎的最主要貢獻則是他們解決了圖論演演算法中的一些難題。1970年，霍潑克洛夫特在康乃爾大學獲得一年休假(他是1967年被另一圖靈獎獲得者哈特馬尼斯招至麾下的)。他決定回母校斯坦福大學到克努特(D.Knuth)教授名下做研究，因為克努特雖然只比他年長一歲，但因在1967年和1968年連出兩卷《計算機程序設計的藝術》 (《TheArtofComputerProgramming》)而已名滿天下，成為演演算法領域的權威。克努特知道霍潑克洛夫特對演演算法感興趣並有獨到見解，就把他和自己的得意門生、研究方向也是演演算法的塔揚安排在一個辦公室，為他們的合作創造了條件。他們選擇了圖論中與實際應用有很大關係的圖的連通性和平面性測試難題進行攻關。拿平面圖來說，它對印刷電路板設計這樣一類問題有十分重要的意義。學過圖論的人都知道，平面圖的判斷問題，在數學上已由波蘭數學家庫拉托夫斯基(Kuratowski)於1930年解決。庫拉托夫斯基的判據原理看似簡單，但實現起來很難。對於有100個頂點的圖，用普通的演演算法，計算機需要1萬億步才能確定其是否為平面圖！因此，尋找高效的平面圖測試演演算法成為擺在當時計算機科學家面前的一大難題。霍潑克洛夫特和塔揚都是富有創造性的人，又都善於合作共事，因此當兩朵智慧的火花碰在一起時，就很快迸發出耀眼的光芒！在解決這個難題的過程中，霍潑克洛夫特首先提出了一種新的思路、新的演演算法，經過塔揚的反覆推敲和完善，一種適於解這類問題的新的演演算法終於誕生了，這就是“深度優先搜索演演算法”(depth-firstsearchalgorithm)。利用這種演演算法對圖進行搜索時，結點擴展的次序是向某一個分枝縱深推進，到底后再回溯，這樣就能保證所有的邊在搜索過程中都經過一次，並且只經過一次，從而大大提高了效率。新演演算法的運行時間是線性的，也就是說時間與圖的大小成正比關係，大小翻一倍，解問題所需的時間也只翻一倍。相比之下，若用庫拉托夫斯基判斷的老演演算法，那麼當圖的大小翻一倍時，所需時間要增加60倍以上。利用他們創造的新演演算法，塔揚用Algolw為一個包含900個結點和2694條邊的圖編製了一個測試其平面性的程序，程序只有500行，在IBM360/67上運行，只用了12秒就得到了結果。霍潑克洛夫特和塔揚把他們的研究成果寫成論文在《JournaloftheACM》上發表，引起學術界很大的轟動。而他們創造的深度優先演演算法則被推廣到信息檢索、國際象棋比賽程序、專家系統中的衝突消解策略等許多方面。在霍潑克洛夫特和塔揚獲得圖靈獎的授獎儀式上，當年的計算機象棋程序比賽的優勝者就說，他的程序中使用了霍潑克洛夫特和塔揚所發明的深度優先搜索演演算法，這是他的程序所以能出奇制勝的關鍵。

在取得輝煌成功之後，霍潑克洛夫特和塔揚並不滿足，他們致力於開發效率更高的演演算法。不久，他們又提出了一種新的數據結構叫“雙堆棧疊”（pileoftwinstacks），這種新的數據結構被深度優先搜索演演算法的優點更加發揚光大。塔揚的一個學生用這種新的數據結構和演演算法編寫了一個Algolw程序，只有250行，在IBM370/168上測試有8000個結點的圖的平面性只用了8秒鐘。

霍潑克洛夫特除了和塔揚合作取得上述成果外，在數據結構和演演算法方面還有其他一系列創造。比如常用於索引組織的著名數據結構B樹(B-tree)是一種平衡的多分樹，由於對查找、插入、刪除等操作能始終保持動態平衡，具有高效的特性。霍潑克洛夫特在對B樹進行深入研究以後，為了進一步提高其操作效率和空間利用率，提出了它的一種變形叫2-3樹，這種樹的每個結點有2個鍵，每個鍵都有2-3個兒子。

《計算機演演算法的設計與分析》

《數據結構和演演算法》

《自動機理論，語言和計算的導論》

《計算機科學：成就與機遇》

書名：《形式語言及其與自動機的關係》

作者：(美)霍普克羅夫特(J.E.Hopcroft),(美)厄爾曼(J.D.Ullman)著

價格：RMB1.05

發行地：北京

出版社：科學出版社

出版時間：1979年

頁數：316頁

開本：19cm

圖靈獎

圖靈獎，是國際計算機協會（ACM）於1966年設立的，又叫“A.M.圖靈獎”，專門獎勵那些對計算機事業作出重要貢獻的個人。其名稱取自計算機科學的先驅、英國科學家阿蘭·圖靈，這個獎設立目的之一是紀念這位科學家。獲獎者的貢獻必須是在計算機領域具有持久而重大的技術先進性的。大多數獲獎者是計算機科學家。

圖靈獎是計算機界最負盛名的獎項，有“計算機界諾貝爾獎”之稱。圖靈獎對獲獎者的要求極高，評獎程序也極嚴，一般每年只獎勵一名計算機科學家，只有極少數年度有兩名以上在同一方向上做出貢獻的科學家同時獲獎。目前圖靈獎由英特爾公司贊助，獎金為100,000美元。

每年，美國計算機協會將要求提名人推薦本年度的圖靈獎候選人，並附加一份200到500字的文章，說明被提名者為什麼應獲此獎。任何人都可成為提名人。美國計算機協會將組成評選委員會對被提名者進行嚴格的評審，並最終確定當年的獲獎者。

截止至2005年，獲此殊榮的華人僅有一位，他是2000年圖靈獎得主姚期智。

圖靈獎對獲獎者的要求極高，評獎程序極嚴，一般每年只獎勵一名計算機科學家，只有極少數年度有兩名在同一方向上做出貢獻的科學家同時獲獎。因此，儘管“圖靈”的獎金數額不算高，但它卻是計算機界最負盛名的獎項，有“計算機界諾貝爾獎”之稱。