Juris Hartmanis

Article

August 18, 2022

Juris Hartmanis (5 juillet 1928 - 29 juillet 2022) était un informaticien et théoricien informatique américain d'origine lettone qui, avec Richard E. Stearns , a reçu le prix ACM Turing 1993 "en reconnaissance de leur article fondateur qui a jeté les bases de le domaine de la théorie de la complexité computationnelle ».

Vie et carrière

Hartmanis est né en Lettonie le 5 juillet 1928. Il était le fils de Mārtiņš Hartmanis, général de l'armée lettone et frère de la poétesse Astrid Ivask. Après que l'Union soviétique a occupé la Lettonie en 1940, Mārtiņš Hartmanis a été arrêté par les Soviétiques et est mort en prison. Plus tard dans la Seconde Guerre mondiale, la femme et les enfants de Mārtiņš Hartmanis ont quitté la Lettonie en 1944 en tant que réfugiés, craignant pour leur sécurité si l'Union soviétique reprenait la Lettonie. Ils ont d'abord déménagé en Allemagne, où Juris Hartmanis a obtenu l'équivalent d'une maîtrise en physique de l'Université de Marbourg. Il a ensuite déménagé aux États-Unis, où en 1951 il a obtenu une maîtrise en mathématiques appliquées à l'Université de Kansas City (maintenant connue sous le nom d'Université du Missouri-Kansas City) et en 1955 un doctorat. en mathématiques de Caltech sous la direction de Robert P. Dilworth. L'Université du Missouri-Kansas City lui a décerné un doctorat honorifique en lettres humaines en mai 1999. Après avoir enseigné les mathématiques à l'Université Cornell et à l'Ohio State University, Hartmanis a rejoint le General Electric Research Laboratory en 1958. Pendant son séjour à General Electric, il a développé de nombreux principes de la théorie de la complexité computationnelle. En 1965, il devient professeur à l'Université Cornell. Il a été l'un des fondateurs et le premier président de son département d'informatique (qui était l'un des premiers départements d'informatique au monde). Hartmanis a contribué aux efforts nationaux pour faire progresser l'informatique et l'ingénierie (CS&E) de plusieurs façons. Plus important encore, il a présidé l'étude du Conseil national de recherches qui a abouti à la publication de 1992 Computing the Future - A Broad Agenda for Computer Science and Engineering, qui a fait des recommandations basées sur ses priorités pour soutenir l'effort de base en CS&E, pour élargir le champ, et pour améliorer l'éducation de premier cycle en CS&E. Il a été directeur adjoint de la Direction de l'informatique et des sciences de l'information et de l'ingénierie (CISE) de la National Science Foundation (NSF) de 1996 à 1998. En 1989, Hartmanis a été élu membre de la National Academy of Engineering pour ses contributions fondamentales à la théorie de la complexité computationnelle et à la recherche et à l'enseignement en informatique. Il était membre de l'Association for Computing Machinery et de l'American Mathematical Society, également membre de la National Academy of Sciences. Il était également membre étranger de l'Académie des sciences de Lettonie, qui lui a décerné sa grande médaille en 2001 pour ses contributions à l'informatique. Hartmanis est décédé le 29 juillet 2022.

Complexité computationnelle : contributions fondamentales

En 1993, Hartmanis et R.E. Stearns a reçu le prix le plus élevé en informatique, le Turing Award. La citation se lit, "En reconnaissance de leur article fondateur qui a jeté les bases du domaine de la théorie de la complexité computationnelle." Leur papier défini la notion fondamentale d'une classe de complexité, une façon de classer les problèmes de calcul en fonction du temps nécessaire pour les résoudre. Ils ont ensuite prouvé un certain nombre de résultats fondamentaux tels que le Théorème de la hiérarchie temporelle. Dans sa propre conférence pour le prix Turing, Richard M. Karp fait remarquer que "[c]'est l'article de 1965 de Juris Hartmanis et Richard Stearns qui marque le début de l'ère moderne de théorie de la complexité. "Avec P.M. Lewis II, Hartmanis et Stearns ont également défini des classes de complexité basées sur l'utilisation de l'espace et prouvé le premier théorème de la hiérarchie spatiale. La même année, ils a également prouvé que chaque langage hors contexte a des propriétés déterministes complexité de l'espace (log n)2, qui contenait l'idée essentielle qui a conduit au théorème de Savitch sur la complexité de l'espace. Hartmanis a continué à faire signi