迈克尔·拉宾 (科学家)

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

相关

  • 丁香园丁香园(DXY),始建于2000年7月23日,创办者李天天,是一个医学知识分享网站。该网站曾于2014年9月2日获得腾讯公司7000万美元投资。2019年1月,丁香园指权健产品骨正基鞋垫价格是天价
  • 无板纲原口动物 Protostomia见内文无板纲(学名:Aplacophora)是软体动物门的一个纲,曾被认为是多系群,近年再次被确认为单系群。仅有300种左右。是一类身体呈蠕虫状的软体动物。过往当生
  • 期望在概率论和统计学中,一个离散性随机变量的期望值(或数学期望,亦简称期望,物理学中称为期待值)是试验中每次可能的结果乘以其结果概率的总和。换句话说,期望值像是随机试验在同样的
  • 巴地省巴地头顿省(越南语:Tỉnh Bà Rịa - Vũng Tàu/.mw-parser-output .han-nom{font-family:"Nom Na Tong","Han-Nom Gothic","Han-Nom Ming","HAN NOM A","HAN NOM B","Ming-Lt
  • 大学校训列表此段落为台湾各大学之校训特殊
  • 构件在机械工程学中,指称机器中每一个独立的运动单元体称为一个构件,它可以由单个或数个机械零件构成。两个以上的构件可进一步组成运动副。此外,构件的概念被使用到计算机科学中,指
  • 东姑阿都拉曼国家公园东姑阿都拉曼公园 (马来语:Taman Negara Tunku Abdul Rahman) 是马来西亚第一座海洋型国家公园,坐落在马来西亚沙巴州亚庇岸外的南中国海上,由佳雅岛(Gaya Island),沙比岛(Sapi Isl
  • 阿阿拉姆巴达阿阿拉姆巴达(Aarambhada),是印度古吉拉特邦Jamnagar县的一个城镇。总人口15008(2001年)。该地2001年总人口15008人,其中男性7725人,女性7283人;0—6岁人口2409人,其中男1294人,女1115
  • 第三位影武者《第三位影武者》(第三の影武者)为1963年上映的日本时代剧,原作为南条范夫。
  • 基尔夏达赫峰坐标:47°04′04″N 11°20′33″E / 47.067861°N 11.342444°E / 47.067861; 11.342444基尔夏达赫峰(意大利语:Kirchdach),是意大利的山峰,位于该国西部,由蒂罗尔州负责管辖,属于