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