Юрис Хартманис -Juris Hartmanis

Юрис Хартманис
Юрис Хартманис (2002).jpg
Родился ( 1928-07-05 )5 июля 1928 г.
Рига , Латвия
Умер 29 июля 2022 г. (2022-07-29)(94 года)
Альма-матер
Награды Премия Тьюринга (1993)
Научная карьера
Поля Информатика
Учреждения
Докторантура Роберт П. Дилворт
Докторанты Аллан Бородин (1969), Декстер Козен (1976), Нил Иммерман (1980), Джин-И Кай (1986)

Юрис Хартманис (5 июля 1928 г. - 29 июля 2022 г.) был американским ученым-компьютерщиком и теоретиком вычислений латвийского происхождения , который вместе с Ричардом Э. Стернсом получил в 1993 году премию Тьюринга ACM «в знак признания их основополагающей статьи, которая заложила основы для области теории вычислительной сложности ».

Жизнь и карьера

Хартманис родился в Латвии 5 июля 1928 года. Он был сыном Мартиньша Хартманиса  [ lv ] , генерала латышской армии , и братом поэтессы Астрид Иваск . После того, как Советский Союз оккупировал Латвию в 1940 году, Мартиньш Хартманис был арестован Советским Союзом и умер в тюрьме. Позже во время Второй мировой войны жена и дети Мартиньша Хартманиса покинули Латвию в 1944 году как беженцы, опасаясь за свою безопасность, если Советский Союз снова захватит Латвию.

Сначала они переехали в Германию , где Юрис Хартманис получил эквивалент степени магистра физики в Марбургском университете . Затем он переехал в Соединенные Штаты , где в 1951 году получил степень магистра прикладной математики в Университете Канзас-Сити (ныне известный как Университет Миссури-Канзас-Сити ), а в 1955 году — степень доктора философии. по математике в Калифорнийском технологическом институте под руководством Роберта П. Дилворта . Университет Миссури-Канзас-Сити удостоил его звания почетного доктора гуманитарных наук в мае 1999 года. После преподавания математики в Корнелльском университете и Университете штата Огайо Хартманис присоединился к исследовательской лаборатории General Electric в 1958 году. Работая в General Electric, он разработал множество принципов. теории вычислительной сложности. В 1965 году он стал профессором Корнельского университета. Он был одним из основателей и первым заведующим кафедрой информатики (одной из первых кафедр информатики в мире).

Хартманис во многом способствовал национальным усилиям по развитию компьютерных наук и инженерии (CS&E). Что наиболее важно, он возглавлял исследование Национального исследовательского совета , результатом которого стала публикация 1992 года «Вычисления будущего — широкая повестка дня для компьютерных наук и инженерии» , в которой были даны рекомендации, основанные на его приоритетах, для поддержки основных усилий в области CS&E, для расширения области и улучшить студенческое образование в области CS&E. Он был помощником директора Управления компьютерных и информационных наук и инженерии (CISE) Национального научного фонда (NSF) с 1996 по 1998 год.

В 1989 году Хартманис был избран членом Национальной инженерной академии за фундаментальный вклад в теорию вычислительной сложности, а также в исследования и образование в области вычислительной техники. Он был членом Ассоциации вычислительной техники и Американского математического общества , а также членом Национальной академии наук . Он также был иностранным членом Латвийской академии наук , которая наградила его Большой медалью  [ lv ] в 2001 году за его вклад в информатику.

Вместе с RE Stearns Хартманис получил в 1993 году премию Тьюринга за статью, в которой они представили классы временной сложности TIME(f(n)) и доказали теорему об иерархии времени . В другой статье Хартманиса 1977 года вместе с Леонардом Берманом была представлена ​​​​до сих пор нерешенная гипотеза Бермана-Хартманиса о том , что все NP-полные языки изоморфны в полиномиальном времени.

Хартманис умер 29 июля 2022 года. У него остались трое детей Ренета, Мартин и Одри.

Награды

Избранные публикации

Книги
  • Теория алгебраической структуры последовательных машин, 1966 г. (совместно с RE Stearns )
  • Возможные вычисления и доказуемые свойства сложности 1 978
  • Теория вычислительной сложности (ред.) 1989 г.
  • Вычисления будущего: более широкая повестка дня в области компьютерных наук и инженерии (ред.) 1992 г. (совместно с Гербертом Лином)
Избранные статьи
  • «Вычислительная сложность рекурсивных последовательностей» 1964 г. (совместно с RE Stearns )
  • «Классификации вычислений по времени и требованиям к памяти», 1965 г. (совместно с П. М. Льюисом и Р. Е. Стернсом )
  • «Иерархии вычислений с ограниченным объемом памяти» 1965 г. (совместно с П. М. Льюисом и Р. Е. Стернсом )
  • «О вычислительной сложности алгоритмов» 1965 г. (совместно с Р.Э. Стернсом )
  • Границы памяти для распознавания контекстно-свободных и контекстно-зависимых языков 1965 г. (совместно с PM Lewis и RE Stearns )
  • «Об изоморфизмах и плотности NP и других полных множеств» 1977 г. (совместно с Л. Берманом)
  • «Наблюдения о развитии теоретической информатики» 1981 г.

Интервью

Юрис Хартманис давал интервью четыре раза. Видео доступны для двух из них. Самый далеко идущий принадлежит Уильяму Эспрэю.

  • Уильям Эспрей берет интервью у Хартманиса для интервью ACM Oral History, 2009 г.
  • Дэвид Грайс берет интервью у Хартманиса для коллекции Cornell ecommons, 2010 г.
  • Лен Шустек берет интервью у Хартманиса в статье в CACM , 2015 г.
  • Дэвид Грайс берет интервью у Хартманиса как лауреата премии ACM Turing Award, 2018 г.

использованная литература

внешние ссылки