« Michael Rabin » : différence entre les versions

Biographie
Naissance	1er septembre 1931 (93 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	Université Harvard; Université de New York; California Institute of Technology; Technion; Institut de technologie du Massachusetts; Université Columbia; Université de Californie à Berkeley; École polytechnique fédérale de Zurich
Membre de	Académie américaine des sciences (1984); Royal Society (2007); Association for Computing Machinery (2021); Académie américaine des arts et des sciences; Académie des sciences; Société américaine de philosophie; Académie israélienne des sciences et lettres
Directeur de thèse	Alonzo Church
Distinctions	Prix Turing (1976); Liste détaillée Prix Turing (1976); Prix Harvey (1980); Conférence Gibbs (1985); Prix Israël (1995); Doctorat honoris causa de l'université Bordeaux-I (1995); Prix Paris-Kanellakis (2003); Prix EMET pour l'Art, la Science et la Culture (en) (2004); Gödel Lecturer (2004); Membre étranger de la Royal Society (2007); IACR Fellow (2009); Prix Dan-David (2010); ACM Fellow (2020); Prix Wolf de mathématiques; Prix Rothschild en sciences; Docteur honoris causa de l'Institut Weizmann

Navigation interactive dans l’historique

← Modification précédente

Contenu supprimé Contenu ajouté

VisuelWikicode

Intégrés

Dernière version du 21 février 2023 à 15:49

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (mars 2013).

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 Oser Rabin, né le 1^er septembre 1931 à 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, n^o 5,‎ septembre 1968, p. 1025–1029 (ISSN 0002-9904 et 1936-881X, lire en ligne, consulté le 19 septembre 2018)
↑ (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re é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

Liens externes

Notices d'autorité :
- VIAF
- ISNI
- BnF (données)
- IdRef
- Pays-Bas
- Israël
- Tchéquie
(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 :

[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, n^o 5,‎ septembre 1968, p. 1025–1029 (ISSN 0002-9904 et 1936-881X, lire en ligne, consulté le 19 septembre 2018)

[3] (en) Rajeev Motwani et Prabhakar Raghavan, Randomized Algorithms, Cambridge, New York et Melbourne, Cambridge University Press, 1995 (réimpr. 1997, 2000), 1^re éd., 476 p. (ISBN 978-0-521-47465-8, lire en ligne), chap. 9, p. 273

[1]

[2]

[3]

@@ Ligne 1 : / Ligne 1 : @@
-{{voir homonyme|Michael Rabin (violoniste)}}
+{{voir homonymes|Michael Rabin (violoniste)|Rabin (homonymie)}}
 {{Sources|date = mars 2013}}
+{{Infobox Biographie2}}
-[[Fichier:Michael O. Rabin.jpg|thumb|Michael Rabin]]
-'''Michael Oser Rabin''' (né en [[1931]] à [[Wrocław|Breslau]] en [[Allemagne]], maintenant [[Wrocław]] en [[Pologne]]) est un [[informaticien]] et un  [[logique mathématique|logicien]] ; il a été récipiendaire du [[prix Turing]], la récompense la plus prestigieuse en informatique.
+'''Michael Oser Rabin''', né le {{date de naissance|1 septembre 1931}} à [[Wrocław|Breslau]] en [[Allemagne]], maintenant [[Wrocław]] en [[Pologne]]) est un [[informaticien]] et un [[logique mathématique|logicien]] [[Israël|israélien]]. Il a été récipiendaire du [[prix Turing]], la récompense la plus prestigieuse en informatique.
-==Repères bibliographiques==
+== 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 :
-{{Citation|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<ref>Traduction libre de : {{en}} [http://amturing.acm.org/award_winners/rabin_9681074.cfm Citation du prix ACM Turing]</ref>.}}
+{{Citation|Pour leur article « {{Langue|en|Finite Automata and Their Decision Problem}} » présentant l'idée des [[Automate fini non déterministe|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<ref>Traduction libre de : {{en}} [http://amturing.acm.org/award_winners/rabin_9681074.cfm Citation du prix ACM Turing].</ref>.}}
 Les machines non déterministes sont devenues un concept clé dans la [[théorie de la complexité (informatique théorique)|théorie de la complexité]], en particulier avec la description des classes de complexité [[P (complexité)|P]] et [[NP (complexité)|NP]].
+== Travaux ==
-En [[1957]] et [[1958]], Rabin a démontré que divers problèmes de théorie de  [[Présentation d'un groupe|groupes]] sont indécidables (ce sont les premiers du genre après ceux de {{Lien|Sergei Adian}} en 1955).
+En [[1957]] et [[1958]], Rabin a démontré que divers problèmes de théorie de [[Présentation d'un groupe|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.
+En [[1969]], Rabin a démontré que l'arithmétique monadique du second ordre (avec ''k'' successeurs) est décidable<ref>{{Article|langue=EN|prénom1=Michael O.|nom1=Rabin|titre=Decidability of second-order theories and automata on infinite trees|périodique=Bulletin of the American Mathematical Society|volume=74|numéro=5|date=1968-09|issn=0002-9904|issn2=1936-881X|lire en ligne=https://projecteuclid.org/euclid.bams/1183529958|consulté le=2018-09-19|pages=1025–1029}}</ref>. 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 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 [[1975]], Rabin a été un pionnier des [[algorithme probabiliste|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]]<ref>
+{{Randomized Algorithms (Motwani et Raghavan)
+ |passage = 273
+ |chapitre= Geometric Algorithms and Linear Programming
+ | numéro chapitre = 9
+}}
+</ref>.
-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 en nombres premiers|factorisation d'un nombre entier]].
+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 en nombres premiers|factorisation d'un nombre entier]].
-En [[1981]], Rabin a inventé la technique du {{Lien|trad=Oblivious transfer|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 [[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 [[Algorithme de recherche de sous-chaîne|recherche de chaîne de caractères]], l'[[algorithme de Rabin-Karp]].
@@ Ligne 31 : / Ligne 37 : @@
 Les recherches actuelles de Rabin se concentrent sur la [[sécurité informatique|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==
+== 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 ==
 {{Traduction/Référence|en|Michael O. Rabin|29763372|type=note}}
-{{reflist}}
+{{références}}
 == Voir aussi ==
+{{Autres projets|commons=Category:Michael O. Rabin}}
-===Articles connexes===
+=== Articles connexes ===
 * [[Test de primalité de Miller-Rabin]]
 * [[Cryptosystème de Rabin]]
 * [[Algorithme de Rabin-Karp]]
-*{{Lien|trad=Oblivious transfer|Transfert inconscient}}
+* [[Transfert inconscient]]
-===Liens externes===
+=== Liens externes ===
+* {{Autorité}}
 * {{en}} [http://www.sis.pitt.edu/~mbsclass/hall_of_fame/rabin.html Description courte] dans le ''Information Science Hall of Fame ''à l'[[université de Pittsburgh]]
 * {{en}} [http://cri.haifa.ac.il/events/2005/graph/oblivious.htm The Past, Present and Future of Oblivious Transfer], workshop sur le transfert inconscient à l'[[université de Haïfa]], 2005
+* {{Bases recherche}}
-{{publications informatique |prénom=Michael |middle=O |nom=Rabin |initiale=R}}
-{{Palette|Lauréats du prix Turing}}
+{{Palette|Lauréats du prix Turing|Lauréats du prix Kanellakis}}
 {{Portail|cryptologie|sécurité informatique|informatique théorique}}
 {{DEFAULTSORT:Rabin, Michael}}
+[[Catégorie:Personnalité américaine de l'informatique]]
-[[Catégorie:Naissance en 1931]]
+[[Catégorie:Logicien israélien]]
-[[Catégorie:Naissance à Breslau]]
-[[Catégorie:Personnalité américaine en informatique]]
-[[Catégorie:Lauréat du prix Turing]]
 [[Catégorie:Universitaire israélien]]
 [[Catégorie:Personnalité en sécurité informatique]]
-[[Catégorie:Lauréat du prix Paris Kanellakis]]
-[[Catégorie:Membre de l'Académie israélienne des sciences et lettres]]
 [[Catégorie:Personnalité en informatique théorique]]
+[[Catégorie:Personnalité d'IBM]]
+[[Catégorie:Enseignant à l'École polytechnique fédérale de Zurich]]
+[[Catégorie:Étudiant de l'université hébraïque de Jérusalem]]
+[[Catégorie:Docteur de l'université de Princeton]]
+[[Catégorie:Professeur à l'université Harvard]]
+[[Catégorie:Professeur à l'université hébraïque de Jérusalem]]
+[[Catégorie:Professeur au Technion]]
+[[Catégorie:Docteur honoris causa de l'Institut Weizmann]]
+[[Catégorie:Lauréat du prix Turing]]
+[[Catégorie:Lauréat du prix Paris-Kanellakis]]
+[[Catégorie:Lauréat du prix Israël]]
+[[Catégorie:Lauréat du prix Dijkstra]]
+[[Catégorie:Lauréat du prix Harvey (Technion)]]
+[[Catégorie:Lauréat du prix Dan-David]]
+[[Catégorie:Gödel Lecturer]]
+[[Catégorie:Tarski Lecturer]]
+[[Catégorie:Membre de l'Académie israélienne des sciences et lettres]]
+[[Catégorie:Membre de l'Académie américaine des arts et des sciences]]
+[[Catégorie:Membre de la Société américaine de philosophie]]
+[[Catégorie:Membre de l'Académie nationale des sciences]]
+[[Catégorie:Membre de l'Académie des sciences (France)]]
+[[Catégorie:Membre de la Royal Society]]
+[[Catégorie:Naissance en septembre 1931]]
+[[Catégorie:Naissance à Breslau]]