迈克尔·拉宾 (科学家)

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

相关

  • 超常现象超常现象(英语:Paranormal),又称灵异现象,是指与科学和常识相互矛盾的现象。因为超常现象无法用已存在的逻辑架构、或普遍被接受的现实知识来解释。这些真实性并未确定的现象,通常
  • 卡尔洪县卡尔霍恩县 (Calhoun County, Georgia)是美国乔治亚州西南部的一个县。面积734平方公里。根据美国2000年人口普查估计,共有人口6,320人。县治摩根 (Morgan)。成立于1854年2月
  • 泛生物地理学泛生物地理学(英语:Panbiogeography)是生物地理学的一种研究方法,由意大利、法国籍植物学家利昂·克鲁瓦扎(英语:Léon Croizat)提出。其具体操作方法是将某个分类下的物种各个分离
  • 憔悴潘郎《憔悴潘郎》(英语:),中文又作《奉子成婚》、《拖家带口》,是美国的一部情景喜剧,由Michael G. Moye(英语:Michael G. Moye)和Ron Leavitt(英语:Ron Leavitt)制片,福克斯播出。它于1987年
  • 布兰卡二世布兰卡二世(法语:Blanche II de Navarre;西班牙语:Blanca II de Navarra;1424年6月9日-1464年12月2日),名义上的纳瓦拉女王。她是亚拉冈国王胡安二世和纳瓦拉女王布兰卡一世的次女,长
  • 山﨑夕贵山﨑夕贵(日语:山﨑 夕貴,1987年8月4日-),出身于冈山县仓敷市。日本富士电视台播报员。高中毕业于冈山县立仓敷天城高等学校,大学毕业于冈山大学经济学部。2010年正式加入富士电视台成
  • 高通骁龙骁龙(英语:Snapdragon)处理器是美国高通公司(Qualcomm)为移动设备(智能手机、平板电脑以及SmartBook)所推出的处理器系列平台名称。Snapdragon的中央处理器 (CPU) 采用ARM RISC架构
  • 范柏群范柏群(1987年2月18日-),是一名中国足球运动员。2005年,范柏群进入中国足球超级联赛球队天津泰达的一线队名单。但很快他又被调到预备队,2007年夏季再次进入一队。2008年3月30日,他
  • 轴心国与同盟国轴心国与同盟国(英文:Axis & Allies)是一个以第二次世界大战为背景的战略图版游戏,一共售出近2百万份。轴心国与同盟国原本由拉里·哈里斯(Larry Harris)设计,新星游戏设计在1981年
  • 建宁站建宁站位于江苏省南京市建宁乡,有宁铜铁路经过,邮政编码210041。车站建于1969年:227,现仅办理货运,不办理客运业务,车站及其上下行区间均未电气化。车站距离南京西站47公里,隶属中