對於不熟悉計算機科學的人來說,東尼·霍爾可能是個陌生的名字,但是他為計算機科學發展做出的突出貢獻可以說是造福了每一個現代人。
他在26歲時發明的快速排序算法,如今全世界每天都有程序員在使用。
今天讓我們一起來走近這位偉大的科學家。
哲學經歷造就了超強的思維能力
1934年1月11日,東尼·霍爾出生於當時還是英國殖民地的斯里蘭卡。
在學生時代,他就讀於英國牛津大學,專業是西方哲學,兼習拉丁語和希臘語。
1956-1958年,在皇家海軍服役期間,他又開始學習俄語。
東尼·霍爾除了研讀古希臘哲學家亞里士多德和柏拉圖的古典哲學著作,對當代哲學家羅素和艾耶爾的思想也有深入瞭解。他最感興趣的課程是數學哲學和科學哲學。
在當時,哲學家已經對計算這個話題進行了許多有益的探討。在他們看來,計算本身是一種可以用來探索世界、探索人類思維和人類邏輯思考的一個有效途徑。
在19世紀早期,沒有大學專門開設計算機科學相關課程,但是此時東尼·霍爾的哲學思維能力已經為他後來走上計算機科學的研究道路奠定了堅實基礎。
東尼·霍爾在接受《程序員》雜誌採訪時也曾談到:
“我覺得早期學習哲學的經歷讓我在思考時具備了分析框架的能力。”
“當我思考一個問題的時候,不管這個問題是什麼,我基本上能夠考慮得到這個問題的所有方面,接著想出多種不同解決方法。然後,我會選擇其中最令人信服的、最好的,甚至是最優雅的一種方法。”
快速排序算法的發明
1959年,作為莫斯科國立大學的學生,東尼·霍爾開始研習機器語言翻譯,也是在這個時候他開始學習編程。
在取得博士學位後,英國國家物理實驗室給了他一個工作機會,該項目主要是用機器翻譯的方法,把俄語翻譯成英語。
當時的字典錄在磁帶上,每次要花幾分鐘時間倒半個磁帶,才能找到一個詞。
要怎麼解決花費時間過長這個問題呢?
東尼·霍爾想了一個辦法:把一個句子當中所有的詞,儘量一次性的都查出來。然後按照它在字典中的順序加以排列,再到磁帶當中去找。
一開始,他想到的方法叫做「冒泡排序」,也就是說一次查一個詞。但是,這樣做查起來還是很慢。
後來,他想到了一個常用的理論「分治法」。
在解決一個問題的時候,先把這個問題分割成兩個部分。這兩個部分比起初的問題要小,但是和原先的問題很類似。然後,針對分割出來的部分找解決方法。最後,再把兩個解決方法結合起來,回頭來解決這個最初的問題。
這就是在算法上應用最廣泛、最著名的發明——快速排序。
專注學術研究
之後,東尼·霍爾在當時還是小型設備製造公司的倫敦艾略特兄弟公司「Elliott Brothers」擔任程序員。也就是從這個時候開始,他將重心轉向了計算機算法研究方面的工作。
他帶領一個小團隊,用高級計算機語言「Algol 60」設計並研發一個早期的彙編程序。項目大獲成功,他也因此晉升為了首席工程師,開始領導更大的團隊實現一整個操作系統的研發。
這段時光給東尼·霍爾留下了美好而難忘的回憶,在Algol 60彙編語言的運用上,東尼·霍爾已經達到了爐火純青的狀態。他認為這個項目的成功,很大程度上是因為使用了Algol 60作為設計語言。
東尼·霍爾曾表示:“我最鍾情的語言是我最開始使用的Algol 60 。”
正是東尼·霍爾這種返璞歸真、堅定初心的態度,讓他在日後的研究中總能撥開雲霧看清問題的本質,並以最直接且最純粹的方式解決它,不斷攻克難題。
時間來到1968年,東尼·霍爾申請了皇后大學的計算機科學教授職位,於是他舉家搬到了貝爾法斯特,開始了在高校中的研究和教學工作。
那個政治動盪的年代,卻絲毫沒有影響他的學術研究。
東尼·霍爾在皇后大學啟動他的研究工作後,還建立了一個強大的教學研究部門,並撰寫了一系列高水平論文,以一種相對簡單的編程語言來從事程序的驗證。這種思想與他之前堅持返璞歸真的問題解決策略,保持著高度一致性。
東尼·霍爾知道這是一項長期的研究,有可能在他的整個學術生涯中都無法實現全面的工業應用。但是他可能從未預見到,這些研究工作在整個行業當中,特別是在接下來30年的時間裡能夠一直為人們津津樂道。
1977年,他轉至牛津大學繼續從事相關研究,並著手建立編程研究小組。在政府倡議、工業合作和慈善捐款的外部資助下,他設立了與計算科學有關的多個本科與碩士學位,包括工業軟件工程師的外部碩士學位。
他在牛津大學的研究團隊追求的理想是,將可證明的正確性作為計算系統精確規範、設計和開發的驅動力。團隊著名的研究成果包括規範語言和CSP併發編程模型。
舉世矚目的大獎獲得者
1980年,由於在計算機領域突出的學術貢獻和對學科領域的深遠影響,東尼·霍爾獲得了計算機界的諾貝爾獎——圖靈獎(Turing Award)。這個獎項由「美國計算機協會」於1966年設立,專門獎勵那些對計算機事業作出重要貢獻的個人。
圖靈獎對獲獎條件要求極高,評獎程序極嚴,一般每年只獎勵一名計算機科學家,它也是計算機界最負盛名、最崇高的一個獎項。東尼·霍爾可謂是實至名歸。
1982年,東尼·霍爾被評選為英國皇家學會院士。
2000年,因為他在計算機科學與教育方面做出的傑出貢獻,獲得英國王室頒贈「爵士」頭銜。
在30多年的學術生涯中,東尼·霍爾通過諮詢、教學和合作研究項目與業界保持著密切的聯繫。
1999年,在牛津大學達到退休年齡後,東尼·霍爾加盟微軟劍橋研究院,擔任高級研究員,從事程序精確性領域的深入研究,以及此領域某些早期研究成果的應用工作。
東尼·霍爾始終堅持自己熱愛的學術研究,雖然他如今已經是一位年近九十歲的高齡老師,但他仍然孜孜不倦,在計算機科學的發展道路上繼續前行。
算法、語言及可驗證理論——圖靈獎獲得者託尼·霍爾爵士採訪記,程序員,張蜀, 2009年第11期。
Quicksort,Computer Journal,Tony Hoare,1962.
算法導論,機械工業出版社,Thomas H.Cormen、Charles E.Leiserson,2006。
閱讀更多 夏暖教育 的文章