迈克尔·拉宾

维基百科，自由的百科全书
跳转至： 导航、 搜索
迈克尔·拉宾
Michael Oser Rabin

出生 1931年9月1日 (1931-09-01)（81歲）
德国魏瑪共和國布雷斯劳（今波兰弗罗茨瓦夫）
研究領域 计算机科学
任职於 哈佛大学
希伯来大学
哥伦比亚大学
著名成就 米勒-拉宾素数检验
拉宾密码系统
不经意传输（Oblivious transfer）
拉宾-卡普字符串搜索算法 （Rabin-Karp string search algorithm）
非确定有限状态自动机
獲獎 图灵奖

迈克尔·O·拉宾（Michael Oser Rabin希伯来语：מִיכָאֵל אֹשֶׁר רַבִּין‎，1931年9月1日－ ）是一名以色列计算机科学家，1976年图灵奖得主。

简介[编辑]

拉宾出生于德国布雷斯劳（二战后成为波兰弗羅茨瓦夫），父亲是一个拉比。

1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。

1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（Finite Automata and Their Decision Problems）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（Complexity of Computations）的演讲。图灵奖的引文是：

“
因他们的合著论文“有限自动机与其判定性问题”。论文中引入了非确定自动机的概念，被证明是（计算理论科学研究中的）一个非常重要的概念。拉宾和斯科特的这篇经典论文成为了这个领域后续研究的源泉。[1]
”

非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。

1969年，拉宾证明N successors的二阶逻辑是可判定的。[2]证明的关键部分暗示了parity game的确定性。1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机算法（有较小的可能性错误），用于判断一个大数是否是素数。[3][4] 快速素数检验是目前大部分公钥密码体系的关键。1979年，拉宾发明了第一个非对称密码系统——拉宾密码系统。它的安全性被证明和整数因式分解的复杂度相同。[5]1981年，拉宾提出了不经意传输（oblivious transfer）技术。[6] 1987年，拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。[7]

参考[编辑]

  1. ^ 英文为：For their joint paper "Finite Automata and Their Decision Problem," which introduced the idea of nondeterministic machines, which has proved to be an enormously valuable concept. Their (Scott & Rabin) classic paper has been a continuous source of inspiration for subsequent work in this field. ACM Turing Award Citation
  2. ^ Rabin, MO. Decidability of second order theories and automata on infinite trees. Trans. AMS. 1969, 141: 1–35. doi:10.2307/1995086. 
  3. ^ Rabin, MO. Probabilistic algorithms. Algorithms and Complexity, Proc. Symp. Pittsburgh. 1976. 
  4. ^ Rabin, MO. Probabilistic algorithm for testing primality. Journal of Number Theory. 1980, 12 (1): 128–138. doi:10.1016/0022-314X(80)90084-0. 
  5. ^ Rabin, MO. Digital signatures and public-key functions as intractable as factorization. {MIT Laboratory of Computer Science Technical Report. January 1979 [2007-03-15]. 
  6. ^ Rabin, Michael O., How to exchange secrets by oblivious transfer (Technical Report TR-81) (PDF), Aiken Computation Laboratory: Harvard University. 1981 
  7. ^ Karp, RM; Rabin, MO. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development. 1987.March, 31 (2): 249–260 [2007-03-15]. 

外部链接[编辑]
佩利（1966） · 威尔克斯（1967） · 漢明（1968） · 閔斯基（1969） · 维尔金森（1970） · 麦卡锡（1971） · 戴克斯特拉（1972） · 巴赫曼（1973） · 高德納（1974） · 纽厄尔、西蒙（1975） · 拉宾、斯科特（1976） · 巴科斯（1977） · 弗洛伊德（1978） · 艾佛森（1979） · 霍爾（1980） · 科德（1981） · 古克（1982） · 湯普遜、里奇（1983） · 维尔特（1984） · 卡普（1985） · 霍普克罗夫特、塔扬（1986） · 科克（1987） · 苏泽兰（1988） · 卡亨（1989） · 考巴托（1990） · 米尔纳（1991） · 兰普森（1992） · 哈特马尼斯、斯特恩斯（1993） · 费根鲍姆、瑞迪（1994） · 布卢姆（1995） · 伯努利（1996） · 恩格尔巴特（1997） · 格雷（1998） · 布鲁克斯（1999） · 姚期智（2000） · 达尔、奈加特（2001） · 李维斯特、萨莫尔、阿德曼（2002） · 凯（2003） · 瑟夫、卡恩（2004） · 诺尔（2005） · 艾伦（2006） · 克拉克、爱默生、斯发基斯（2007） · 利斯科夫（2008） · 萨克尔（2009） · 瓦利安特（2010） · 珀尔（2011） · 莎菲·歌德瓦爾賽 (2012) · 希爾維奧·米卡利 (2012)
来自“http://zh.wikipedia.org/w/index.php?title=迈克尔·拉宾&oldid=25513128”