迈克尔·拉宾 (科学家)

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

相关

  • 马德堡马格德堡(Magdeburg)位于易北河畔,是德国萨克森-安哈尔特州的首府,它是本州仅次于哈雷的第二大城市,也是本州三个无属县城市之一。马格德堡是基督教和天主教的主教教区首邑,拥有两
  • 火龙果火龙果又称红龙果、龙珠果,正确名称叫仙人掌果、量天尺果,是仙人掌科三角柱属或蛇鞭柱属(英语:Selenicereus)植物果实。水果呈椭圆形,直径10-12cm,外观为红色或黄色,有绿色圆角三角形
  • 凯格尔运动凯格尔运动(英语:Kegel exercise),又称骨盆运动(英语:pelvic floor exercise),于1948年由美国阿诺·凯格尔医生公布,借由重复缩放部分的骨盆底(英语:Pelvic floor)肌肉进行,用以帮助怀孕
  • 拉玛一世帕佛陀约华朱拉洛(泰语:พระพุทธยอดฟ้าจุฬาโลก,皇家转写:Phra Phutthayotfa Chulalok;1737年3月20日-1809年9月7日),即拉玛一世(Rama I),泰国曼谷王朝(扎克里王朝)第
  • 拉伯克县拉伯克县(Lubbock, Texas)是美国德克萨斯州西北部的一个县。面积2,333平方公里。根据美国2000年人口普查,共有人口242,628人。县治拉伯克(Lubbock)。成立于1876年8月21日,县政府成
  • 兰辛兰辛(英语:Lansing)是美国密歇根州首府,城市主要位于英厄姆县,还有少部分位于伊顿县和克林顿县,人口119,128(2000年),都会区人口454,044,其中白人占65.28%、非裔美国人占21.91%、亚裔
  • 河狸溪河狸溪(英语:Beaver Creek)是加拿大育空地区的一个社区,是加拿大最西的居民点。河狸溪人口不到100人。河狸溪平均海拔为762米,气候为亚寒带气候。1月份平均气温为−26.9 °C,7月
  • 蚌埠公交微1路蚌埠公交微1路,是中国安徽省蚌埠市的一条社区巴士线路,使用8米纯电动空调车。由张公湖首末站开往紫荆名流二期东门,由蚌埠市公共交通集团有限公司运营、管理。整装待发的微1线
  • 维克托·卡文迪什,第九代德文郡公爵维克托·克里斯蒂安·威廉·卡文迪什,第九代德文郡公爵,KG,GCMG,GCVO(Victor Christian William Cavendish, 9th Duke of Devonshire,1868年5月31日-1938年5月6日),英国政治人物。曾
  • 卡斯蒂利亚-拉曼恰联合左翼卡斯蒂利亚-拉曼恰联合左翼(西班牙语:Izquierda Unida de Castilla-La Mancha,缩写为IU CLM)是西班牙左翼政党联盟联合左翼在卡斯蒂利亚-拉曼恰自治区的分支。它成立于1986年,主