迈克尔·拉宾 (科学家)

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

相关

  • 宫崎县宫崎县(日语:宮崎県/みやざきけん Miyazaki ken */?)位于九州东南部,东濒太平洋、南接鹿儿岛县、西接熊本县、北接大分县。首府位于宫崎市。1960年代以降为蜜月的圣地,主要是在
  • 激微波激微波(英语:MASER),音译为激微波,义译为激微波或微波激射器,是受激放大微波辐射(英语:Microwave Amplification by Stimulated Emission of Radiation)的头字母。它指通过受激辐射放
  • 半鸟半鸟属(属名:Unenlagia,意为“一半的鸟”)又名若鸟龙,是兽脚亚目恐龙的一属,生存于晚白垩纪的南美洲,化石发现于阿根廷内乌肯省中部山区。半鸟属于驰龙科的半鸟亚科,是群奇特、极度
  • 底斑尖鼻鲀底斑尖鼻鲀为辐鳍鱼纲鲀形目四齿鲀亚目四齿鲀科的其中一种,为热带海水鱼,分布于太平洋夏威夷及日本海域,栖息深度124-274米,体长可达7.6公分,栖息在沙石底质底层水域,生活习性不明
  • 黑海舰队黑海舰队(俄语:Черноморский флот)是俄罗斯(以及苏联)的一支海军舰队,苏联时叫红旗黑海舰队(Краснознаменный Черноморский флот)
  • 门钉肉饼门丁肉饼或门钉肉饼是北京的一种传统小吃。因为形状像古时候城门上的门钉而得名。而且据说门丁肉饼有吉祥的含义。据说清朝时皇宫的御膳房为特意慈禧太后做了一道有馅的点心
  • 伊金霍洛草原伊金霍洛,蒙古语意为“君主的圣地”,位于中国内蒙古地区鄂尔多斯高原东南部,全称为伊金霍洛草原。成吉思汗陵(衣冠冢)在那里,因此成为蒙古族心中的圣地。参见:内蒙古自治区文物保
  • 克利夫·伯顿克利夫·伯顿(英语:Clifford Lee "Cliff" Burton,1962年2月10日-1986年9月27日)是一位美国音乐家,重金属乐队金属乐队的第二任贝斯手。克利夫于1982年加入了金属乐队,并录制其首张
  • 横波横波,又称为高低波,是介质振动方向和波行进方向垂直的一种波。若此波沿着x轴移动,则介质的振动方向为与x轴垂直的方向上。举例来说绳波就是一种横波。水波在外表看起来具有横波
  • 比小说更甜蜜 《比小说更甜蜜》(英语:Sweeter than Fiction)是美国创作歌手泰勒·斯威夫特的一首歌曲,收录于英国电影《成名机会》的原声带。 这首歌是由泰勒·斯威夫特和杰克·安东诺夫共同