迈克尔·拉宾 (科学家)

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

相关

  • 王士禛清禹之鼎绘《王士禛幽篁坐啸图卷》,故宫博物院藏王士禛(1634年9月17日-1711年6月26日),赐名士祯,小名豫孙,字贻上,号阮亭,别号渔洋山人,人称王渔洋,谥文简。山东新城(今山东桓台)人,清代著
  • cope在心理学上, 因应(英语:Coping)有意识的努力,去解决个人和人际关系问题,来控制、减少或容忍压力和衡突的。心理应对机制是通常被称为 应对策略 或 应对技巧 (英语:coping strategies
  • 芝加哥1号堆芝加哥1号堆(英语:Chicago Pile-1)是人类历史上第一个核子反应堆,由恩里科·费米、利奥·西拉德等人在美国芝加哥大学建立,于1942年12月2日产生可控的铀裂变链式反应,最初输出功率
  • Clitellata环带纲(Clitellata),是环节动物门下的一个纲,在系统演化上为一个单系群,包括蛭(蚂蟥,含水蛭、旱蛭)和寡毛类(如蚯蚓)等。它们的特色是身体上有一节像是“衣领”一样的环带,在生育时会产
  • 司马江汉司马江汉(日语:司馬江漢,1747年-1818年11月19日),日本江户时代学者与艺术家。出生于今日本本州岛中部的东京,本名安藤峻。凭借其西式手法作画而闻名于世。他多年致力于绘画技巧的创
  • 丹尼尔·文森特·加莱瑞丹尼尔·文森特·加莱瑞(英语:Daniel Vincent Gallery,1901年7月10日-1977年1月)是一位美国海军将领,最高军衔为少将。加莱瑞出战于第二次世界大战的大西洋战场,曾掳获德国海军的“
  • 卡乔纳帕特塞尼卡乔纳帕特塞尼(Kachhauna Patseni),是印度北方邦Hardoi县的一个城镇。总人口13504(2001年)。该地2001年总人口13504人,其中男性7260人,女性6244人;0—6岁人口2252人,其中男1163人,女1
  • 2016年亚洲沙滩运动会越武道比赛越武道 竞赛在 2016年亚洲沙滩运动会 于 岘港, 越南举办。从2016年9月30日至10月2日在东海公园举行。Template:Events at the 2016 Asian Beach Games
  • 耀皮玻璃上海耀皮玻璃集团股份有限公司,简称上海耀皮玻璃集团股份、上海耀皮玻璃集团,以及上海耀皮玻璃(英语:SYP Glass Group Company Limited,上交所:600819/900918,简称:耀皮玻璃/耀皮B股
  • 弗林德斯山脉弗林德斯山脉(Flinders Ranges)是南澳大利亚州最大的山脉。弗林德斯山脉起始于阿德莱德以北约200 km(125 mi)处,山脉全长430 km(265 mi)。最高峰圣玛丽峰高1,171米(3,842英尺)。