迈克尔·拉宾 (科学家)

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

相关

  • 肾上腺素拮抗剂肾上腺素拮抗剂(英语:adrenergic antagonist)指的是抑制肾上腺素接受器(英语:adrenergic receptor)功能的药物。人体中有五个肾上腺素接受器,而这五个肾上腺素接受器又分为两类。α
  • 英国地质调查局1835Nottingham NG12 5GG£52m英国地质调查局(英语:British Geological Survey,BGS)是一个部分由国家赞助的组织,旨在透过有系统性的测量、监测和研究,提升英国陆地及其大陆架的地
  • 中队和平期间罕见军事强国有实力编制普通国家有实力编制连(英语:Company)是现代陆军、海军陆战队等军种的一种编制,由若三个排到六个排组成,人数大约在80-150人之间。譬如在三三制的
  • 刺齿枝子花刺齿枝子花(学名:)为唇形科青兰属下的一个种。
  • 钮玉庚钮玉庚,字润生,号韵笙,浙江会稽县人,寄籍顺天府大兴县。清朝翰林。同治四年(1865年)乙丑科二甲进士,选庶吉士,散馆授编修。同治十二年(1873年)任山东学政。官至侍讲学士。
  • 郑煊浩郑煊浩(1988年6月13日 - )是一名韩国现代五项运动员,身高1.75米,体重70千克。曾参加2010年广州亚运会现代五项比赛,并获得男子个人第十名和男子团体金牌。
  • 侘寂侘寂(日语罗马音:Wabi-sabi),一种以接受短暂和不完美为核心的日式美学。侘寂的美有时被描述为“不完美的,无常的,不完整的”。它是从佛教三法印派生的概念,特别是无常。侘寂的特征
  • 辉钼矿辉钼矿是一种钼的矿物,化学组成为二硫化钼。具有与石墨相似的外观和晶体结构,因而和石墨一样具有润滑效果。晶体中,钼原子以层状排列,夹在两层硫原子之间。该结构内的钼硫键很强
  • 哈剌孩卫哈剌孩卫,明朝的卫。明成祖永乐四年(1406年)二月,明朝在哈剌孩河(今哈拉哈河)流域设立哈剌孩河千户所,后升为卫。作为羁縻卫,管理当地的蒙古族和其他民族。辖境相当于今内蒙古自治区
  • 新普罗维登斯岛新普罗维登斯岛(New Providence),是巴哈马的一个岛屿,为首都拿骚(Nassau)所在地。新普罗维登斯岛位于巴哈马群岛北部,安德罗斯岛和伊柳塞拉岛之间。新普罗维登斯岛总面积207 km²。