Роберт Тарджан - Robert Tarjan
Роберт Эндре Тарджан | |
|---|---|
 | |
| Родился | 30 апреля 1948 г. |
| Гражданство | Американец |
| Альма-матер | Калифорнийский технологический институт (BS ) Стэндфордский Университет (РС, кандидат наук ) |
| Известен | Алгоритмы и структуры данных |
| Награды | Премия Пэрис Канеллакис (1999) Премия Тьюринга (1986) Приз Неванлинны (1982) |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Университет Принстона Нью-Йоркский университет Стэндфордский Университет Калифорнийский университет в Беркли Корнелл Университет Microsoft Research Интертраст Технологии Hewlett Packard Compaq NEC Research Bell Labs |
| Тезис | Эффективный алгоритм планарности (1972) |
| Докторант | Роберт В. Флойд |
| Другие научные консультанты | Дональд Кнут |
| Докторанты | |
| Интернет сайт | www |
Роберт Эндре Тарджан (родился 30 апреля 1948 г.) Американец специалист в области информатики и математик. Он первооткрыватель нескольких график алгоритмы, в том числе Автономный алгоритм наименьших общих предков Тарьяна, и соавтор обоих растопыренные деревья и Куча Фибоначчи. Тарьян в настоящее время Джеймс С. Макдоннелл Заслуженный профессор компьютерных наук в Университет Принстона, и главный научный сотрудник Корпорация Intertrust Technologies.[1]
ранняя жизнь и образование
Он родился в Помона, Калифорния. Его отец был детским психиатром, специализирующимся на умственной отсталости, и руководил государственной больницей.[2] В детстве Тарджан читал много научной фантастики и хотел астроном. Он заинтересовался математика после чтения Мартин Гарднер столбец "Математические игры" в Scientific American. Он серьезно увлекся математикой в восьмом классе благодаря «очень стимулирующему» учителю.[3]
В старших классах школы Тарджан устроился на работу, где работал подборщиком перфокарт IBM. Он впервые работал с настоящими компьютерами, когда изучал астрономию в Летняя научная программа в 1964 г.[2]
Тарьян получил Степень бакалавра по математике из Калифорнийский технологический институт в 1969 году. Стэндфордский Университет, он получил степень магистра компьютерных наук в 1971 году и Кандидат наук. в области информатики (с небольшим в математике) в 1972 году. В Стэнфорде его руководил Роберт Флойд[4] и Дональд Кнут,[5] оба выдающихся компьютерных ученых, и его доктор философии. диссертация была Эффективный алгоритм планарности. Тарьян выбрал информатику в качестве области своих интересов, потому что считал, что информатика - это способ заниматься математикой, который может иметь практическое значение.[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).
Алгоритмы и структуры данных
Тарьян известен своей новаторской работой над алгоритмами теории графов и структурами данных. Некоторые из его известных алгоритмов включают Автономный алгоритм наименее распространенных предков Тарьяна, и Алгоритм сильносвязных компонентов Тарьяна, и он был одним из пяти соавторов медиана медиан линейное время алгоритм выбора. Хопкрофт-Тарьян проверка планарности Алгоритм был первым алгоритмом линейного времени для проверки планарности.[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]
Заметки
- ^ «Интертрестовское лидерство». intertrust.com.
- ^ а б Шаша, Деннис Эллиотт; Лазер, Кэти А. (1998) [1995]. "Роберт Э. Тарджан: В поисках хорошей структуры". Не в их уме: жизни и открытия 15 великих ученых-компьютерщиков. Коперник / Спрингер. стр.102–119. ISBN 978-0-387-97992-2. OCLC 32240355.
- ^ "Роберт Тарджан: Искусство алгоритма". Hewlett Packard. Получено 2010-09-05.
- ^ "Роберт Эндре Тарджан". Проект "Математическая генеалогия". Получено 2008-01-09.
- ^ а б Тарджан, Роберт Эндре (15 ноября 2019 г.). "Биография Резюме" (PDF). Архивировано из оригинал (PDF) на 2019-11-23. Получено 2019-11-23.
- ^ а б «Роберт Эндре Тарджан: Искусство алгоритма (интервью)». Hewlett Packard. Сентябрь 2004 г.. Получено 2008-01-09.
- ^ а б c d е Кинг, В. "Роберт Э. Тарджан - лауреат премии А.М. Тьюринга". ACM. Получено 2014-01-19.
- ^ Коджай, Уильям; Крехер, Дональд Л (2005). «Плоские графы». Графики, алгоритмы и оптимизация. Бока-Ратон: Чепмен и Холл / CRC. п.312. ISBN 978-1-58488-396-8. OCLC 56319851.
- ^ «Премия стипендиатов - Роберт Э. Тарьян». ACM. 25 сентября 1998 г.. Получено 2005-11-18.
- ^ «Лауреаты премии Рольфа Неванлинны». Международный математический союз. Архивировано из оригинал на 2008-12-27. Получено 2014-01-19.
- ^ "Роберт Эндре Тарджан". Американская академия искусств и наук. Получено 2020-06-15.
- ^ "Роберт Тарьян". www.nasonline.org. Получено 2020-06-15.
- ^ "Доктор Роберт Э. Тарджан". Веб-сайт NAE. Получено 2020-06-15.
- ^ "Калтех назвал пять выдающихся выпускников" (Пресс-релиз). Калифорнийский технологический институт. 2010-03-15. Архивировано из оригинал на 2010-10-10. Получено 2010-08-26.
- ^ Бентли, Джон Л .; Слеатор, Дэниел Д. К .; Тарджан, Роберт Э. (3 января 1989 г.). «Патент США 4796003 - сжатие данных».
- ^ Нина, Мишра; Шрайбер, Роберт Сэмюэл; Роберт Э., Тарьян (19 октября 2010 г.). «Патент США 7818272 - Метод обнаружения кластеров объектов в произвольном неориентированном графе с использованием разницы между долей внутренних соединений и максимальной долей соединений внешнего объекта».
- ^ Пинкас, Биньямин; Haber, Stuart A .; Тарьян, Роберт Э .; Сандер, Томас (10 июля 2012 г.). «Патент США 8220036 - Создание безопасного канала с человеком-пользователем».
использованная литература
- Тарджан, Роберт Э. (1983). Структуры данных и сетевые алгоритмы. Филадельфия: Общество промышленной и прикладной математики. ISBN 978-0-89871-187-5. OCLC 10120539.
- Тарьян, Роберт Э .; Полиа, Джордж; Вудс, Дональд Р. (1983). Заметки по вводной комбинаторике. Бостон: Биркхаузер. ISBN 978-0-8176-3170-3. OCLC 10018128.
- Записи OCLC для Тарьян Роберт Э.
- Роберт Э. Тарджан в DBLP Сервер библиографии
