算法設(shè)計與分析：Turing獎介紹

圖靈獎（Turing）簡介世界上第一臺電子計算機ENIAC于1946年2月誕生在美國賓夕法尼亞大學(xué)莫爾學(xué)院。但學(xué)術(shù)界公認(rèn)，電子計算機的理論和模型是由英國數(shù)學(xué)家圖靈(AlanMathisonTuring，1912-1954)在1936年發(fā)表的一篇論文“論可計算數(shù)及其在判定問題中的應(yīng)用”中奠定了基礎(chǔ)的。因此，當(dāng)美國計算機協(xié)會ACM在1966年紀(jì)念電子計算機誕生20周年，也就是圖靈的有歷史意義的論文發(fā)表30周年的時候，決定設(shè)立計算機界的第一個獎項，并且很自然地把它命名為“圖靈獎”以紀(jì)念這位計算機科學(xué)理論的奠基人。

圖靈獎是計算機界最負盛名的獎項,有“計算機界諾貝爾獎”之稱。圖靈獎對獲獎?wù)叩囊髽O高,評獎程序也極嚴(yán),一般每年只獎勵一名計算機科學(xué)家,只有極少數(shù)年度有兩名以上在同一方向上做出貢獻的科學(xué)家同時獲獎.目前圖靈獎由英特爾公司贊助,獎金為100,000美元。每年，美國計算機協(xié)會（ACM）將要求提名人推薦本年度的圖靈獎候選人，并附加一份200到500字的文章，說明被提名者為什么應(yīng)獲此獎。評選委員會對被提名者進行嚴(yán)格的評審，并最終確定當(dāng)年的獲獎?wù)摺lanTuring生平簡介1912年6月23日，出生于英國倫敦。1931-1934年，在英國劍橋大學(xué)國王學(xué)院學(xué)習(xí)。1932-1935年，研究量子力學(xué)、概率論和邏輯學(xué)。1935年，由于獨立發(fā)現(xiàn)中心極限定理，獲Smith獎，年僅23歲被選為劍橋大學(xué)國王學(xué)院院士。1936年，研究可計算理論，提出“圖靈機”的構(gòu)想。1936-1938年，在美國普林斯頓大學(xué)做博士研究，涉及邏輯學(xué)、代數(shù)和數(shù)論等領(lǐng)域。1938-1939年，返回劍橋從事研究工作，并應(yīng)邀加入英國政府破譯二戰(zhàn)德軍密碼的工作。1940-1942年，作為主要參與者和貢獻者之一，成功破譯德軍U-潛艇密碼。AlanTuring生平簡介1943-1945年，擔(dān)任英美密碼破譯部門的總顧問。1945年，應(yīng)邀在英國國家物理實驗室從事計算機理論研究工作。1946年，被英國皇室授予OBE爵士勛銜。1947-1948年，從事計算機程序理論的研究，并同時在神經(jīng)網(wǎng)絡(luò)和人工智能領(lǐng)域作出開創(chuàng)性的理論研究。1948年，應(yīng)邀加入英國曼徹斯特大學(xué)從事研究工作，擔(dān)任曼徹斯特大學(xué)計算實驗室副主任。1949年，把計算機實際用于數(shù)學(xué)研究。1950年，發(fā)表論文“計算機器與智能”，為人工智能科學(xué)提供開創(chuàng)性的構(gòu)思。提出著名的“圖靈測試”理論。AlanTuring生平簡介1951年，提出生物增長的非線性理論研究。年僅39歲被選為英國皇家學(xué)會會員。1952年，有同性戀傾向的圖靈被捕入獄。法庭審判過程中，圖靈明確告知人們自己并沒有做錯什么事，然而為了避免被判刑入獄，圖靈被迫選擇了為期一年的雌性激素注射的所謂“治療”，才得以重返研究工作。1953-1954年，繼續(xù)在生物和物理學(xué)等方面的研究。被迫承受對同性戀傾向的“治療”，致使原本熱愛體育運動的圖靈在身心上受到極大的傷害。1954年6月7日，42歲的圖靈死于家中的床上，床頭有一個咬了一半的，在氰化物溶液中浸泡過的蘋果，警方調(diào)查結(jié)論是自殺。圖靈終生未娶。AlanTuring的主要貢獻24歲提出圖靈機理論31歲參與Colossus的研制（二戰(zhàn)時英國破解德國通訊密碼的計算機，核心成員）33歲時構(gòu)思了仿真系統(tǒng)35歲提出了自動程序設(shè)計的概念38歲設(shè)計了“圖靈測試”39歲提出了關(guān)于生物增長的非線性理論有“計算機之父”、“人工智能之父”、“破譯之父”等美譽。有人甚至認(rèn)為，他的貢獻及對未來世界的影響幾乎可與牛頓、愛因斯坦等人比肩。圖靈相信如果模擬人類大腦的思維就可以做出一臺可以思考的機器，它于1950寫文章提出了著名的“圖靈測試”，測試是讓人類考官通過鍵盤向一個人和一個機器發(fā)問，這個考官不知道他現(xiàn)在問的是人還是機器。如果在經(jīng)過一定時間的提問以后，這位人類考官不能確定誰是人誰是機器，那這個機器就有智力了。

算法在CS中占有重要地位的一個體現(xiàn)

——有超過1/3的Turing獎獲獎?wù)咂涑晒c算法有關(guān)。首位亞裔圖靈獎得主 2000年 AndrewChi-ChihYao(姚期智)

——(授予姚期智圖靈獎以表彰其在)計算理論領(lǐng)域的基礎(chǔ)性的卓越貢獻,其中包括產(chǎn)生偽隨機數(shù)的復(fù)雜性理論,密碼系統(tǒng)和通訊復(fù)雜性等.于1987年獲得美國工業(yè)與應(yīng)用數(shù)學(xué)學(xué)會GeorgePolya獎,1996年獲得美國計算機學(xué)會算法與計算理論分會(ACMSIGACT)DonaldE.Knuth獎.于1998年當(dāng)選為美國科學(xué)院院士,于2000年當(dāng)選為美國科學(xué)與藝術(shù)學(xué)院院士,并于2004年當(dāng)選為中國科學(xué)院外籍院士。1946年12月24日生于上海,美國國籍.于1967年獲得臺灣大學(xué)物理學(xué)士學(xué)位,1972年獲得美國哈佛大學(xué)物理博士學(xué)位,1975年獲得美國伊利諾依大學(xué)計算機科學(xué)博士學(xué)位.曾先后在美國麻省理工學(xué)院數(shù)學(xué)系,斯坦福大學(xué)計算機系,加利福尼亞大學(xué)伯克利分校計算機系、普林斯頓大學(xué)計算機科學(xué)系任助理教授,教授.

現(xiàn)任清華大學(xué)高等研究中心

(TheCenterforAdvancedStudyinTsinghuaUniversity)教授.姚期智之妻儲楓（FrancisYao），自2004年起在香港城市大學(xué)電腦科學(xué)系擔(dān)任系主任。首位女性圖靈獎得主

2006年 FrancesE.Allen(弗朗西斯·

艾倫)

——在編譯器優(yōu)化技術(shù)理論和實踐做出的先驅(qū)性貢獻，這些理論和實踐是現(xiàn)代優(yōu)化編譯和自動并行執(zhí)行的基礎(chǔ)。Frances1957年加盟IBMWatson研究中心.是IBM歷史上第一位女院士,深刻影響計算機工業(yè)界。RSA算法的發(fā)明者

2002年 RonaldL.

Rivest

(隆·

里維斯特),

AdiShamir(阿迪·

沙米爾)和

LeonardM.

Adleman

(雷奧納德·

阿德爾曼)

——使得公鑰密碼技術(shù)在實際中可用的創(chuàng)造性貢獻Shamir&Rivest&Adleman

有關(guān)AlanTuring的一些軼事兩次報考劍橋三圣學(xué)院（TrinityCollege，最負盛名）未被錄取，只好進了劍橋國王學(xué)院（King’sCollege）攻讀數(shù)學(xué)。不善言辭，有些木訥害羞，常咬指甲。在劍