Роберт Тарьян
Роберт Тарьян | |
|---|---|
 | |
| Рожденный | Роберт Эндре Тарьян 30 апреля 1948 г. Помона , Калифорния , США |
| Альма-матер | Калифорнийский технологический институт ( BS ) Стэнфордский университет ( MS , PhD ) |
| Известный | Алгоритмы и структуры данных |
| Награды | Премия Пэрис Канеллакис (1999) Премия Тьюринга (1986) Премия Неванлинны (1982) |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Принстонский университет Нью-Йоркский университет Стэнфордский университет Калифорнийский университет, Беркли Корнелльский университет Microsoft Исследования Интертраст Технологии Хьюлетт-Паккард Компак НЭК Исследования Белл Лаборатории |
| Диссертация | Эффективный алгоритм планарности (1972) |
| Докторантура | Роберт В. Флойд |
| Другие научные консультанты | Дональд Кнут |
| Докторанты | |
| Веб-сайт | www |
Роберт Эндре Тарьян (родился 30 апреля 1948 года) — американский учёный-компьютерщик и математик . Он является первооткрывателем нескольких алгоритмов теории графов , в том числе его алгоритма сильно связанных компонентов , а также соавтором как деревьев расширения , так и куч Фибоначчи . Тарьян в настоящее время является Джеймса С. Макдоннелла заслуженным профессором компьютерных наук в Принстонском университете .
Личная жизнь и образование
[ редактировать ]Он родился в Помоне, Калифорния . Его отец, Джордж Тарьян (1912–1991), вырос в Венгрии. [1] был детским психиатром, специализирующимся на умственной отсталости, и руководил государственной больницей. [2] Роберта Тарьяна Младший брат Джеймс стал гроссмейстером по шахматам. [3] В детстве Роберт Тарьян читал много научной фантастики и хотел стать астрономом . Он заинтересовался математикой после прочтения Мартина Гарднера колонки о математических играх в журнале Scientific American . Серьезно увлекся математикой в восьмом классе благодаря «очень стимулирующей» учительнице. [4]
Пока он учился в старшей школе, Тарьян устроился на работу, где работал с сортировщиками перфокарт IBM. Впервые он работал с настоящими компьютерами во время изучения астрономии в рамках Летней научной программы в 1964 году. [2]
Тарьян получил степень бакалавра математики в Калифорнийском технологическом институте в 1969 году. В Стэнфордском университете он получил степень магистра компьютерных наук в 1971 году и степень доктора философии. получил степень бакалавра информатики (со специализацией по математике) в 1972 году. В Стэнфорде его курировал Роберт Флойд. [5] и Дональд Кнут , [6] оба выдающихся ученых-компьютерщика, и его доктор философии. диссертация была «Эффективный алгоритм планарности» . Тарьян выбрал информатику в качестве области своих интересов, потому что считал, что информатика — это способ заниматься математикой, который может иметь практическое значение. [7]
Сейчас Тарьян живет в Принстоне, штат Нью-Джерси, и в Силиконовой долине. Он женат на Найле Ризк. [8] У него три дочери: Алиса Тарьян, Софи Завацки и Максин Тарьян. [9]
Карьера в области информатики
[ редактировать ]Тарьян преподает в Принстонском университете с 1985 года. [7] Он также занимал академические должности в Корнельском университете (1972–73), Калифорнийском университете в Беркли (1973–1975), Стэнфордском университете (1974–1980) и Нью-Йоркском университете (1981–1985). Он также был научным сотрудником Исследовательского института NEC (1989–1997). [10] В апреле 2013 года он присоединился к Microsoft Research Silicon Valley в дополнение к должности в Принстоне. В октябре 2014 года он вернулся в Intertrust Technologies в качестве главного научного сотрудника.
Тарьян работал в AT&T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014 – настоящее время), Compaq (2002) и Hewlett Packard (2006–2013).
Алгоритмы и структуры данных
[ редактировать ]Тарьян известен своими новаторскими работами над алгоритмами теории графов и структурами данных. Некоторые из его известных алгоритмов включают автономный алгоритм наименьших общих предков Тарьяна , алгоритм сильно связанных компонентов Тарьяна и алгоритм поиска мостов Тарьяна , и он был одним из пяти соавторов медианы медиан с линейным временем алгоритма выбора . Хопкрофта – Тарьяна Алгоритм тестирования планарности был первым алгоритмом тестирования планарности с линейным временем. [11]
Тарьян также разработал важные структуры данных, такие как куча Фибоначчи (структура данных кучи, состоящая из леса деревьев) и дерево расширения (самонастраивающееся двоичное дерево поиска; изобретено совместно Тарьяном и Дэниелом Слитером ). Еще одним важным вкладом стал анализ структуры данных с непересекающимися множествами ; он был первым, кто доказал оптимальное время выполнения с использованием обратной функции Аккермана . [12]
Награды
[ редактировать ]Тарьян получил премию Тьюринга совместно с Джоном Хопкрофтом в 1986 году. В ссылке на награду говорится: [10] что это было:
За фундаментальные достижения в разработке и анализе алгоритмов и структур данных.
Тарьян также был избран членом ACM в 1994 году. В подписи к этой награде говорится: [13]
За выдающиеся достижения в разработке и анализе структур данных и алгоритмов.
Некоторые из других наград Тарьяна включают:
- Премия Неванлинны в области информатики (1983) [10] - первый получатель [14]
- Член Американской академии искусств и наук , избран в 1985 г. [15]
- Премия Национальной академии наук за исследовательские инициативы (1984 г.) [10]
- Член Национальной академии наук , избран в 1987 г. [16]
- Член Национальной инженерной академии , избран в 1988 г. [17]
- Член Американского философского общества , избран в 1990 г. [18]
- Премия Пэрис Канеллакис в области теории и практики, ACM (1999) [10]
- Премия выдающимся выпускникам Калифорнийского технологического института, Калифорнийский технологический институт (2010 г.) [19]
Избранные публикации
[ редактировать ]Статьи Тарьяна в совокупности цитировались более 94 000 раз. [20] Среди наиболее цитируемых:
- 1972: Алгоритмы поиска в глубину и линейные графы, Р. Тарьян, SIAM Journal on Computing 1 (2), 146–160 [21]
- 1987: Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети, М. Л. Фредман, Р. Э. Тарьян, Журнал ACM (JACM) 34 (3), 596–615. [22]
- 1983: Структуры данных и сетевые алгоритмы, Р.Э. Тарьян, Общество промышленной и прикладной математики. [23]
- 1988: Новый подход к проблеме максимального расхода, В. Гольдберг, Р. Э. Тарьян, Журнал ACM (JACM) 35 (4), 921–940. [24]
Патенты
[ редактировать ]Тарьян имеет как минимум 18 патентов США. [6] К ним относятся:
- Дж. Бентли, Д. Слиатор и Р.Э. Тарьян, патент США № 4,796,003, сжатие данных , 1989 г. [25]
- Н. Мишра, Р. Шрайбер и Р. Э. Тарьян, Патент США 7,818,272, Метод обнаружения кластеров объектов в произвольном неориентированном графе с использованием разницы между долей внутренних связей и максимальной долей связей внешнего объекта , 2010 г. [26]
- Б. Пинкас, С. Хабер, Р. Э. Тарьян и Т. Сандер, Патент США 8220036, Установление безопасного канала с пользователем-человеком , 2012 г. [27]
Примечания
[ редактировать ]- ^ «Еврейские лауреаты премии Тьюринга ACM AM» . jinfo.org .
- ↑ Перейти обратно: Перейти обратно: а б Шаша, Деннис Эллиотт; Лазер, Кэти А. (1998) [1995]. «Роберт Э. Тарьян: В поисках хорошей структуры». Они сошли с ума: жизнь и открытия 15 великих ученых-компьютерщиков . Коперник/Спрингер. стр. 102–119 . ISBN 978-0-387-97992-2 . ОСЛК 32240355 .
- ^ Мелвин, Шабсин (август 1984 г.). «Джордж Тарьян, доктор медицинских наук, сто двенадцатый президент, 1983–1984 годы». Американский журнал психиатрии . 141 (8): 931–934. дои : 10.1176/ajp.141.8.931 .
- ^ «Роберт Тарьян: Искусство алгоритма» . Хьюлетт-Паккард . Проверено 5 сентября 2010 г.
- ^ «Роберт Эндре Тарьян» . Проект математической генеалогии . Проверено 9 января 2008 г.
- ↑ Перейти обратно: Перейти обратно: а б Тарьян, Роберт Эндре (15 ноября 2019 г.). «Биографическая справка» (PDF) . Архивировано из оригинала (PDF) 23 ноября 2019 г. Проверено 23 ноября 2019 г.
- ↑ Перейти обратно: Перейти обратно: а б «Роберт Эндре Тарьян: Искусство алгоритма (интервью)» . Хьюлетт-Паккард. Сентябрь 2004 года . Проверено 9 января 2008 г.
- ^ «Найла Ризк и Роберт Тарьян» . Нью-Йорк Таймс . Июль 2013.
- ^ «Фотографии с симпозиума по случаю 60-летия Боба Тарджана» . ДИМАКС. Май 2008 года.
- ↑ Перейти обратно: Перейти обратно: а б с д и Кинг, В. «Роберт Э. Тарьян - лауреат премии А. М. Тьюринга» . АКМ . Проверено 19 января 2014 г.
- ^ Кочай, Уильям; Креер, Дональд Л. (2005). «Планарные графы». Графики, алгоритмы и оптимизация . Бока-Ратон: Чепмен и Холл/CRC. п. 312 . ISBN 978-1-58488-396-8 . OCLC 56319851 .
- ^ Тарьян, Роберт Э .; ван Леувен, Ян (1984). «Анализ наихудшего случая алгоритмов объединения множеств» . Журнал АКМ . 31 (2): 245–281. дои : 10.1145/62.2160 . S2CID 5363073 .
- ^ «Награда стипендиатов — Роберт Э. Тарджан» . АКМ . 25 сентября 1998 года . Проверено 18 ноября 2005 г.
- ^ «Лауреаты премии Рольфа Неванлинны» . Международный математический союз . Архивировано из оригинала 27 декабря 2008 г. Проверено 19 января 2014 г.
- ^ «Роберт Эндре Тарьян» . Американская академия искусств и наук . Проверено 15 июня 2020 г.
- ^ «Роберт Тарьян» . www.nasonline.org . Проверено 15 июня 2020 г.
- ^ «Доктор Роберт Э. Тарьян» . Сайт НАЭ . Проверено 15 июня 2020 г.
- ^ «История участников APS» . search.amphilsoc.org . Проверено 19 апреля 2022 г.
- ^ «Калифорнийский технологический институт называет пять выдающихся выпускников» (пресс-релиз). Калифорнийский технологический институт . 15 марта 2010 г. Архивировано из оригинала 10 октября 2010 г. Проверено 26 августа 2010 г.
- ^ «Страница Роберта Тарьяна в Google Scholar» . Google Академик . Проверено 6 марта 2023 г.
- ^ Тарьян, Роберт (1 июня 1972 г.). «Поиск в глубину и алгоритмы линейного графа» . SIAM Journal по вычислительной технике . 1 (2): 146–160. дои : 10.1137/0201010 . ISSN 0097-5397 . S2CID 16467262 .
- ^ Фредман, Майкл Л.; Тарьян, Роберт Эндре (1 июля 1987 г.). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Журнал АКМ . 34 (3): 596–615. дои : 10.1145/28869.28874 . ISSN 0004-5411 . S2CID 7904683 .
- ^ «Обратное дело» . Структуры данных и сетевые алгоритмы : 125–131. Январь 1983 г. doi : 10.1137/1.9781611970265.bm . ISBN 978-0-89871-187-5 .
- ^ Гольдберг, Эндрю В.; Тарьян, Роберт Э. (1 октября 1988 г.). «Новый подход к проблеме максимального потока» . Журнал АКМ . 35 (4): 921–940. дои : 10.1145/48014.61051 . ISSN 0004-5411 . S2CID 14492800 .
- ^ Бентли, Джон Л.; Слитор, Дэниел Д.К.; Тарьян, Роберт Э. (3 января 1989 г.). «Патент США 4796003 — Сжатие данных» .
- ^ Нина, Мишра; Шрайбер, Роберт Сэмюэл; Роберт Э., Тарьян (19 октября 2010 г.). «Патент США 7818272 — Способ обнаружения кластеров объектов в произвольном неориентированном графе с использованием разницы между долей внутренних связей и максимальной долей связей внешнего объекта» .
- ^ Пинкас, Биньямин; Хабер, Стюарт А.; Тарьян, Роберт Э.; Сандер, Томас (10 июля 2012 г.). «Патент США 8220036 — Установление безопасного канала с пользователем-человеком» .
Ссылки
[ редактировать ]- Тарьян, Роберт Э. (1983). Структуры данных и сетевые алгоритмы . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-187-5 . ОСЛК 10120539 .
- Тарьян, Роберт Э.; Полиа, Джордж; Вудс, Дональд Р. (1983). Заметки по вводной комбинаторике . Бостон: Биркхаузер. ISBN 978-0-8176-3170-3 . ОСЛК 10018128 .
- Записи OCLC для Роберта Э. Тарьяна
- Роберт Э. Тарьян на DBLP библиографическом сервере
Внешние ссылки
[ редактировать ]
- 1948 рождений
- Живые люди
- Члены Национальной академии наук США
- Американские ученые-компьютерщики
- Американские ученые-теоретики-компьютерщики
- Лауреаты премии Тьюринга
- Лауреаты премии Неванлинны
- Ученые из Bell Labs
- Выпускники Калифорнийского технологического института
- Выпускники инженерной школы Стэнфордского университета
- Преподаватели Принстонского университета
- Люди из Помоны, Калифорния
- Американские евреи 20-го века
- Американские евреи XXI века
- Члены Общества промышленной и прикладной математики
- Летняя научная программа
- Члены Национальной инженерной академии США
- Теоретики графов
- Члены Американского философского общества
- 1994 г. Члены Ассоциации вычислительной техники.