迈克尔·拉宾 (科学家)

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

相关

  • 尸冷尸冷(Algor mortis)是指恒温动物死亡后,新陈代谢和产热停止,由于自然散热体温下降的现象。尸冷的温度下限是环境温度,但后来腐烂过程开始后,尸体温度可能又会上升。成年人类死亡后
  • 壬二酸壬二酸是一种饱和二羧酸,化学式为HOOC(CH2)7COOH。在标准状态下,纯壬二酸呈白色粉末状。壬二酸自然存在于小麦、黑麦和大麦等榖物中。壬二酸可作为聚合物和增塑剂等化工产品的
  • 图利奥·勒维奇维塔图利奥·列维-齐维塔(意大利语:Tullio Levi-Civita,1873年3月29日-1941年12月29日),意大利数学家。
  • 丹尼尔·卢瑟福丹尼尔·卢瑟福(英文:Daniel Rutherford,1749-1819),苏格兰化学家,氮气的发现者之一。丹尼尔的父亲约翰·卢瑟福(1695年-1779年)是爱丁堡大学医学院的教授。七岁时他在私人教育家蒙代
  • 东台湾东台湾是台湾一个常用的地区简称,又有“后山”之称。东台湾亦指台湾东岸,多指中央山脉以东的花莲县和台东县,故亦称“花东地区”;有时东台湾还包含宜兰县(雪山山脉以东,中央山脉以
  • 克拉克国际机场克拉克国际机场(英语:Clark International Airport;他加禄语:Paliparang Pandaigdig ng Clark;IATA代码:CRK;ICAO代码:RPLC),又称马嘉柏臬国际机场,是一位于菲律宾邦板牙省安赫莱斯市克
  • 北非雪松北非雪松(拉丁语:)是雪松属下的一个物种,主要分布在阿尔及利亚和摩洛哥境内的阿特拉斯山脉海拔1370至2200米的森林。
  • 莱卡一世莱卡(1939年4月5日-2011年11月30日),阿尔巴尼亚王国唯一一任君主索古一世和匈牙利贵族洁拉尔蒂·阿波尼·德·纳加-波尼的独子。他出生后的两天(4月7日),阿尔巴尼亚即被意大利王国
  • 业务业务意指某种有目的的工作或工作项目,业务也是业务员、业务人员的简称,是指一群专门做销售、行销的工作者,负责将公司之产品或服务销售给客户。从理论定义上而言,业务的活动主体
  • 治愈系治愈系是日本近年出现的词语,原本是指电视上演出的女性艺人中能让人感到平静、治愈、舒畅的人。现时(尤其在动漫画等二次元作品中),治愈系通常是指能给予观众积极、爱、阳光、温