迈克尔·拉宾 (科学家)

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

相关

  • 国际辅助语国际辅助语(International Auxiliary Language(IAL、auxlang)、Interlanguage)是为帮助使用不同的民族语言的人们更好的进行语言交往而设计的一种辅助性语言。其目的并非是为了
  • 吠陀时代吠陀文化(约前16世纪—前7世纪)是指吠陀经典所记载和反映的印度历史时期文化。透过吠陀经典的古梵文史料,所谓的吠陀经典即指四吠陀——梨俱吠陀、娑摩吠陀、夜柔吠陀、阿闼婆
  • 素可泰历史城镇和相关历史城镇群素可泰历史公园(泰语:อุทยานประวัติศาสตร์สุโขทัย)位于泰国北部素可泰府,为泰国最古老的素可泰王朝的首都遗迹。1991年,以素可泰古城以及邻近的西撒
  • 摩西湖市摩西湖市(Moses Lake)位于美国华盛顿州格兰特县。美国2010年人口普查时人口为20,366人。摩西湖市是格兰特郡最大的城市。摩西湖市有一个姊妹市:摩西湖市与米泽市之间有很长的历
  • 大卫·弗里德曼知识产权 市场化 自由放任 小政府主义 负所得税 公开市场操作 私有财产 私有化 经济主题 大卫·德瑞特·弗里德曼(英语:David Director Friedman,或翻译为大卫·弗里德曼,1945年
  • 武田翔太 武田翔太(日语:武田 翔太/たけだ しょうた ,1993年4月3日-)是一名出身于日本宫崎县宫崎市的棒球选手,司职投手,目前效力于日本职棒福冈软银鹰。80 平石洋介 | 80 本多雄一 | 83 立
  • 刘玉兰刘玉兰(Lauw Giok Lan;1883年-1953年)是一名闽南裔印尼华人记者、作家。他是《新报》的创始人之一。1883年,刘玉兰出生于荷属东印度巴达维亚。他在一所福建话学校接受教育,同时也
  • 沃尔特·史考特·休斯顿沃尔特·史考特·休斯顿(1912年5月30日-1993年12月23日)是向大众推广天文学的美国业余天文学家。他于1946年至1993年在《天空与望远镜》杂志上撰写"深空奇观"(Deep-Sky Wonders)
  • 罗贝尔·德·索邦罗贝尔·德·索邦(法语:Robert de Sorbon,1201年10月9日-1274年8月15日),法国神学家,曾担任法王路易九世的私人神职人员。他是索邦学院的创建者。出生于索本(Sorbon,位于现今的阿登
  • 李克如李克如(1904年-1998年),男,湖南衡阳人,中华人民共和国政治人物,曾任中国人民解放军海军航空兵副政治委员兼政治部主任,甘肃省政协副主席,甘肃省人大常委会副主任,第五、六届全国政协委