沃爾克·施特拉森

德国数学家

沃爾克·施特拉森(德語:Volker Strassen,1936年4月29日)是一名德國數學家康斯坦茨大學數學和統計系的名譽教授[1]

沃爾克·施特拉森
Volker Strassen
沃爾克·施特拉森在2009年SODA上發表高德納獎演講
出生 (1936-04-29) 1936年4月29日88歲)
 納粹德國杜塞道夫
國籍 德國
母校哥廷根大學
知名於施特拉森演算法
頌哈吉-施特拉森演算法
索洛維-施特拉森質數測試英語Solovay–Strassen primality test
獎項康托爾獎章(1999年)
帕里斯·卡內拉基斯獎英語Paris Kanellakis Award(2003年)
高德納獎(2008年)
康拉德·楚澤獎章英語Konrad Zuse Medal(2011年)
科學生涯
研究領域數學
機構康斯坦茨大學
博士導師康拉德·雅各(Konrad Jacobs)
博士生彼得·柏吉瑟英語Peter Bürgisser
約阿希姆·馮·祖爾·加滕英語Joachim von zur Gathen

施特拉森因對算法分析的重要貢獻而獲得許多獎項,包括康托爾獎章[2]康拉德·楚澤獎章英語Konrad Zuse Medal[3]、因隨機質數測試英語Solovay–Strassen primality test工作而獲得的帕里斯·卡內拉基斯獎英語Paris Kanellakis Award[4],以及因「對高效算法的設計與分析有開創性和影響力貢獻」的高德納獎[5]

生平

 
1979年的施特拉森

施特拉森在1936年4月29日出生於杜塞道夫[2]。在德國多所大學學習音樂、哲學、物理學和數學後[2],他在1962年於哥廷根大學獲得數學博士學位,導師為康拉德·雅各(Konrad Jacobs)[6]。隨後,他在加利福尼亞大學柏克萊分校統計所任職,同時在愛爾朗根-紐倫堡大學進行特許任教資格訓練[2]。1968年,施特拉森搬到蘇黎世大學的應用數學研究所任教,1988年搬到康斯坦茨大學任教[2]。他於1998年退休[4]

研究

施特拉森作為機率論者開始了他的研究;他在1964年的論文《重對數律的不變性原則》中定義重對數律的函數形式,顯示出隨機漫步中的一種尺度不變性英語Scale invariance。這個結果現在被稱為「施特拉森不變性原則」或「施特拉森重對數律」,被高度引用,並導致1966年在國際數學家大會的演講。

1969年,施特拉森將研究工作轉向算法分析,發表了一篇關於高斯消去法的論文,並介紹施特拉森演算法,為第一個執行矩陣乘法的演算法,其速度比樸素算法所產生的 時間約束要快。在同一篇論文中,他還提出一種基於快速矩陣乘法算法的漸進式快速算法來進行矩陣求逆。此結果是一個重要的理論突破,導致對快速矩陣乘法的更多研究,儘管後來在理論上有所改進,但它仍是中度到高度密集矩陣乘法的實用方法。1971年,施特拉森與阿諾德·頌哈吉英語Arnold Schönhage一起發表另一篇關於基於快速傅立葉轉換漸進快速整數乘法的論文;參見頌哈吉-施特拉森演算法。施特拉森還因1977年與羅伯特·M·索洛維英語Robert M. Solovay合作研究索洛維-施特拉森質數測試英語Solovay–Strassen primality test而知名,這是第一個表明檢驗一個數字是否為質數的方法可以在在隨機多項式時間內進行,也是更普遍地表明隨機算法力量的第一批結果之一。

獲獎和榮譽

施特拉森在1999年被授予康托爾獎章[2],2003年與羅伯特·索洛維英語Robert M. Solovay加里·米勒英語Gary Miller (computer scientist)麥可·拉賓共同獲得帕里斯·卡內拉基斯獎英語Paris Kanellakis Award,以表彰在隨機質數測試方面的工作[4]。2008年,他因「對高效算法的設計與分析有開創性和影響力貢獻」而被授予高德納獎[5]。2011年,他贏得德國資訊學會英語German Informatics Society康拉德·楚澤獎章英語Konrad Zuse Medal[3][7]。2012年,他成為美國數學學會的會士[8]

參考資料

  1. ^ FB Mathematik and Statistik 網際網路檔案館存檔,存檔日期2008-12-25., U. Konstanz.
  2. ^ 2.0 2.1 2.2 2.3 2.4 2.5 Schönhage, A., Cantor-Medaille für Volker Strassen (PDF), Jahresbericht der Deutschen Mathematiker-Vereinigung, 2000, 102 (4) [2022-05-23], (原始內容 (PDF)存檔於2011-09-28) .
  3. ^ 3.0 3.1 Winter, Cornelia, Konrad-Zuse-Medaille für Informatik an Fritz-Rudolf Güntsch und Volker Strassen, Informationsdienst Wissenschaft, September 28, 2011 [2022-05-23], (原始內容存檔於2014-06-06) (德語) 
  4. ^ 4.0 4.1 4.2 Preis für Prof. Volker Strassen, uni'kon 16.2004[失效連結], Univ. of Konstanz.
  5. ^ 5.0 5.1 The 2008 Knuth Prize is awarded to Volker Strassen for his seminal and influential contributions to efficient algorithms頁面存檔備份,存於網際網路檔案館), ACM SIGACT.
  6. ^ 沃爾克·施特拉森數學譜系計畫的資料。
  7. ^ Konrad-Zuse-Medaille 網際網路檔案館存檔,存檔日期2014-08-19., Gesellschaft für Informatik (in German), retrieved 2012-03-09.
  8. ^ List of Fellows of the American Mathematical Society頁面存檔備份,存於網際網路檔案館), retrieved 2013-08-05.

外部連結