Michael Rabin
Pour les articles homonymes, voir Michael Rabin (violoniste) et Rabin (homonymie).
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Michael Rabin
| Naissance |  (92 ans)Wrocław |
|---|---|
| Nom dans la langue maternelle | Michael Oser Rabin |
| Nationalité | israélienne |
| Formation | Université hébraïque de Jérusalem Hebrew Reali School (en) Université de Princeton |
| Activités | Informaticien, pédagogue, cryptographe, mathématicien, professeur d'université |
| Père | Israel Abraham Rabin (d) |
| Mère | Ester Rabin (d) |
| Fratrie | Chaim Rabin (en) (frère consanguin) Miriam Ben-Peretz (en) |
| Enfant | Tal Rabin |
| A travaillé pour | |
|---|---|
| Membre de | |
| Directeur de thèse | |
| Distinctions | Prix Turing () Liste détaillée Prix Turing () Prix Harvey () Conférence Gibbs () Prix Israël () Prix Paris-Kanellakis () Gödel Lecturer () Prix EMET pour l'Art, la Science et la Culture (en) () Membre étranger de la Royal Society () IACR Fellow () Prix Dan-David () ACM Fellow () Prix Rothschild en sciences Prix Wolf de mathématiques Docteur honoris causa de l'Institut Weizmann |
modifier - modifier le code - modifier Wikidata
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
- 1976 : prix Turing
- 2004 : Gödel Lecturer avec une conférence intitulée Proofs persuasions and randomness in mathematics.
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).
- ↑ Traduction libre de : (en) Citation du prix ACM Turing.
- ↑ (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 )
- ↑ (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
Sur les autres projets Wikimedia :
- Michael Rabin, sur Wikimedia Commons
Articles connexes
- Test de primalité de Miller-Rabin
- Cryptosystème de Rabin
- Algorithme de Rabin-Karp
- Transfert inconscient
Liens externes
- Notices d'autorité
: - VIAF
- ISNI
- BnF (données)
- IdRef
- Pays-Bas
- Israël
- Tchéquie
- WorldCat
- (en) Description courte dans le Information Science Hall of Fame à l'université de Pittsburgh
- (en) The Past, Present and Future of Oblivious Transfer, workshop sur le transfert inconscient à l'université de Haïfa, 2005
- Ressources relatives à la recherche :
- Digital Bibliography & Library Project
- Mathematics Genealogy Project
- Royal Society
- Scopus
Portail de la cryptologie 
Portail de la sécurité informatique 
Portail de l'informatique théorique
