迈克尔·拉宾 (科学家) 提示：此条目的主题不是麥可·拉賓 (小提琴家)。
迈克尔·O·拉宾（希伯來語：מִיכָאֵל אֹשֶׁר רַבִּין，英語：Michael Oser Rabin，1931年9月1日— ）是一名以色列计算机科学家，1976年图灵奖得主。 生平拉宾出生于德国布雷斯劳（二战后成为波兰弗羅茨瓦夫），父亲是一个拉比。 1953年，他获得希伯来大学的理学硕士，1956年获普林斯顿大学博士学位。 1959年，拉宾和达纳·斯科特共同发表了“有限自动机与其判定性问题”（Finite Automata and Their Decision Problems）的论文，提出了非确定自动机的观点。他们也因此获得了1976年的图灵奖，并做“计算机复杂性”（Complexity of Computations）的演讲。图灵奖的引文是：
非确定自动机已经成为计算复杂度理论中的一个重要概念，特别是在描述P与NP问题的复杂度类时。 1969年，拉宾证明N successors的二阶逻辑是可判定的。[2]证明的关键部分暗示了奇偶游戏的确定性。1975年，拉宾发明了米勒-拉宾检验，这是一个相当快速的随机化算法（有较小的可能性错误），用于判断一个大数是否是素数。[3][4] 快速素数检验是目前大部分公钥密码体系的关键。1979年，拉宾发明了第一个非对称密码系统——拉宾密码系统。它的安全性被证明和整数因式分解的复杂度相同。[5]1981年，拉宾提出了不经意传输技术。[6] 1987年，拉宾和理查德·卡普提出了一个著名的字符串搜索算法——拉宾-卡普算法。[7] 参考
外部链接 |
|||||||||||||||||||
Index:
pl ar de en es fr it arz nl ja pt ceb sv uk vi war zh ru af ast az bg zh-min-nan bn be ca cs cy da et el eo eu fa gl ko hi hr id he ka la lv lt hu mk ms min no nn ce uz kk ro simple sk sl sr sh fi ta tt th tg azb tr ur zh-yue hy my ace als am an hyw ban bjn map-bms ba be-tarask bcl bpy bar bs br cv nv eml hif fo fy ga gd gu hak ha hsb io ig ilo ia ie os is jv kn ht ku ckb ky mrj lb lij li lmo mai mg ml zh-classical mr xmf mzn cdo mn nap new ne frr oc mhr or as pa pnb ps pms nds crh qu sa sah sco sq scn si sd szl su sw tl shn te bug vec vo wa wuu yi yo diq bat-smg zu lad kbd ang smn ab roa-rup frp arc gn av ay bh bi bo bxr cbk-zam co za dag ary se pdc dv dsb myv ext fur gv gag inh ki glk gan guw xal haw rw kbp pam csb kw km kv koi kg gom ks gcr lo lbe ltg lez nia ln jbo lg mt mi tw mwl mdf mnw nqo fj nah na nds-nl nrm nov om pi pag pap pfl pcd krc kaa ksh rm rue sm sat sc trv stq nso sn cu so srn kab roa-tara tet tpi to chr tum tk tyv udm ug vep fiu-vro vls wo xh zea ty ak bm ch ny ee ff got iu ik kl mad cr pih ami pwn pnt dz rmy rn sg st tn ss ti din chy ts kcg ve
Portal di Ensiklopedia Dunia
