迈克尔·拉宾

✍ dations ◷ 2024-09-20 13:43:23 #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年,拉宾提出了不经意传输(英语:Oblivious transfer)技术。 1987年,拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。

相关

  • 信息架构信息架构(英语:Information Architecture)是在信息环境中,影响系统组织、导览、及分类标签的组合结构。它是也基于信息架构方法论,并运用内容管理技术来管理和组织信息的一个专门
  • 冷却剂冷却剂是一种流过或环绕某个系统来防止该系统过热的流体。它通过将该系统产生的热量传导到其他的系统来使用或消耗热量。理想的冷却剂具有高热容量,低黏度,廉价,无毒,化学惰性,既
  • FAO联合国粮食及农业组织(法语:L'Organisation des Nations Unies pour l'Alimentation et l'Agriculture,缩写为ONUAA; 英语:Food and Agriculture Organization of the United Na
  • 法国语言法国语言(法语:Langues régionales ou minoritaires de France)是指法国境内使用的各种语言,法语是法国唯一的官方语言,但是许多居民也使用不同的方言。因为许多外国人移居法国,
  • 塔塔尔语鞑靼语(鞑靼语:татарча)又称塔塔尔语,属于阿尔泰语系,是鞑靼斯坦地区使用的语言。鞑靼语本来用阿拉伯字母,斯大林时期改用西里尔字母,2001年鞑靼斯坦共和国政府决定改用土耳
  • 脎(英语:Osazone,汉语拼音:sà,注音:ㄙㄚˋ),也称糖脎,是糖类的苯肼衍生物。糖脎为难溶于水的黄色结晶,由糖与苯肼反应生成,分解又得到原来的糖,因此可以用于糖的提纯。费歇尔在当年研究
  • 北伦敦北伦敦(英语:North London)是英国英格兰伦敦的北部地区,一般多指伦敦位于泰晤士河北岸的地区,和南伦敦相对。北伦敦是伦敦的历史中心区,伦敦金融区和伦敦的大部分捷运路线都位于北
  • 牛市投资学中,普遍相信市场趋势存在于金融市场,并大致可分为主要趋势,次要趋势(短期)和持续趋势(长期)。市场价格根据趋势而移动是技术分析学说的主要假设;在股票市场中,有关市场趋势的论
  • 承德市承德市市标承德市,简称承,旧称热河,是中华人民共和国河北省下辖的地级市,位于河北省东北部。市境南邻天津市、唐山市、秦皇岛市,东接辽宁省朝阳市,东北与内蒙古自治区赤峰市毗邻,
  • 亚历山大·伊万琴科夫亚历山大·谢尔盖耶维奇·伊万琴科夫(俄语:Александр Сергеевич Иванченков,1940年9月28日-)是苏联宇航员,航天工程师。1940年生于伊万捷耶夫卡。196