Jump to content

Юрис Хартманис

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

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

Жизнь и карьера [ править ]

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

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

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

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

Хартманис умер 29 июля 2022 года. [23] [24] [25]

Вычислительная сложность фундаментальный вклад :

В 1993 году Хартманис и Р.Э. Стернс получили высшая премия в области информатики — премия Тьюринга . В цитате говорится:«В знак признания их основополагающей работы, которая заложила основы этой областитеории сложности вычислений ». [26] Их статья [13] определил основополагающее понятие класса сложности , способаклассифицировать вычислительные задачи по времени, необходимому для их решения.Далее они доказали ряд фундаментальных результатов, таких как Теорема об иерархии времени . В своей лекции на премию Тьюринга Ричард М. Карп отмечает, что «[это] статья 1965 года Юриса Хартманиса и Ричарда Стернса, которая знаменует начало современной эрытеория сложности». [27]

Вместе с премьер-министром Льюисом II Хартманис и Стернс также определили классы сложности, основанные на использовании пространства, и доказали, чтопервая теорема о пространственной иерархии. [12] В том же году они также доказал [28] что каждый контекстно-свободный язык имеет детерминированныйпространственная сложность (log n) 2 , который содержал основную идею, которая привелак теореме Савича о пространственной сложности.

Хартманис продолжал вносить значительный вклад в область вычислительной сложности на протяжении десятилетий. Вместе с Леонардом Берманом он доказал, что все естественные NP-полные языки изоморфны в полиномиальном времени. [29] и предположилчто это справедливо для всех NP-полных множеств. [30] Хотя сама гипотеза остается открытой, она привела кбольшое количество исследований структуры NP-полных множеств, кульминацией которых сталов теореме Махани о несуществовании разреженных NP-полных множеств. [31] [32] [33] [34] Он и его соавторы также определил булеву иерархию . [35] [36]

Статья Хартманиса 1981 года [14] дает личный отчет о разработках в этой области и теории автоматов и обсуждаетосновные убеждения и философия, которыми руководствовались его исследования. Книганаписанное в честь его 60-летия, [37] в частности, глава Стернса, [38] является ценным ресурсом по вычислительной сложности.

В конце 1980-х годов экспозиция Хартманиса [39] о недавно обнаруженном письме от 20 марта 1956 г.от Гёделя до фон Неймана принесли новое пониманиев раннюю историю вычислительной сложности до его знаковой статьи со Стернсом,касаясь взаимодействий между Тьюрингом , Гёделем , Черч , Пост и Клини .Гёдель в этом письме первым поставил под вопрос, существует ли проблема, эквивалентная NP-полной задаче.проблема может быть решена за квадратичное или линейное время, предвещая P = NP? вопрос .

Награды [ править ]

Избранные публикации [ править ]

Книги
  • Алгебраическая структурная теория последовательных машин [50] 1966 (с Р.Э. Стернсом )
  • Возможные вычисления и доказуемые свойства сложности [51] 1978
  • Теория сложности вычислений (ред.) [52] 1989
  • Вычисления будущего: более широкая повестка дня в области информатики и техники (под ред.) [53] 1992 (с Гербертом Лином)
Избранные статьи
  • «Вычислительная сложность рекурсивных последовательностей» [10] 1964 (с Р.Э. Стернсом)
  • «Классификации вычислений по времени и требованиям к памяти» [11] 1965 (с премьер-министром Льюисом и Р.Э. Стернсом)
  • «Иерархии вычислений с ограниченной памятью» [12] 1965 (с премьер-министром Льюисом и Р.Э. Стернсом)
  • «О вычислительной сложности алгоритмов» [13] 1965 (с Р.Э. Стернсом)
  • Границы памяти для распознавания контекстно-свободных и контекстно-зависимых языков [28] 1965 (с премьер-министром Льюисом и Р.Э. Стернсом)
  • «Об изоморфизмах и плотности NP и других полных множеств» [29] 1977 (совместно с Л. Берманом)
  • «Наблюдения о развитии теоретической информатики» [14] 1981
  • «Гедель, фон Нейман и проблема P =? NP» [39] 1989

Интервью [ править ]

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

Ссылки [ править ]

  1. ^ «Юрис Хартманис» . mathgenealogy.org . Проект математической генеалогии . Проверено 4 августа 2022 г.
  2. ^ Селман, Алан Л. , изд. (1990). Ретроспектива теории сложности: в честь Юриса Хартманиса по случаю его шестидесятилетия, 5 июля 1988 г. Нью-Йорк, штат Нью-Йорк: Springer New York. дои : 10.1007/978-1-4612-4478-3 . ISBN  978-1-4612-4478-3 . S2CID   31789744 . Проверено 4 августа 2022 г.
  3. ^ В балтийских языках собственные имена не являются лексическими константами, а имеют разные грамматические формы. Хартманис следует понимать как Хартман-is, при этом Хартман является основой собственного имени, тогда как суффикс -is указывает на грамматическую форму мужского рода в латышском языке. Подобным образом, например, философ Кант на литовском языке известен как Кант .
  4. Перейти обратно: Перейти обратно: а б Хартманис, Юрис (26 июля 2009 г.). «Интервью доктора Юриса Хартманиса» (текст). Беседовал Уильям Эспрей. Итака, Нью-Йорк: Интервью ACM Oral History. дои : 10.1145/1141880.1775727 .
  5. Перейти обратно: Перейти обратно: а б Хартманис, Юрис (17 мая 2018 г.). «Юрис Хартманис, лауреат премии Тьюринга ACM 1993 года» (видео). Беседовал Дэвид Грайс . Итака, Нью-Йорк: ACM .
  6. ^ В двух интервью [4] [5] цитируется в разделе #Интервью , Хартманис подробно рассказывает об этом периоде своей жизни, когда его отцу было передано поместье Лестене; русские оккупировали Латвию, забрали его отца и конфисковали Лестене; немцы снова захватили власть и вернули часть Лестене его семье; и семья уехала из Латвии в Германию до того, как русские снова вторглись в Латвию.
  7. ^ «Дань Астрид Иваск: Литературный свет» . Мировая литература сегодня . 2 апреля 2015 года . Проверено 4 августа 2022 г.
  8. ^ Хартманис, Юрис (1955). Некоторые теоремы вложения для решеток (кандидатская диссертация). Калифорнийский технологический институт . дои : 10.7907/40KS-0T27 .
  9. Перейти обратно: Перейти обратно: а б «Почетные степени Университета Миссури» . Университет Миссури .
  10. Перейти обратно: Перейти обратно: а б —; Стернс, Р.Э. (11 ноября 1964 г.). Вычислительная сложность рекурсивных последовательностей . 5-я Энн. Симп. по теории коммутационных цепей и логическому проектированию. Принстон, Нью-Джерси: IEEE. стр. 82–90. дои : 10.1109/SWCT.1964.6 .
  11. Перейти обратно: Перейти обратно: а б —; Льюис, премьер-министр; Стернс, RE (24 мая 1963 г.). Уэйн А. Каленич (ред.). Классификации вычислений по времени и требованиям к памяти . Учеб. Конгресс ИФИП 65. Нью-Йорк: Spartan Books, Inc., Вашингтон, округ Колумбия, стр. 31–35. дои : 10.2307/2272795 . JSTOR   2272795 .
  12. Перейти обратно: Перейти обратно: а б с —; Льюис, премьер-министр; Стернс, Р.Э. (6 октября 1965 г.). Иерархии вычислений с ограниченной памятью . FOCS 65: Учеб. Шестая Анна. Теория коммутационных схем Symp и логическое проектирование. Нью-Йорк: IEEE . стр. 179–190. дои : 10.1109/FOCS.1965.11 .
  13. Перейти обратно: Перейти обратно: а б с —; Стернс, RE (1965). «О вычислительной сложности алгоритмов» . Труды Американского математического общества . 117 : 285–306. дои : 10.2307/1994208 . JSTOR   1994208 . МР   0170805 .
  14. Перейти обратно: Перейти обратно: а б с - (1981), «Наблюдения за развитием теоретической информатики», IEEE Annals of the History of Computing , 3 (1): 42–51, doi : 10.1109/MAHC.1981.10005 , hdl : 1813/6244 , ISSN   1058- 6180
  15. ^ В этих ранних статьях были разработаны многие принципы теории сложности вычислений. [10] [11] [12] [13] Обзорная статья Хартманиса 1981 года содержит обширную информацию о работах в области теории сложности вычислений. [14]
  16. ^ Университет Пердью создал первый факультет компьютерных наук в 1962 году. «История кафедры» . Корнелл открыл свой отдел компьютерной техники в 1965 году. «Хронология отдела CS» . как и Стэнфорд, «Хронология отдела CS» . , Карнеги-Меллон, «История кафедры КС» . и несколько других.
  17. ^ Хартманис, Юрис; Лин, Герберт, ред. (1992). Вычисления будущего: более широкая повестка дня в области информатики и техники . Вашингтон, округ Колумбия: Издательство национальных академий . п. 288. дои : 10.17226/1982 . ISBN  978-0-309-04740-1 .
  18. ^ «Юрис Хартманис возглавит дирекцию NSF по CISE» . НФС . 5 сентября 1996 года . Проверено 2 августа 2022 г.
  19. Перейти обратно: Перейти обратно: а б Список членов Американского математического общества , получен 19 января 2013 г.
  20. Избраны члены Национальной академии наук и иностранные сотрудники. Архивировано 27 мая 2013 г., в Wayback Machine , Национальная академия наук , 30 апреля 2013 г.
  21. Перейти обратно: Перейти обратно: а б «Иностранные участники» . Латвийская академия наук . 1990 . Проверено 30 июля 2022 г.
  22. Перейти обратно: Перейти обратно: а б «Большая медаль» [Большая медаль]. www.lza.lv (на латышском языке). Латвийская академия наук . Архивировано из оригинала 6 января 2022 года . Проверено 4 августа 2022 г. 2001 ... Юрис Хартманис — за выдающийся вклад в развитие информатики. [2001 ... Юрис Хартманис — за выдающийся вклад в развитие информатики.]
  23. ^ Синь Чжи Юань [Синь Чжи Юань] (31 июля 2022 г.) «Лауреат премии Тьюринга и основатель теории «вычислительной сложности» Юрис Хартманис скончался в возрасте 94 лет» [лауреат премии Тьюринга и основатель теории «вычислительной сложности»]. , Юрис Хартманис, умер в возрасте 94 лет] . Sinafinance.sina.com.cn ( Проверено 4 августа 2022 г. ) .
  24. ^ Уолдрон, Патрисия (4 августа 2022 г.). «Юрис Хартманис, первый заведующий кафедрой КС, умер в возрасте 94 лет» . Корнеллские хроники . Проверено 5 августа 2022 г.
  25. ^ Гарфинкель, Самсон; Спаффорд, Юджин Х. (октябрь 2022 г.). «Памяти: Юрис Хартманис 1928–2022» . САКМ . 65 (10): 14–15. дои : 10.1145/3559705 .
  26. Перейти обратно: Перейти обратно: а б «Премия Тьюринга» . АКМ . 1993 год . Проверено 30 июля 2022 г.
  27. См. стр. 103 его лекции: Карп, Ричард М. (февраль 1986 г.). «Комбинаторика, сложность и случайность» . Коммуникации АКМ . 29 (2): 98–109. дои : 10.1145/5657.5658 . ISSN   0001-0782 .
  28. Перейти обратно: Перейти обратно: а б Льюис, премьер-министр; Стернс, RE ; - (6 октября 1965 г.). Границы памяти для распознавания контекстно-свободных и контекстно-зависимых языков . FOCS 65: Учеб. Шестая Анна. Теория коммутационных схем Symp и логическое проектирование. Анн-Арбор, Мичиган: IEEE. стр. 191–202. дои : 10.1109/FOCS.1965.14 .
  29. Перейти обратно: Перейти обратно: а б Берман, Л.; — (1977). «Об изоморфизмах и плотности NP и других полных множеств» (PDF) . SIAM Journal по вычислительной технике . 6 (2): 305–322. дои : 10.1137/0206023 . hdl : 1813/7101 . МР   0455536 .
  30. ^ Гипотеза Бермана-Хартманиса
  31. ^ Махани, Стивен Р. (октябрь 1982 г.). «Разреженные полные наборы для NP: решение гипотезы Бермана и Хартманиса». Журнал компьютерных и системных наук . 25 (2): 130–143. дои : 10.1016/0022-0000(82)90002-2 . hdl : 1813/6257 .
  32. ^ Цай, Джин-И; Сивакумар, Д. (апрель 1999 г.), «Разреженные жесткие множества для P: разрешение гипотезы Хартманиса», Journal of Computer and System Sciences , 58 (2): 280–296, doi : 10.1006/jcss.1998.1615
  33. ^ Редкий язык
  34. ^ Теорема Махани
  35. ^ Цай, Джин-И; Гундерманн, Томас; —; Хемачандра, Лейн А.; Сьюэлсон, Вивиан; Вагнер, Клаус; Вексунг, Герд (декабрь 1988 г.), «Булева иерархия I: Структурные свойства», SIAM Journal on Computing , 17 (6): 1232–1252, doi : 10.1137/0217078
  36. ^ Цай, Джин-И; Гундерманн, Томас; —; Хемачандра, Лейн А.; Сьюэлсон, Вивиан; Вагнер, Клаус; Вексунг, Герд (февраль 1989 г.), «Булева иерархия II: Приложения», SIAM Journal on Computing , 18 (1): 95–111, doi : 10.1137/0218007
  37. ^ Селман, Алан Л. , изд. (1990). Ретроспектива теории сложности . Спрингер Нью-Йорк, штат Нью-Йорк. дои : 10.1007/978-1-4612-4478-3 . ISBN  978-1-4612-8793-3 . S2CID   31789744 .
  38. ^ Стернс, RE (1990). «Юрис Хартманис: Начало вычислительной сложности». В Селмане, Алан Л. (ред.). Ретроспектива теории сложности . Спрингер Нью-Йорк, штат Нью-Йорк. дои : 10.1007/978-1-4612-4478-3 . ISBN  978-1-4612-8793-3 . S2CID   31789744 .
  39. Перейти обратно: Перейти обратно: а б Хартманис, Юрис (1989). «Гедель, фон Нейман и проблема P =? NP» . Бюллетень Европейской ассоциации теоретической информатики . 38 : 101–107.
  40. ^ «Товарищи» . Американская ассоциация содействия развитию науки . 1981 год . Проверено 30 июля 2022 г.
  41. ^ «Веб-сайт НАЭ – доктор Юрис Хартманис» . Национальная инженерная академия .
  42. ^ «Члены» . Американская академия искусств и наук . 1992 год . Проверено 30 июля 2022 г.
  43. ^ «Фонд Александра фон Гумбольдта, Юрис Хартманис» . Фонд Александра фон Гумбольдта . 1993.
  44. ^ «Стипендиаты ACM» . АКМ . 1994 . Проверено 30 июля 2022 г.
  45. ^ «Юрис Хартманис: научный сотрудник ACM» . 1994 . Проверено 9 июля 2022 г.
  46. ^ «Награда за выдающиеся заслуги» . Ассоциация компьютерных исследований . КРА . 16 января 2015 года . Проверено 30 июля 2022 г.
  47. ^ «Награда ACM за выдающиеся заслуги» . АКМ . 2013 . Проверено 30 июля 2022 г.
  48. ^ «Юрис Хартманис: награда за выдающиеся заслуги» . 2013 . Проверено 30 июля 2022 г.
  49. ^ «Почетный член» . Национальная академия наук (НАН) . Проверено 31 июля 2022 г.
  50. ^ —; Ричард Э., Стернс (1966). Алгебраическая структурная теория последовательных машин . Энглвуд Клиффс, Нью-Джерси: Прентис-Холл. п. 211. ИСБН  0130222771 .
  51. ^ — (1978). Возможные вычисления и доказуемые свойства сложности . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики (SIAM) . п. 62. ИСБН  978-0-898710-27-4 .
  52. ^ -, ред. (1989). Теория сложности вычислений . АМС . п. 128. ИСБН  978-0-8218-0131-4 .
  53. ^ —; Лин, Герберт, ред. (1992). Вычисления будущего: более широкая повестка дня в области информатики и техники . Вашингтон, округ Колумбия: Издательство национальных академий . п. 288. дои : 10.17226/1982 . ISBN  978-0-309-04740-1 .
  54. ^ Хартманис, Юрис (31 марта 2010 г.). «Разговор с Юрисом Хартманисом» (видео). Беседовал Дэвид Грайс . Итака, Нью-Йорк: Интернет-первое университетское издательство.
  55. ^ Шустек, Лен (2015). «Интервью с Юрисом Хартманисом» . САКМ . 58 (4): 33–37. дои : 10.1145/2736346 . S2CID   35051248 .

Внешние ссылки [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: cea38e61b55c6addfd68d12e4cda6531__1714965840
URL1:https://arc.ask3.ru/arc/aa/ce/31/cea38e61b55c6addfd68d12e4cda6531.html
Заголовок, (Title) документа по адресу, URL1:
Juris Hartmanis - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)