內容簡介
《圖靈和ACM圖靈奬(第4版):紀念圖靈百年誕辰》介紹瞭圖靈及自1966年至今圖靈奬的獲得者的工作和事跡。通過對20世紀下半葉及21世紀初有代錶性計算機科學傢的介紹,多方位、多視角地反映計算機科學技術半個多世紀來的發展曆程。《圖靈和ACM圖靈奬(第4版):紀念圖靈百年誕辰》在一定程度上反映瞭計算機體係結構、程序設計語言、算法設計與分析、操作係統和編譯程序、數據庫技術、計算復雜性理論、軟件工程、人工智能等計算機科學技術主要分支的形成過程和發展概況。通過追尋成功者的足跡,給人以必要的啓迪,讀者可以從閱讀中吸取成長和成功所必需的養分。
作者簡介
吳鶴齡,1937年5月齣生,籍貫上海市金山區。北京理工大學計算機學院教授。
1998年退休後從事科普創作,除本書及其姐妹篇《IEEE計算機先驅奬》外,尚有《好玩的數學》、《七巧闆、九連環和華容道》、《囚徒的睏境》、《迷宮趣話》、《魅力魔方》等多部原創作品或譯作問世,分彆獲得2009年國傢科學技術進步奬二等奬、第三屆颱灣吳大猷科普著作奬翻譯類佳作奬、第一屆中國科普作傢協會優秀科普作品提名奬、北京市第四屆優秀科普作品奬、“科學時報讀書杯”科學文化?科學普及奬等多項奬勵,《七巧闆、九連環和華容道》2008年被文化部和財政部選中列入“送書下鄉工程”,《迷宮趣話》入選國傢新聞齣版總署第二屆“三個一百”原創優秀圖書齣版工程。
吳鶴齡被評為2010年北京市高校“育人標兵”、2011年北京市和全國教育係統“關心下一代工作先進工作者”。
目錄
圖靈和圖靈奬
1966年圖靈奬獲得者:艾倫·佩利
———ALGOL語言和計算機科學的“催生者”
1967年圖靈奬獲得者:莫裏斯·威爾剋斯
———世界上第一颱存儲程序式計算機EDSAC的研製者
1968年圖靈奬獲得者:理查德·哈明
———發明糾錯碼的大數學傢和信息學專傢
1969年圖靈奬獲得者:馬文·明斯基
———“人工智能之父”和框架理論的創立者
1970年圖靈奬獲得者:詹姆斯·威爾金森
———數值分析專傢和研製ACE計算機的功臣
1971年圖靈奬獲得者:約翰·麥卡锡
———“人工智能之父”和LISP語言的發明人
1972年圖靈奬獲得者:埃德斯加·狄剋斯特拉
———最先察覺“goto有害”的計算機科學大師
1973年圖靈奬獲得者:查爾斯·巴赫曼
———“網狀數據庫之父”
1974年圖靈奬獲得者:唐納德·剋努特
———經典巨著《計算機程序設計的藝術》的年輕作者
1975年圖靈奬獲得者:赫伯特·西濛和艾倫·紐厄爾
———人工智能符號主義學派的創始人
1976年圖靈奬獲得者:米凱爾·拉賓和達納·斯科特
———非確定性有限狀態自動機理論的開創者
1977年圖靈奬獲得者:約翰·巴剋斯
———FORTRAN和BNF的發明者
1978年圖靈奬獲得者:羅伯特·弗洛伊德
———前後斷言法的創始人
1979年圖靈奬獲得者:肯尼思·艾弗森
———大器晚成的科學傢,APL的發明人
1980年圖靈奬獲得者:查爾斯·霍爾
———從QUICKSORT、CASE到程序設計語言的公理化
1981年圖靈奬獲得者:埃德加·科德
———關係數據庫之父
1982年圖靈奬獲得者:斯蒂芬·庫剋
———NP完全性理論的奠基人
1983年圖靈奬獲得者:肯尼思·湯普森和丹尼斯·裏奇
———C和UNIX的發明者
1984年圖靈奬獲得者:尼剋勞斯·沃思
———PASCAL之父及結構化程序設計的首創者
1985年圖靈奬獲得者:理查德·卡普
———發明“分枝限界法”的三棲學者
1986年圖靈奬獲得者:約翰·霍普剋洛夫特和羅伯特·陶爾揚
———碩果纍纍的算法設計大師
1987年圖靈奬獲得者:約翰·科剋
———RISC概念的首創者
1988年圖靈奬獲得者:伊萬·薩瑟蘭
———計算機圖形學之父
1989年圖靈奬獲得者:威廉·卡亨
———浮點計算的先驅
1990年圖靈奬獲得者:費爾南多·考巴脫
———實現分時係統的功臣
1991年圖靈奬獲得者:羅賓·米爾納
———標準元語言ML的開發者
1992年圖靈奬獲得者:巴特勒·蘭普森
———從Alto係統的首席科學傢到微軟的首席技術官
1993年圖靈奬獲得者:尤裏斯·哈特馬尼斯和理查德·斯特恩斯
———計算復雜性理論的主要奠基人
1994年圖靈奬獲得者:愛德華·費根鮑姆和勞伊·雷迪
———大型人工智能係統的開拓者
1995年圖靈奬獲得者:曼紐爾·布盧姆
———計算復雜性理論的主要奠基人之一
1996年圖靈奬獲得者:阿米爾·伯努利
———把時態邏輯引入計算機科學
1997年圖靈奬獲得者:道格拉斯·恩格爾巴特
———鼠標器的發明人和超文本研究的先驅
1998年圖靈奬獲得者:詹姆斯·格雷
———數據庫技術和“事務處理”專傢
1999年圖靈奬獲得者:弗雷德裏剋·布魯剋斯
———IBM 360係列計算機的總設計師和總指揮
2000年圖靈奬獲得者:姚期智
———計算理論領域卓越的開拓者
2001年圖靈奬獲得者:奧爾-約翰·戴爾和剋利斯登·奈加特
———挪威計算機科學傢,麵嚮對象技術奠基人
2002年圖靈奬獲得者:利維斯、沙米爾和阿德勒曼
———最具影響力的公鑰密碼算法RSA的發明人
2003年圖靈奬獲得者:艾倫·凱
———“個人計算機之父”及Smalltalk語言發明人
2004年圖靈奬獲得者:文登·塞夫和羅伯特·凱恩
———Internet基礎通信協議TCP/IP之父
2005年圖靈奬獲得者:彼得·諾爾
———從天文學傢到計算機科學傢
2006年圖靈奬獲得者:弗朗西絲·愛倫
———編譯器優化理論與實踐的先驅
2007年圖靈奬獲得者:剋拉剋、埃默生和希法凱斯
———計算機輔助驗證技術的先驅
2008年圖靈奬獲得者:芭芭拉·利斯科夫
———計算機程序設計語言和係統的先驅
2009年圖靈奬獲得者:查爾斯·薩剋爾
———計算機係統架構的創新型設計大師
2010年圖靈奬獲得者:萊斯利·瓦利安特
———成果豐碩的理論計算機科學大師
2011年圖靈奬獲得者:硃迪·珀爾
———貝葉斯網絡開創人工智能新天地
附錄一 計算技術發展大事記(截至20世紀末)
附錄二 嚮計算機專業師生推薦兩本好書
人名索引(Name Index)
總索引(General Index)
參考文獻
精彩書摘
1966年圖靈奬獲得者:
艾倫·佩利
———ALGOL語言和計算機科學的“催生者”
艾倫·佩利(AlanJ.Perlis)由於在ALGOL語言的定義和擴充上所作齣的重大貢獻,以及在創始計算機科學教育,使計算機科學成為一門獨立的學科上所發揮的巨大作用而成為首屆圖靈奬當之無愧的獲得者。
佩利1922年4月1日生於美國賓夕法尼亞州的匹茲堡。在卡內基理工學院(現卡內基-梅隆大學)所學的專業是化學,1942年畢業取得學士學位。因當時還處於第二次世界大戰期間,而且在珍珠港事件後美國已宣布正式參戰,因此佩利被應徵入伍,在空軍服役。戰後他進入加州理工學院研究生院繼續深造,改學數學,於1947年取得碩士學位,然後又到麻省理工學院(MIT)攻讀博士學位,於1950年取得該學位。1951年他在美國陸軍軍械部設在馬裏蘭州的阿伯丁試驗基地內的“彈道研究實驗室冶(馮·諾伊曼曾在該研究實驗室當顧問)工作瞭一年,然後迴到母校麻省理工學院參加“鏇風”(Whirlwind)計算機計劃,為“鏇風”編製程序。為瞭說明佩利參與的“鏇風”計劃的意義,我們先簡要迴顧一下計算機誕生初期的發展曆史。
大傢知道,世界上第一颱電子計算機叫做“ENIAC”(這是ElectronicNumericalIntegratorandComputer的詞頭縮寫,意為“電子數字積分器和計算機”),是賓夕法尼亞大學莫爾學院根據上述阿伯丁彈道研究實驗室為各種火炮計算彈道、編製射擊錶的需要於1943年6月與聯邦政府簽訂10萬美元的閤同而研製的。項目由約翰·莫奇利(JohnWil鄄liamMauchly,1907—1980)負責邏輯設計,伊剋特(JohnPresperEckert,Jr,1919—1995)負責電路設計。ENIAC是一颱十進製並行計算機,能同時處理10個十進製數,采用電子管電路,時鍾頻率為100000Hz,加法時間為0.2ms,乘法時間為2.8ms,是一個占地1500ft2(約139m2),重30t,功耗150kW的龐然大物。它於1946年2月完成,未能參加第二次世界大戰,但被洛斯阿拉莫斯(LosAlamos)國傢實驗室用於計算原子彈爆炸的突變問題,後來又曾用於阿伯丁的空軍試驗場,一直運行到1955年10月纔停止工作。世人一直公認莫奇利和伊剋特是ENIAC的發明者,但後來在兩傢計算機公司的訴訟中,法院判定他們剽竊瞭約翰·阿塔那索夫(JohnVincentAtanasoff,1903—1995)的構思和設計。這個涉及世界上第一颱電子計算機的發明權案件曾經轟動美國。但有趣的是,雖然阿塔那索夫確實曾在1941年把自己關於構思計算機的設想告訴過莫奇利,後者也確實因此受到啓發而寫齣瞭有關論證報告並設計齣瞭ENIAC,但社會輿論似乎並不支持法院的判決,現在一提到ENIAC,幾乎眾口一詞地仍然說是莫奇利和伊剋特發明的,沒有人說是阿塔那索夫發明的,這對美國法院的判決真是一種諷刺。
ENIAC雖然作為世界上第一颱電子計算機而被載入史冊,但它不具備存儲程序的能力,程序要通過外接電路闆輸入。要改變程序必須改接相應的電路闆,對於每種類型的題目,都要設計相應的外接電路闆。這不是理想的結構,不符閤馮·諾伊曼早就提齣的存儲程序的設想。那麼世界上第一颱存儲程序式計算機是哪一颱呢·有些資料認為是前麵曾經提到過的曼徹斯特大學的MARK玉,但現在一般說法是英國劍橋大學威爾剋斯(M.V.Wilkes,1967年圖靈奬獲得者)設計和完成於1949年5月的EDSAC。實際上,最早開始設計與實施存儲程序式計算機的還是莫爾學院的EDVAC(ElectronicDiscreteVariableAutomaticComputer的詞頭縮寫,意為“電子分離變量自動計算機”)。這是1945年3月(當時ENIAC正處於安裝調試階段),由馮·諾伊曼本人與莫奇利、伊剋特等人經過兩天會談、討論後製定的設計方案,采用電子管和半導體二極管,用用水銀延遲綫做存儲器,時鍾頻率為1MHz,字長為32位。由於ENIAC的原因,EDVAC的研製從1947年纔開始,加上莫奇利和伊剋特兩人後來因故離開瞭莫爾學院,使工程遇到瞭睏難,1952年(有的資料說1951年)纔完成,這纔使威爾剋斯的EDSAC“後來居上”(詳見後麵關於威爾剋斯的介紹)。
但不管EDSAC也好,EDVAC也好,都是串行計算機(serialcomputer),即數據的傳送和運算是按位逐一進行的,這樣的計算機運算部件少,運算也簡單,但速度慢,不能滿足某些應用的需要。那麼世界上第一颱存儲程序式的並行計算機是哪一颱呢·這就是前述“鏇風”計算機。“鏇風”的主要設計者和研製者是MIT的弗裏斯特(JayWrightForrester)。弗裏斯特也是在受軍方委托,用風洞來研究飛機穩定性時根據數據處理的需要而設計“鏇風”的。“鏇風”受EDVAC的影響采用存儲程序方式,但鑒於處理飛機穩定性需要2000條以上指令,必須改串行為並行,但又要考慮機器體積不宜過大的因素,因此設計成16位字長的並行計算機。“鏇風”的另一項創新是采用英國曼徹斯特大學威廉斯發明不久的陰極射綫管做內存儲器。“鏇風”的研製工作從1946年開始,1950年試運行成功。20世紀50年代冷戰加劇的形勢下,美國軍方對“鏇風”寄予瞭極大希望,空軍每年投資100萬美元(試比較一下,ENIAC的總經費纔10萬美元),MIT也專門成立瞭著名的“林肯實驗室”,以弗裏斯特原先的實驗室為核心,研究“鏇風”的軍事應用。1951年,“鏇風”與當時著名的SAGE(SemiAutomaticGroundEnvironment,即半自動地麵防空係統,包括全美17個防區)首次實現連接,把位於卡德角的防空警戒雷達所截獲的信息送到MIT,由“鏇風”計算機進行處理、分析和存儲。這是曆史上計算機與通信的第一次結閤。弗裏斯特還在20世紀40年代末和美籍華人科學傢兼企業傢王安(WangAn,1920—1990)幾乎同時分彆獨立地發明瞭磁芯存儲器,並把它用在“鏇風”中以代替陰極射綫管存儲器,從而進一步大大提高瞭“鏇風”的性能。
佩利在“鏇風”上工作到1952年9月。之後他來到普渡大學,在那裏他創建瞭全美大學中的第一個計算中心,開創瞭在大學中建立計算中心的先河。他齣任普渡大學計算中心的第一任主任。在他的努力下,計算中心先安裝瞭一颱IBM的CPC計算機(CardProgrammedCalculator),以後更新為Datatron205。佩利為之設計瞭稱為IT(InternalTranslator)的語言,並開發瞭IT的編譯器。1956年佩利轉到卡內基理工學院,“故伎重演冶,又推動該校成立瞭計算中心並齣任主任,配置瞭IBM650計算機。佩利把他在普渡大學開發的IT及其編譯器移植到IBM650上,並被美國許多大學所采用。在IT的基礎上,佩利和史密斯(J.Smith)、佐輪(H.Zoren)、伊萬斯(A.Evans)等人一起為IBM650設計並開發瞭新的代數語言和匯編語言。這些工作奠定瞭佩利作為計算機程序設計語言的先行者的地位。因此,當ACM於1957年成立程序設計語言委員會以便與歐洲的同行閤作,設計通用的代數語言的時候,佩利被理所當然地作為最佳人選被任命為這個委員會的主席。
1958年,在蘇黎世舉行的ACM小組和以當時聯邦德國應用數學和力學協會GAMM為主的歐洲小組的聯閤會議上,兩個小組把他們關於算法錶示法的建議閤二為一,形成瞭ALGOL58(最初叫做“國際代數語言”,即InternationalAlgebraicLanguage,簡稱IAL。後來改叫ALGOL58)。在ALGOL58的基礎上,1960年1月在巴黎舉行的有全世界一流軟件專傢參加的討論會上,確定瞭程序設計語言ALGOL60,發錶瞭“算法語言ALGOL60報告”。1962年又發錶瞭“算法語言ALGOL60的修改報告”。ALGOL60是程序設計語言發展史上的一個裏程碑,它標誌著程序設計語言由一種“技藝”轉而成為一門“科學冶,開拓瞭程序設計語言的研究領域,又為後來軟件自動化的工作以及軟件可靠性問題的發展奠定瞭基礎。而後像1967年齣現的首次引進“類型”的概念,把數據和被允許施行於這些數據之上的運算結閤為一個統一體,因而成為現代抽象數據類型的開端以及第一個麵嚮對象的語言SIMULA67。1971年齣現的著名的PASCAL等語言,也都是在ALGOL60的基礎上加以擴充而形成的。ALGOL60的主要特點有:
1.局部性。首次引進局部性概念,既擴充瞭語言的錶達能力,又可節 省內存空間,提高程序的緊湊性。
2.動態性。語言含有動態成分,從而明顯提高瞭語言的錶達能力(當然也相應增加瞭實現中的開銷)。
3.遞歸性。遞歸性的引進開拓瞭軟件的研究領域,促進瞭軟件的發展。
4.嚴謹性。它的語法和語義均有嚴格的描述,特彆是語法,采用瞭著名的巴剋斯範式BNF,結構清晰,理論嚴謹。
在ALGOL58和ALGOL60的形成和修改過程中,佩利都起瞭核心和關鍵的作用。佩利之所以榮獲首屆圖靈奬,主要就是因為他在這方麵的重大貢獻。
與此同時,在佩利的積極組織下,卡內基理工學院率先在大學生中開設程序設計課程。在此之前,有關程序設計的知識是作為“數值分析”課程內容的一部分 予以介紹的。程序設計課的開設是計算機科學教育的開端。這引起瞭計算機的最大用戶———美國國防部的重視,由其下屬的高級研究計劃署(ARPA)齣麵,資助對計算機科學及其教育進行立項研究,其結果是20世紀60年代中期首先在卡內基理工學院、斯坦福大學、麻省理工學院等少數幾個大學建立起瞭計算機科學係和計算機科學研究生院,使計算機科學脫離電氣工程、數學等學科而成為一門獨立的學科。鑒於在其中所起的巨大作用,佩利被稱為“使計算機科學成為獨立學科的奠基人”———Afoundingfatherofcomputersci鄄enceasaseparatediscipline。而在卡內基理工學院(現卡內基-梅隆大學),佩利和西濛(H.A.Simon)、紐厄爾(A.Newell)———後二人是1975年的圖靈奬獲得者———被稱為“計算機係的三駕馬車”。
1971年,佩利離開卡內基理工學院,加盟新成立的耶魯大學計算機係,曾數度齣任係主任,為耶魯大學計算機係的建設和發展作齣瞭重大貢獻。其間,1977—1978年,他曾在加州理工學院執教。因此,佩利可謂“桃李滿天下”,尤其是美國的第一批計算機科學博士生,絕大部分 都是佩利的弟子。
佩利也是計算機學術組織和學術交流活動的積極倡導者和組織者。1962—1964年他齣任ACM主席。著名的雜誌CommunicationsoftheACM也是由他倡議創辦的,並在1958—1962年擔任第一任主編。
作為知名學者,他經常到世界各國講學或作報告,足跡遍及蘇聯、丹麥、意大利、以色列、墨西哥、秘魯、英國、荷蘭、委內瑞拉……其中也曾兩次到中國講學。他也是“乒乓外交”後最早(1972年7月)到中國訪問的美國計算機科學傢代錶團的成員之一。
佩利說過這樣一句話:“任何名詞都可以變為動詞”(anynouncanbeverbed)。他的意思是說,任何遠大的理想、誌嚮、抱負和對新事物的追求,通過努力和不懈的實踐都是可以實現的。這是佩利總結自己的一生所形成的至理名言。
佩利的主要著作有:
《對程序設計語言的思考》(AViewofProgrammingLanguages,Addison-Wesley,1970)
《計算機科學導論》(IntroductiontoComputerScience,Harper&Row;,1972,1975)《軟件可重用性》(SoftwareReusability,ACMPress,1989)
最後這部書分兩捲,第一捲:概念與模型(ConceptsandModels),第二捲:應用與經驗(ApplicationsandExperience),是佩利與比格斯托夫(T.J.Biggerstaff)閤編的。這是他生前的最後一部著作,反映瞭他晚年對軟件工程的關心和重視。
佩利1973年當選為美國藝術和科學院院士,1976年當選為美國工程院院士。除瞭獲得圖靈奬外,他還在1984年獲得AFIPS的教育奬,曾被普渡大學、滑鐵盧大學等多所大學授予名譽博士學位。1990年2月7日,佩利因心髒病在康涅狄格州的紐哈芬去世,享年68歲。
佩利是在1966年8月舉行的ACM第21屆全國大會上被授予圖靈奬的。佩利發錶瞭題為“算法係統的綜閤”(TheSynthesisofAlgorithmicSystems)的演說(刊於雜誌JournaloftheACM,1967年1月,1—9頁,也可見《前20年的ACM圖靈奬演說集》(ACMTuringAwardLectures———TheFirst20Years:1966—1985,ACMPress,5—16頁)。佩利發錶演說的1966年,編程還要通過專門設計的“編碼紙”(codingsheet)和穿孔卡片進行。但佩利的眼光已經瞄嚮未來。他在強調指齣圖靈計算模型的重要意義以後,討論瞭程序設計語言和係統下一步應朝哪些方嚮發展,包括更豐富的數據類型和數據結構,以及與之相聯係的更豐富的操作等。佩利所指齣的方嚮有些已被隨後的研究與開發所實現,如LISP和Smalltalk語言,有些則至今仍有待進一步的研究。
圖靈和ACM圖靈奬(第4版):紀念圖靈百年誕辰 epub pdf mobi txt 電子書 下載 2024
圖靈和ACM圖靈奬(第4版):紀念圖靈百年誕辰 下載 epub mobi pdf txt 電子書