當前位置 主頁 > 站長資源大全 > iis7百科 > 最大化 縮小

    理查德·斯特恩斯——計算復雜性理論的創始人

    欄目:iis7百科 時間:2019-11-19 09:59

      理查德·斯特恩斯(Richard Stearns)(綽號“迪克”)于1936年7月5日在新澤西州考德威爾市,是埃德溫·斯特恩斯博士和斯里蘭卡的Winifred Serge Son的兒子。他和夏洛特·里德(Charlotte Reid)于1963年結婚。他們有兩個成年子女,克里斯·斯特恩斯(Chris Stearns)和伊麗莎白·岡薩斯(Elizabeth Gonzers)。
      Stearns于1958年從Carleton大學獲得數學學士學位。1961年,他獲得了博士學位。在普林斯頓大學獲得數學博士學位。它的論文《沒有偏袒懲罰的三人合作游戲是在哈羅德·庫恩的監督和羅伯特·歐邁安的指導下完成的。
      1960年夏天斯特恩斯在位于紐約州東部的斯克內克塔迪的通用電氣研究實驗室,在那里他和尤里斯·哈特馬尼斯開始一起研究狀態指定問題。在1961年獲得博士學位后,斯特恩斯加入哈特馬尼斯成為通用電氣研究實驗室的信息學習分支的一名正式員工,受理查德·休伊管理。在研究實驗室的氣氛和環境鼓勵了他們所熱愛的自由的、不受約束的研究方式。
      斯特恩斯和哈特馬尼斯一開始在進行線性機器的分解方面的工作:簡單電腦的模型如何能被分解成一些更小的線性機器的結合,且能完成相同的任務。關于這個主題他們發表了一些論文,并在1966年將他們的工作總結寫入了一本書。后來他們開始研究計算復雜性,并在1965年發表了那篇讓他們獲得圖靈獎的論文。
      在哈特馬尼斯離開通用電氣而成為了康奈爾大學計算機科學系的系主任后,斯特恩斯開始和丹尼爾·盧森爾茲及菲利普·萊維斯一同工作。這個合作的一部分繼續了在計算復雜性方面的研究。
      復雜的的類層次結構所闡釋的其中一點是有很多生活中的實際問題是非常復雜的以至于解決它們是不現實的。關于近似計算復雜度問題的研究表明求解有些問題的精確解會耗時非常長的時間而得到一個可以被證明與最優解很接近的近似可以被一個使用短得多的時間的算法解決。
      盧森爾茲、萊維斯和斯特恩斯發表了一系列論文,并在1976年出版了一本關于編譯器設計原理的書。一個編譯器是將用高級語言寫的程序翻譯成指定平臺機器碼的程序。一個編譯器設計問題是如何對某個程序語言的程序進行語法分析的問題。對于自然語言,對一個句子進行詞法分析包括找到主語、謂語和賓語等等。程序語言通常使用上下文無關文法表達,而且使用這種文法寫的程序必須能通過編譯器的語法分析。使用上下文無關文法對一個“句子”(程序)進行語法分析的計算復雜度是n^3,這對于一個編譯器來說代價太高了,不現實。這三位作者定義了一類特殊的上下文無關文法,LL(k)文法,它可以在線性時間內進行語法分析,也就是說復雜度只有n。他們用來描述對LL(k)文法進行語法分析的方法叫做自頂向下的語法分析而且現在已經是編譯器設計的一個重要部分。他們還指出從程序語言到機器語言的大部分翻譯工作可以在語法分析的同時完成。
      在1978年斯特恩斯離開通用電氣而去位于奧爾巴尼的紐約州立大學之后(盧森爾茲已在1977年離開去了奧爾巴尼),他繼續和萊維斯一起工作。他們做了關于并發數據庫系統的研究,在這種數據庫中會有一些事務在同一個數據庫中進行讀和寫操作。這種系統的目標之一是讓事務盡可能并發地執行以增加系統的輸出,但同時不會破壞數據庫的正確性。他們寫的關于這個主題的論文指出并發執行的一致性和正確性的充分必要條件是事務的可串行性——它指的是,所有并發運行事務的讀寫操作的影響必須和他們在某種順序下串行運行(一個接一個)一樣。在這之前已經知道可串行性是一致性的充分條件:如果執行時可串行的,結果就是對的。這篇論文指出除去一些特定的只有讀操作的事務的情況,這也是一個必要條件:執行必須要可串行化才能保證正確。這個結論現在已經是所有數據庫課程和數據庫系統設計的核心部分。
      在紐約州立大學,斯特恩斯開始和哈利·亨特三世進行長期合作。要證明所感興趣的問題是很難的,通常需要將其“歸約”(即映射)到那些已知很難的問題(假設P≠NP)。亨特和斯特恩斯研究了和歸約相關的更深入的問題。他們試圖尋找那些能將問題映射到具體情況的簡單子集上的歸約,因為實際感興趣的具體情況可能都是很簡單的。他們還試圖尋找針對小規模問題的歸約,因為規模越小,可以得到的關于復雜性的結論就越強。他們用冪指數法的概念對這些思想進行了形式化描述。除了一個一個地尋找歸約,他們還嘗試尋找了能被應用到多種對象的歸約原理,特別是針對多種代數結構。通過這樣,他們用同一個簡單的理由說明了許多問題是很難的。
      亨特和斯特恩斯還研究了和積問題,其中加法運算符和乘法運算符是來自可交換的半環。他們指出如果一個問題有像結構樹所展示的那種好結構,那么這樣的問題是可以用更少的運算符解決的。這里的“好結構”指的是用于自頂向下處理的小“有權深度”或自頂向上處理的“管道寬度。如果形象地來看和積問題,管道寬度是樹寬的一種表現形式,但是如果用代數角度來看這個問題,用結構樹就很清楚。然后,利用代數條件中的加法,他們擴展了結構樹的概念以適應定量公式。他們還完成了次線性空間和受次線性樹寬約束的或與問題的一個緊連接。
      與拉維、哈利·亨特三世、丹尼爾· 盧森爾茲和馬達夫·馬拉地合作,斯特恩斯還有在動態系統方面的工作。
      2000年9月,斯特恩斯退休并和他的夫人住在斯林格蘭。他仍然會拜訪并和大學以前的同事合作。
777亚洲人成视频免费视频