Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.
Concept
Michael Rabin
Résumé
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.
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 :
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 1955).
En 1969, Rabin a démontré que l'arithmétique monadique du second ordre (avec k successeurs) est décidable. 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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.