迈克尔·拉宾 (科学家)

✍ dations ◷ 2025-11-24 23:47:24 #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年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • 哺乳类动物哺乳动物是指脊椎动物亚门下哺乳纲(学名:Mammalia)的一类用肺呼吸空气的温血脊椎动物,因能通过乳腺分泌乳汁来给幼体哺乳而得名。按照《世界哺乳动物物种》(Mammal Species of th
  • 内共生体共生体学说(英语:Symbiogenesis),又称内共生学说(英语:endosymbiotic theory),是关于真核生物细胞中的一些自主细胞器ㄧ线粒体和叶绿体起源的学说。根据这个学说,它们起源于共生于真
  • 微博桌面微博桌面是由新浪微博发布的一款新浪微博桌面客户端软件,具有阅读与发布微博、聊天、新消息提示、快速回复消息等功能的微博桌面客户端。自2015年2月后软件再未进行过任何更
  • 砑头虫目砑头虫目(学名:Proetida),又名蚜头虫目,是三叶虫纲下的其中一目,出现在奥陶纪,是泥盆纪后期的大灭绝中唯一幸存的三叶虫类,最后于二叠纪末的大灭绝中消失。具有流线型的身体,但身上没
  • 詹姆斯·格林·哈代詹姆斯·格林·哈代(James Greene Hardy,1795年5月3日-1856年7月16日),美国弗吉尼亚卢嫩堡县人,是一名美国肯塔基州政治人物,他曾经代表美国人党当选第15任肯塔基州副州长。1854年,
  • 米哈伊尔·米哈伊洛维奇·巴赫京米哈伊尔·米哈伊洛维奇·巴赫金(俄语:Михаил Михайлович Бахтин;1895年11月17日-1975年3月7日),出生于俄国奥廖尔,是现代文学理论与文学批评重要理论家。巴
  • 秋山照子秋山照子(1954年4月17日-2014年3月8日),日本女性配音员。本名相同,艺名:あきやまるな。出身于东京都中野区。身高150cm。A型血。电视艺人中心(日语:テレビタレントセンター)20期生。
  • 三时四餐《履行月球公约项目第1弹——自给自足超高速合宿生活——三时四餐》(韩语:달나라 공약 이행 프로젝트 1탄 자급자족 초고속 합숙 라이프 삼시네세끼),简称《三时四餐》(韩语:삼시
  • 小叶云实小叶云实(学名:)是豆科云实属的植物,为中国的特有植物。分布在中国大陆的广西、湖南、江西、广东等地,生长于海拔500米的地区,常生长在山脚灌丛中或溪边旁,目前尚未由人工引种栽培
  • 崔龙洙崔龙洙(韩语:최용수,罗马化:Choi Yong-Soo,1973年9月10日-),退役韩国职业足球运动员,现任K联赛首尔FC主教练。球员时代,崔龙洙曾在韩国和日本的几家球队效力,司职前锋,被誉为“韩国传奇