迈克尔·拉宾 (科学家)

✍ dations ◷ 2025-12-04 00:31:21 #1931年出生,在世人物,图灵奖获得者,计算机科学家,以色列科学家,犹太科学家,普林斯顿大学校友,耶路撒冷希伯来大学校友,耶路撒冷希伯来大学教师,以色列犹太人,

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

拉宾出生于德国布雷斯劳(二战后成为波兰弗罗茨瓦夫),父亲是一个拉比。

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

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

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

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

1969年,拉宾证明N successors的二阶逻辑是可判定的。证明的关键部分暗示了奇偶游戏(英语:Parity game)的确定性。1975年,拉宾发明了米勒-拉宾检验,这是一个相当快速的随机化算法(有较小的可能性错误),用于判断一个大数是否是素数。 快速素数检验是目前大部分公钥密码体系的关键。1979年,拉宾发明了第一个非对称密码系统——拉宾密码系统(英语:Rabin cryptosystem)。它的安全性被证明和整数因式分解的复杂度相同。1981年,拉宾提出了不经意传输技术。 1987年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • 古蕨属Archaeopteris fissilis Archaeopteris halliana Archaeopteris hibernica Archaeopteris macilenta Archaeopteris obtusa古蕨属(学名:Archaeopteris),又名古羊齿属,是一属已灭
  • 太平天国之乱清朝胜利后期:  法兰西第二帝国 英国太平天国之乱,又称洪杨之乱,是指太平天国引起的战乱,广义上是指1851年1月11日江宁之战到1872年李文彩部的覆灭。其中依战事年代可分为江
  • 李 翔李翔可以指:
  • 约翰·奥基夫约翰·奥基夫(英语:John O'Keefe,1939年11月18日-),爱尔兰裔美国暨英国籍神经科学家,伦敦大学学院解剖学系和认知神经科学研究所的教授。奥基夫在纽约长大,于纽约市立大学获学士学位
  • 亨利·路易·勒夏特列亨利·路易·勒夏特列(法语:Henri Louis Le Châtelier ,1850年10月8日-1936年9月17日),又译吕·查德里,是一位十分有影响力的法国化学家和工程师。他因提出化学平衡在外界条件影响
  • 詹姆斯·史密斯·布什詹姆斯·史密斯·布什(英语:James Smith Bush,1825年6月15日-1889年11月11日)是一位美国律师、牧师、宗教作家和布什家族的祖先。
  • 大顺国大顺国,是指1950年在北京等地,由九宫道首领李懋五为首图谋成立的一个秘密结社政权。1947年,北京九宫道外九天天主李懋五与军统特务、八卦道道徒刘培中串通,谋划“宫卦合一”。李
  • 日杰尼埃沃坐标:48°46′14″N 22°58′46″E / 48.77056°N 22.97944°E / 48.77056; 22.97944日杰尼埃沃(乌克兰语:Жденієво),是乌克兰的市级镇,位于该国西部外喀尔巴阡州,处于日杰
  • Audi SportAudi Sport,以前称为quattro GmbH,是大众汽车集团(Volkswagen Group)旗下奥迪(Audi)的高性能部门。该公司成立于1983年10月,当时名为quattro GmbH,主要专业生产高性能的奥迪汽车和零
  • 加尔巴特拉站加尔巴特拉站(意大利语:Garbatella)是罗马地铁的一个车站。加尔巴特拉站开通于1990年,是罗马地铁B线的车站。距离车站200米处有旧的意大利铁路加尔巴特拉站。 维基共享资源中与