Michael Rabin

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir Michael Rabin (violoniste) et Rabin (homonymie).
Michael Rabin
Michael O. Rabin.jpg

Michael Rabin

Naissance
Nationalité
Formation
Activités
Employeur
Distinctions

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

Repères bibliographiques[modifier | modifier le code]

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 machines 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'en est suivi 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.

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) en 1955).

En 1969, Rabin a démontré que l'arithmétique monadique du second ordre (avec k successeurs) est décidable.

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

En 1975, Rabin a 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.

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 à l'intractabilité de la factorisation d'un nombre entier.

En 1981, Rabin a inventé la technique du transfert inconscient (en), 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.

Notes et références[modifier | modifier le code]

(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

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]