Le prix Turing 1993 a été décerné à Richard E. Stearns et Juris Hartmanis pour un article séminal ayant créé la structure fondamentale de la théorie de la complexité computationnelle. Cette recherche a établi comment la difficulté d'un problème évolue avec la taille de ses données d'entrée, un concept qui demeure essentiel à l'informatique moderne et à l'efficacité algorithmique aujourd'hui.
Fondations académiques et premières recherches
Né en 1936 à Caldwell, Richard Edwin Stearns a commencé son parcours académique au Carleton College, où il a obtenu une licence en mathématiques en 1958. Il a poursuivi ses études à l'Université de Princeton, obtenant un doctorat en mathématiques en 1961. Sa thèse de doctorat, supervisée par Harold W. Kuhn, portait sur les mathématiques des jeux coopératifs à trois personnes sans paiements latéraux.
Contributions à la théorie computationnelle
Durant son mandat chez General Electric de 1961 à 1978, Stearns a produit des travaux influents sur les propriétés formelles des systèmes informatiques. En 1965, il a coécrit un article sur la complexité computationnelle des algorithmes, introduisant le théorème de hiérarchie temporelle. Son étude de 1967 sur les machines à pile a établi la décidabilité de la question de savoir si les automates à pile déterministes acceptent les langages réguliers, tandis que sa collaboration de 1968 avec P.M. Lewis II a introduit les analyseurs LL, un développement qui a façonné les méthodologies ultérieures de conception de compilateurs.
Carrière académique et reconnaissance professionnelle
Stearns a été enseignant et chercheur à l'Université d'État de New York à Albany entre 1978 et 2000, occupant finalement le titre de Distinguished Professor. Tout au long de sa carrière, il a été affilié à l'Université de New York et membre de l'Association for Computing Machinery. Au-delà du prix Turing de 1993, sa carrière a été marquée par son élection en tant qu'ACM Fellow en 1994 et l'obtention du prix Frederick W. Lanchester en 1995. Stearns est décédé le 29 août 2026 à l'âge de 90 ans.
Vingt questions, huit minutes au chronomètre et un centile mesuré face à tous ceux qui l’ont passé. Sans inscription.
Passer le test de QI →Faits marquants
- Naissance : 1936, Caldwell - Décès : 29 août 2026 - Éducation : Carleton College, Université de Princeton - Prix majeur : Prix Turing (1993) - Affiliation professionnelle : General Electric (1961-1978) - Carrière académique : Université d'État de New York à Albany (1978-2000) - Domaine de recherche : Théorie de la complexité computationnelle - Reconnaissance : ACM Fellow (1994)
Questions fréquentes
### Pour quoi Richard E. Stearns est-il connu ?
Il est reconnu pour avoir établi les fondements de la théorie de la complexité computationnelle, notamment grâce à ses travaux collaboratifs sur le théorème de hiérarchie temporelle.
### Où Stearns a-t-il enseigné ?
Il était professeur distingué à l'Université d'État de New York à Albany et entretenait des liens académiques avec l'Université de New York.
