迈克尔·拉宾 (科学家)

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

相关

加卫苗加卫苗,（亦作Gardasil、Gardisil、Silgard、recombinant human papillomavirus vaccine ），是人类乳突病毒疫苗的一种，用于预防特定毒株的人类乳突病毒（HPV），特别是6，11，16和18型。约7
小脑小脑（cerebellum，指“大脑后下方的脑”）是位于后颅窝（英语：Posterior cranial fossa）的脑组织。小脑在感觉感知、协调性，和运动控制中扮演重要角色；它也和注意、语言等很多认知功能
员工福利员工福利（英语：Employee benefit），是雇员因为受雇工作而有权享用的福利，通常是由雇主直接给予，如折扣购物、免费穿梭巴士等；也可能由第三者提供，如医疗服务，只要出示有效的工作证等。
格哈德·根岑格哈德·根岑（Gerhard Karl Erich Gentzen，1909年11月24日－1945年8月4日）是德国的数学家和逻辑学家。他生于德国的格赖夫斯瓦尔德，在1929年到1933年期间是赫尔曼·外尔在哥廷根大
博茨瓦纳华人博茨瓦纳华人是指在非洲国家博茨瓦纳的华侨华人，2009年时，总人数约为5至6千。主要分布在首都哈博罗内和第二大城市弗朗西斯敦。
董鼎山董鼎山（1922年－2015年12月19日），美国文学家、翻译家、文学评论家。纽约市立大学荣休教授。曾任《纽约时报》书评人。1922年，董鼎山生于浙江宁波。后赴上海进学。1945年，毕业于上海
时文选粹《时文选粹》是由一系列书籍组成的一个书籍组的名称，通常有具有灵感和激励性的短篇小品文和散文组成，该书籍组的主编是王玉强。《时文选粹》在2001年编辑出版发行，以面向学生为
廿二史考异《二十二史考异》又名《廿二史考异》，清代钱大昕撰，100卷，附三史拾遗五卷、诸史拾遗五卷。钱大昕少年专心史学，四十岁开始撰写《二十二史考异》，“岁有增益，卷帙滋多”，至五十五岁
林荣昌林荣昌，云南籍，著名葫芦丝、巴乌作曲家、演奏家，自1960年代开始活跃于音乐界，曾为中国民族管弦乐学会葫芦丝巴乌专业委员会常务理事，云南省音乐家协会葫芦丝巴乌学会顾问、云南省
齐璧亭齐璧亭（1883年－1968年），名国梁，男，直隶宁津（今属山东）人，中国教育家、政治人物，曾任河北省政协副主席。