Juris Hartmanis

Article

August 18, 2022

Juris Hartmanis (5 lipca 1928 – 29 lipca 2022) był urodzonym na Łotwie amerykańskim informatykiem i teoretykiem obliczeń, który wraz z Richardem E. Stearnsem otrzymał nagrodę ACM Turinga 1993 „w uznaniu ich przełomowego artykułu, który ustanowił podwaliny dla dziedzinie teorii złożoności obliczeniowej”.

Życie i kariera

Hartmanis urodził się na Łotwie 5 lipca 1928 r. Był synem generała armii łotewskiej Mārtiņša Hartmanisa i bratem poetki Astrid Ivask. Po zajęciu Łotwy przez Związek Radziecki w 1940 roku Mārtiņš Hartmanis został aresztowany przez Sowietów i zmarł w więzieniu. Później, podczas II wojny światowej, żona i dzieci Mārtiņša Hartmanisa opuściły Łotwę w 1944 roku jako uchodźcy, obawiając się o swoje bezpieczeństwo, gdyby Związek Radziecki ponownie przejął Łotwę. Najpierw przenieśli się do Niemiec, gdzie Juris Hartmanis otrzymał tytuł magistra w fizyka z Uniwersytetu w Marburgu. Następnie przeniósł się do Stanów Zjednoczonych, gdzie w 1951 roku uzyskał tytuł magistra matematyki stosowanej na Uniwersytecie Kansas City (obecnie znany jako University of Missouri–Kansas City), a w 1955 roku doktorat. w matematyce z Caltech pod kierunkiem Roberta P. Dilwortha. University of Missouri-Kansas City uhonorował go tytułem doktora honoris causa Humane Letters w maju 1999 roku. Po nauczaniu matematyki na Cornell University i Ohio State University, Hartmanis dołączył do General Electric Research Laboratory w 1958. W General Electric opracował wiele zasad teorii złożoności obliczeniowej. W 1965 został profesorem na Cornell University. Był jednym z założycieli i pierwszym przewodniczącym wydziału informatyki (który był jednym z pierwszych wydziałów informatyki na świecie). Hartmanis na wiele sposobów przyczynił się do krajowych wysiłków na rzecz rozwoju informatyki i inżynierii (CS&E). Co najważniejsze, przewodniczył badaniu National Research Council, które zaowocowało publikacją Computing the Future – A Broad Agenda for Computer Science and Engineering z 1992 roku, w której sformułowano zalecenia oparte na jej priorytetach, aby podtrzymać podstawowe wysiłki w zakresie CS&E, aby poszerzyć tę dziedzinę oraz poprawić edukację licencjacką w CS&E. Był zastępcą dyrektora Dyrekcji ds. Informatyki i Inżynierii (CISE) Narodowej Fundacji Nauki (NSF) w latach 1996-1998. W 1989 roku Hartmanis został wybrany członkiem Narodowej Akademii Inżynierii za fundamentalny wkład w teorię złożoności obliczeniowej oraz badania i edukację w dziedzinie informatyki. Był członkiem Association for Computing Machinery i American Mathematical Society, a także członkiem National Academy of Sciences. Był także zagranicznym członkiem Łotewskiej Akademii Nauk, która w 2001 roku przyznała mu Wielki Medal za zasługi dla informatyki. Hartmanis zmarł 29 lipca 2022 roku.

Złożoność obliczeniowa: wkład podstawowy

W 1993 roku Hartmanis i R.E. Otrzymano Stearns najwyższa nagroda w dziedzinie informatyki, nagroda Turinga. Cytat brzmi: „W uznaniu ich przełomowej pracy, która położyła podwaliny pod tę dziedzinę” teorii złożoności obliczeniowej”. Ich papier zdefiniował podstawowe pojęcie klasy złożoności, sposób na klasyfikowanie problemów obliczeniowych według czasu potrzebnego do ich rozwiązania. Następnie udowodnili szereg fundamentalnych wyników, takich jak Twierdzenie o hierarchii czasu. W swoim własnym wykładzie o nagrodzie Turinga, Richard M. Karp zauważa, że ​​„jest to artykuł Jurisa Hartmanisa i Richarda Stearnsa z 1965 roku, który wyznacza początek współczesnej ery teorię złożoności. Wraz z PM Lewis II Hartmanis i Stearns zdefiniowali również klasy złożoności w oparciu o wykorzystanie przestrzeni i udowodnili pierwsze twierdzenie o hierarchii przestrzeni. W tym samym roku oni udowodnił również, że każdy język bezkontekstowy ma charakter deterministyczny złożoność przestrzenna (log n)2, która zawierała zasadniczą ideę prowadzącą do twierdzenia Savitcha o złożoności przestrzeni. Hartmanis nadal czynił znaczące