Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Роберт Эндре Тарджан
Боб Тарджан.jpg
Родившийся( 1948-04-30 )30 апреля 1948 г. (72 года)
Помона , Калифорния
ГражданствоАмериканец
Альма-матерКалифорнийский технологический институт ( BS )
Стэнфордский университет ( MS , PhD )
ИзвестенАлгоритмы и структуры данных
НаградыПремия Пэрис Канеллакис (1999)
Премия Тьюринга (1986)
Премия Неванлинны (1982)
Научная карьера
ПоляИнформатика
УчрежденияПринстонский университет
Нью-Йоркский университет
Стэнфордский университет
Калифорнийский университет, Беркли
Корнеллский университет
Microsoft Research
Intertrust Technologies
Hewlett-Packard
Compaq
NEC Research
Bell Labs
ТезисЭффективный алгоритм планарности  (1972)
ДокторантРоберт В. Флойд
Другие научные консультантыДональд Кнут
Докторанты
Интернет сайтwww .cs .princeton .edu / ~ ret /

Роберт Эндре Тарджан (родился 30 апреля 1948 г.) - американский ученый-компьютерщик и математик . Он является первооткрывателем нескольких алгоритмов графов , в том числе автономного алгоритма наименьших общих предков Тарьяна , и соавтором как растянутых деревьев, так и куч Фибоначчи . В настоящее время Тарджан является заслуженным профессором компьютерных наук в Принстонском университете имени Джеймса С. Макдоннелла и главным научным сотрудником Intertrust Technologies Corporation . [1]

Ранняя жизнь и образование [ править ]

Он родился в Помоне , Калифорния . Его отец был детским психиатром, специализирующимся на умственной отсталости, и руководил государственной больницей. [2] В детстве Тарджан читал много научной фантастики и хотел стать астрономом . Он заинтересовался математикой после чтения колонки Мартина Гарднера о математических играх в Scientific American . Он серьезно увлекся математикой в ​​восьмом классе благодаря «очень стимулирующему» учителю. [3]

В старших классах школы Тарджан устроился на работу, где работал подборщиком перфокарт IBM. Впервые он работал с настоящими компьютерами во время изучения астрономии в Летней научной программе в 1964 году [2].

Тарджан получил степень бакалавра математики в Калифорнийском технологическом институте в 1969 году. В Стэнфордском университете он получил степень магистра компьютерных наук в 1971 году и докторскую степень. в информатике (с несовершеннолетним в области математики) в 1972 году в Стэнфордском университете, он руководил Роберт Floyd [4] и Дональд Кнут , [5] как весьма видные ученые - компьютерщики, и его Ph.D. Диссертация была Эффективный алгоритм планарности . Тарьян выбрал информатику в качестве области своих интересов, потому что считал, что информатика - это способ заниматься математикой, который может иметь практическое значение. [6]

Карьера информатики [ править ]

Тарджан преподает в Принстонском университете с 1985 года. [6] Он также занимал академические должности в Корнельском университете (1972–73), Калифорнийском университете в Беркли (1973–1975), Стэнфордском университете (1974–1980) и в Нью-Йорке. Университет (1981–1985). Он также был научным сотрудником Исследовательского института NEC (1989–1997). [7] В апреле 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).

Алгоритмы и структуры данных [ править ]

Тарьян известен своей новаторской работой над алгоритмами теории графов и структурами данных. Некоторые из его известных алгоритмов включают Tarján в автономном режиме алгоритм не менее общие предки , и сильно связный алгоритм компонентов Tarján в , и он был одним из пяти соавторов в медианы медиан линейного времени алгоритма выбора . Алгоритм проверки планарности Хопкрофта – Тарьяна был первым алгоритмом линейного времени для проверки планарности. [8]

Тарьян также разработал важные структуры данных, такие как куча Фибоначчи (структура данных в куче, состоящая из леса деревьев) и развернутое дерево (самонастраивающееся двоичное дерево поиска; совместно изобретено Тарьаном и Дэниелом Слейтором ). Еще одним важным вкладом был анализ структуры данных с непересекающимися наборами ; он был первым, кто доказал оптимальное время выполнения с использованием обратной функции Аккермана .

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

Тарджан получил премию Тьюринга совместно с Джоном Хопкрофтом в 1986 году. В ссылке на награду указано [7], что это было:

За фундаментальные достижения в разработке и анализе алгоритмов и структур данных.

Тарджан также был избран членом ACM в 1994 году. В цитировании этой награды говорится: [9]

За выдающиеся достижения в области проектирования и анализа структур данных и алгоритмов.

Некоторые из других наград для Тарьяна включают:

  • Премия Неванлинны в области информатики (1983) [7] - первый лауреат [10]
  • Член Американской академии искусств и наук , избран в 1985 г. [11]
  • Премия Национальной академии наук за инициативы в области исследований (1984) [7]
  • Член Национальной академии наук , избран в 1987 г. [12]
  • Член Национальной инженерной академии , избран в 1988 г. [13]
  • Премия Пэрис Канеллакис в области теории и практики, ACM (1999) [7]
  • Премия выдающихся выпускников Калифорнийского технологического института , Калифорнийский технологический институт (2010 г.) [14]

Патенты [ править ]

Тарджан имеет не менее 18 патентов в США. [5] К ним относятся:

  • Дж. Бентли, Д. Слеатор и Р. Э. Тарджан, Патент США 4796003, Сжатие данных , 1989 [15]
  • Н. Мишра, Р. Шрайбер и Р. Э. Тарджан, Патент США 7 818 272, Метод обнаружения кластеров объектов в произвольном неориентированном графе с использованием разницы между долей внутренних соединений и максимальной долей соединений внешнего объекта , 2010 [16 ]
  • Б. Пинкас, С. Хабер, Р. Э. Тарджан и Т. Сандер, Патент США 8220036, Создание безопасного канала с человеком-пользователем , 2012 г. [17]

Научные статьи [ править ]

По данным Google Scholar, он опубликовал более 500 научных работ, которые были процитированы более 80 000 раз. [18]

Некоторые из его главных статей включают:

  • 1972: поиск в глубину и алгоритмы линейного графа, Р. Тарьян, журнал SIAM по вычислениям 1 (2), 146-160 [19]
  • 1987: Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети, ML Fredman, RE Tarjan, Journal of the ACM (JACM) 34 (3), 596-615 [20]
  • 1983: структуры данных и сетевые алгоритмы, RE Tarjan, Общество промышленной и прикладной математики [21]
  • 1988: Новый подход к проблеме максимального расхода, В. Голдберг, Р. Э. Тарьян, Журнал ACM (JACM) 35 (4), 921-940 [22]

Примечания [ править ]

  1. ^ "Intertrust Leadership" . intertrust.com .
  2. ^ a b Шаша, Деннис Эллиотт; Лазер, Кэти А. (1998) [1995]. "Роберт Э. Тарджан: В поисках хорошей структуры". Из их разума: жизни и открытия 15 великих ученых-компьютерщиков . Коперник / Спрингер. С.  102–119 . ISBN 978-0-387-97992-2. OCLC  32240355 .
  3. ^ «Роберт Тарджан: Искусство алгоритма» . Hewlett-Packard . Проверено 5 сентября 2010 .
  4. ^ "Роберт Эндре Тарьян" . Проект «Математическая генеалогия» . Проверено 9 января 2008 .
  5. ^ a b Тарджан, Роберт Эндре (15 ноября 2019 г.). "Биографическая справка" (PDF) . Архивировано из оригинального (PDF) 23.11.2019 . Проверено 23 ноября 2019 .
  6. ^ a b «Роберт Эндре Тарджан: Искусство алгоритма (интервью)» . Hewlett Packard. Сентябрь 2004 . Проверено 9 января 2008 .
  7. ^ a b c d e Кинг, В. "Роберт Э. Тарджан - лауреат премии AM Тьюринга" . ACM . Проверено 19 января 2014 .
  8. ^ Коджай, Уильям; Крехер, Дональд Л (2005). «Плоские графы». Графики, алгоритмы и оптимизация . Бока-Ратон: Чепмен и Холл / CRC. п. 312 . ISBN 978-1-58488-396-8. OCLC  56319851 .
  9. ^ "Премия стипендиатов - Роберт Э. Тарьян" . ACM . 25 сентября 1998 . Проверено 18 ноября 2005 .
  10. ^ "Лауреаты премии Рольфа Неванлинны" . Международный математический союз . Архивировано из оригинала на 2008-12-27 . Проверено 19 января 2014 .
  11. ^ "Роберт Эндре Тарьян" . Американская академия искусств и наук . Проверено 15 июня 2020 .
  12. ^ "Роберт Тарьян" . www.nasonline.org . Проверено 15 июня 2020 .
  13. ^ "Доктор Роберт Э. Тарьян" . Веб-сайт NAE . Проверено 15 июня 2020 .
  14. ^ «Калифорнийский технологический институт называет пять выдающихся выпускников» (пресс-релиз). Калифорнийский технологический институт . 2010-03-15. Архивировано из оригинала на 2010-10-10 . Проверено 26 августа 2010 .
  15. ^ Бентли, Джон Л .; Слеатор, Дэниел Д.К.; Тарджан, Роберт Э. (3 января 1989 г.). «Патент США 4796003 - сжатие данных» .
  16. ^ Нина, Мишра; Шрайбер, Роберт Сэмюэл; Роберт Э., Тарьян (19 октября 2010 г.). «Патент США 7818272 - Метод обнаружения кластеров объектов в произвольном неориентированном графе с использованием разницы между долей внутренних соединений и максимальной долей соединений внешнего объекта» .
  17. ^ Пинкас, Биньямин; Haber, Stuart A .; Тарьян, Роберт Э .; Сандер, Томас (10 июля 2012 г.). «Патент США 8220036 - Создание защищенного канала с человеком-пользователем» .
  18. ^ "Роберт Тарьян" . scholar.google.com . Источник 2021-02-02 .
  19. ^ Тарджан, Роберт (1972-06-01). "Поиск в глубину и алгоритмы линейных графов" . SIAM Journal on Computing . 1 (2): 146–160. DOI : 10.1137 / 0201010 . ISSN 0097-5397 . 
  20. ^ Фредман, Майкл Л .; Тарджан, Роберт Эндре (1987-07-01). «Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети» . Журнал ACM . 34 (3): 596–615. DOI : 10.1145 / 28869.28874 . ISSN 0004-5411 . S2CID 7904683 .  
  21. ^ "Back Matter" . Структуры данных и сетевые алгоритмы : 125–131. Январь 1983 г. doi : 10.1137 / 1.9781611970265.bm . ISBN 978-0-89871-187-5.
  22. ^ Голдберг, Эндрю V .; Тарджан, Роберт Э. (1988-10-01). «Новый подход к проблеме максимального расхода» . Журнал ACM . 35 (4): 921–940. DOI : 10,1145 / 48014,61051 . ISSN 0004-5411 . S2CID 14492800 .  

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

  • Тарджан, Роберт Э. (1983). Структуры данных и сетевые алгоритмы . Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-187-5. OCLC  10120539 .
  • Тарьян, Роберт Э .; Полиа, Джордж; Вудс, Дональд Р. (1983). Заметки по вводной комбинаторике . Бостон: Биркхаузер. ISBN 978-0-8176-3170-3. OCLC  10018128 .
  • Записи OCLC для Роберта Э. Тарьяна
  • Роберт Э. Тарджан на сервере библиографии DBLP

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

  • Роберт Э. Тарджан на сервере библиографии DBLP
  • Список патентов Роберта Тарьяна в Patent Directory IPEXL
  • Домашняя страница Роберта Тарьяна в Принстоне .
  • Роберт Эндре Тарджан на проекте « Математическая генеалогия»