Accueil🇫🇷Chercher

Michael Rabin

Michael Oser Rabin, né le à Breslau en Allemagne, maintenant Wrocław en Pologne) est un informaticien et un logicien israélien. Il a été récipiendaire du prix Turing, la récompense la plus prestigieuse en informatique.

Biographie

Rabin est né fils de rabbin. Il a obtenu une maîtrise de l'université hébraïque de Jérusalem en 1953 et un doctorat de l'université de Princeton en 1956.

La citation pour le prix Turing, attribué en 1976 conjointement à Michael Rabin et Dana Scott pour un article écrit en 1959, déclare qu'on a accordé la récompense :

« Pour leur article « Finite Automata and Their Decision Problem » présentant l'idée des Automates finis non déterministes qui s'est révélée être un concept d'une énorme valeur. Leur article classique a été une source continue d'inspiration pour le travail qui s'est ensuivi dans ce domaine[1]. »

Les machines non déterministes sont devenues un concept clé dans la théorie de la complexité, en particulier avec la description des classes de complexité P et NP.

Travaux

En 1957 et 1958, Rabin a démontré que divers problèmes de théorie de groupes sont indécidables (ce sont les premiers du genre après ceux de Sergei Adian en 1955).

En 1969, Rabin a démontré que l'arithmétique monadique du second ordre (avec k successeurs) est décidable[2]. C'est le théorème de Rabin sur les arbres.

En 1974, Rabin a démontré avec Michel Fischer que l'arithmétique de Presburger a une complexité super-exponentielle.

En 1975, Rabin a été un pionnier des algorithmes probabilistes. Il a notamment inventé un algorithme randomisé, le test de primalité de Miller-Rabin, qui détermine très rapidement, mais avec une minuscule probabilité d'erreur, si un nombre est un nombre premier. Cet algorithme est essentiel à l'implémentation de la plupart des algorithmes de cryptographie asymétrique. Il a aussi écrit l'un des premiers algorithmes géométriques probabilistes, pour la recherche des deux points les plus rapprochés[3].

En 1979, Rabin a inventé le cryptosystème de Rabin, qui est le premier cryptosystème asymétrique dont la sécurité se réduit à la difficulté de la factorisation d'un nombre entier.

En 1981, Rabin a inventé la technique du transfert inconscient, permettant à un expéditeur de transmettre un message à un récepteur afin que celui-ci ait une certaine probabilité d'apprendre le message, tandis que l'expéditeur ne sait rien du succès du récepteur.

En 1987, Rabin, ainsi que Richard Karp, a créé un des algorithmes efficaces les plus connus de recherche de chaîne de caractères, l'algorithme de Rabin-Karp.

Les recherches actuelles de Rabin se concentrent sur la sécurité des systèmes informatiques et il est actuellement professeur titulaire de la chaire d'informatique Thomas J. Watson Sr. à l'université Harvard et professeur d'informatique à l'université hébraïque de Jérusalem.

Prix et distinctions

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Michael O. Rabin » (voir la liste des auteurs).
  1. Traduction libre de : (en) Citation du prix ACM Turing.
  2. (en) Michael O. Rabin, « Decidability of second-order theories and automata on infinite trees », Bulletin of the American Mathematical Society, vol. 74, no 5, , p. 1025–1029 (ISSN 0002-9904 et 1936-881X, lire en ligne, consulté le )
  3. (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, (réimpr. 1997, 2000), 1re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 9, p. 273

Voir aussi

Articles connexes

Liens externes

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.