2000年圖靈獎獲得者姚期智教授主持論壇
姚期智——唯一獲得圖靈獎的華裔中國人！
美國計算機學會(ACM)把2000年度的圖靈獎授予華裔計算機科學家、現(xiàn)普林斯頓大學教授姚期智。這是有“計算機世界的諾貝爾獎”之稱的圖靈獎35年來首次授予一位華裔學者，是值得全世界華人為之驕傲的。
姚期智(YaoChi-chih)的英文名字是安德魯·姚(AndrewC.Yao)。他祖藉湖北孝感，1946年12月24日出生于上海，幼年隨父母去臺灣省。1967年在臺灣大學畢業(yè)以后，去美國深造，原先所學專業(yè)是物理。但20世紀60年代以來計算機技術的迅猛發(fā)展和計算機在各行各業(yè)的廣泛應用吸引了他的目光，他敏銳地意識到這是一個十分重要并具有巨大發(fā)展空間的新興學科，從而決心放棄原先專業(yè)而轉到計算機科學上來。因此，在1972年取得令人羨慕的哈佛大學物理學博士學位以后，他出人意料地又來到伊利諾大學研究生院繼續(xù)學習。伊利諾大學在計算機科學技術方面當時處于美國領先地位。姚期智于1975年在伊利諾大學取得他的第二個博士學位——計算機科學博士學位。之后，他曾先后在麻省理工學院(1975～1976)、斯坦福大學(1976～1981，1983～1986)、加州大學伯克利分校(1981～1983)等美國著名高等學府從事教學與研究，1986年加盟普林斯頓大學至今。
姚期智對計算機科學技術所作出的貢獻主要在計算理論方面。ACM在授獎決定中指出，姚期智對計算理論的眾多貢獻是根本性的、意義重大的，其中包括基于復雜性的偽隨機數生成理論、密碼學和通信復雜性。最近1/4個世紀中姚期智發(fā)表的近百篇學術論文，幾乎覆蓋了計算復雜性的所有方面。姚期智進入計算機科學領域最早的論文之一《尋找最小生成樹的O(|E|loglog|V|)算法》一文就引起轟動，因為學術界原先認為，尋找最小生成樹算法的時間復雜度的下界是O(ElogV)，而姚期智的論文證明這個極限是可以打破的。在姚的這一開創(chuàng)性工作的基礎上，經過近20年的努力，人們終于設計出了尋找最小生成樹的線性時間算法。
在數據組織方面，人們歷來以為排序表(Sorted Table)是一種良好的結構，在其中檢索信息有最快的響應。姚期智經過深入研究，發(fā)現(xiàn)這只在少數特定條件下才成立，而對于允許有任意信息編碼的表而言，在排序表中檢索信息的效率遠不是最佳的。他的研究結果在《表應該被排序嗎?》一文中發(fā)表以后，人們對信息應如何有效地存儲在認識上發(fā)生了革命性的變化。該文為后來出現(xiàn)最佳概率化哈希模式和字典實現(xiàn)方式奠定了基礎。姚在該文中所采用的證明方法則被稱為“Cell Probe”模型而被廣泛應用，在數據結構和算法的分析與設計的研究中產生了深遠的影響。
姚期智對偽隨機數生成理論的諸多貢獻集中反映在他1982年的論文《活板門函數的理論和應用》中。在這篇有開創(chuàng)性意義的論文中，姚期智先證明了著名的BlumMicali發(fā)生器所產生的隨機數實際上是偽隨機的，并由此導出了在隨機數生成技術中一個十分重要的概念，即“隨機性和難度”的折衷。論文還首次定義了“計算熵”(Computational Entropy)的概念，對它進行了深入研究，引出了一系列有關定理和推論，推動了密碼學的發(fā)展。而姚期智自己則在1986年的論文《如何產生和交換秘密信息》中進一步提出了一種稱為“健忘的電路模擬”的密碼技術，利用這種技術能秘密而可靠地計算出任意函數。
隨著Internet的普及和互聯(lián)網的飛速發(fā)展，對通信復雜性的研究成為姚關注的一個重點。他在這方面發(fā)表的論文如《電路和通信復雜性的近期進展》被認為是經典之作，經常被其他論文引用。姚期智為通信建立了基本模型，提出了分析方法，從而使通信復雜性發(fā)展成為一個重要的研究領域，并獲得了多方面的和意想不到的應用。
姚期智近期的研究集中于量子通信和計算。量子計算是以量子力學理論和量子器件為基礎、新近發(fā)展起來的一種新的計算技術，它不但能降低傳統(tǒng)計算技術的計算復雜性，還能解決一些傳統(tǒng)計算機根本無法處理的問題。姚期智在DARPA/ITO的資助下，已經在這方面的研究中取得若干成果，發(fā)表了一些引人注目的論文，如《Quantum Bit Escrow》、《Quantum Cryptography with Imperfect Apparatus》、《Security of Quantum Protocol against Coherent Measurements》等。
在此次榮獲圖靈獎之前，姚期智在1996年獲得以算法設計大師克努特(Donald Ervin Knuth,1994年圖靈獎獲得者)命名的首屆克努特獎。去年4月，姚期智被選為美國藝術和科學院教學部院士，他也是我國《軟件學報》(英文版)的副主編，曾到祖國內地參加學術活動。
姚期智的夫人弗朗西絲·姚(Frances F.Yao)也是來自中國臺灣省的華裔科學家，他們是志趣相投的一對伉儷，曾聯(lián)名發(fā)表許多研究論文。
姚期智，祖藉湖北孝感，1946年12月24日出生于上海，幼年隨父母移居臺灣。
1967年，姚期智畢業(yè)于臺灣大學獲物理學士學位，之后赴美國深造。1972年獲哈佛大學物理學博士學位，1975年獲伊利諾大學香檳分校計算機科學博士學位。1975年至1986年曾先后在美國麻省理工學院數學系、斯坦福大學計算機系、加利福尼亞大學伯克利分校計算機系任助教授、教授。1986年至2004年在普林斯頓大學計算機科學系擔任Wiliam and Edna Macaleer工程與應用科學教授。2004年起在清華大學任全職教授。
更多精彩請點擊：新聞排行榜
關于中華網 |
廣告服務 |
聯(lián)系我們 |
招聘信息 |
版權聲明 |
豁免條款 |
友情鏈接 |
中華網動態(tài)
