迈克尔·拉宾 (科学家)

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

相关

  • 红斑性狼疮红斑狼疮(Lupus erythematosus)为一系列自体免疫性疾病的统称,即免疫系统非正常地攻击自身正常组织。症状可能会发生于全身各处,包含关节、皮肤、肾、血球、心脏,以及肺。最常见
  • 安瑟莫安瑟莫(Anselm,1033年-1109年4月21日),又译安瑟伦,天主教译为安色莫,意大利中世纪哲学家、神学家,1093年至1109年任坎特伯雷大主教。被尊称为最后一位教父与第一位经院哲学学者。运
  • 碳足印碳足迹亦译碳足印,盖指每个人、家庭或每家公司日常释放的温室气体数量(以二氧化碳即CO2的影响为单位),用以衡量人类活动对生态环境的影响。根据以下步骤,可以有效减少碳足迹:最后
  • 锦州府锦州府(满语:ᠵᡠᠩᡤᡳᠨ ᡶᡠ,穆麟德:junggin fu),清朝时设置的府。康熙四年(1665年)改广宁府置,治所在锦县(今辽宁省锦州市)。光绪时下领二州:义州、宁远州,二厅:锦西厅、盘山厅,三县:锦
  • 1987年夏季世界大学生运动会第十四届夏季世界大学生运动会于1987年7月8日至7月19日在南斯拉夫社会主义联邦共和国萨格勒布举行,该届赛事共设12个大项。 *  主办国家/地区(南斯拉夫)
  • 克洛迪·艾涅尔克洛迪·艾涅尔(Claudie Haigneré,本名Claudie André-Deshays,1957年5月13日-),已退役的法国籍法国国家太空研究中心(1985至1999年)和欧洲空间局(1999至2002年)女性太空人、医生、政
  • 徐孝刚徐孝刚(1880年-1956年),别字申甫,四川成都府人,另载四川华阳人,中华人民共和国政治人物、中国近代军事将领。1901年考取公费留学日本,先入日本陆军成城学校完成预备学业,继入日本陆军
  • 拉莫尔方程在电动力学的领域中,拉莫尔方程(英语:Larmor formula)是用来计算非相对论性点电荷在有加速度的状态下释放电磁波的总功率。本公式是由约瑟夫·拉莫尔于1897年提出的光的波动理论
  • 世界地质公园列表世界地质公园是以其地质科学意义、珍奇秀丽和独特的地质景观为主,融合自然景观与人文景观的自然公园。由联合国教科文组织选出,此计划在2000年之后开始推行,目标是选出超过5百
  • 1,3-二氧六环1,3-二氧六环 ,又称 -二氧六环 是一种有机化合物,化学式C4H8O2。 它是饱和的六元环杂环化合物,在1-和3-位上有两个氧原子代替碳原子。相应的五元环被称为1,3-二氧五环(英语:Dioxo