Тарьян Роберт Андре — различия между версиями
Vgabdulin (обсуждение | вклад) (→Библиография) |
Vgabdulin (обсуждение | вклад) |
||
| Строка 19: | Строка 19: | ||
| дата смерти = | | дата смерти = | ||
| место смерти = | | место смерти = | ||
| − | | краткая информация = | + | | краткая информация = Специалист в области теории вычислительных систем |
| − | | тэг01 = доктор | + | | тэг01 = доктор философии |
| тэг02 = профессор | | тэг02 = профессор | ||
| тэг03 = лауреат премии Тьюринга | | тэг03 = лауреат премии Тьюринга | ||
| Строка 26: | Строка 26: | ||
| тэг05 = лауреат премии Paris Kanellakis Award in Theory and Practice | | тэг05 = лауреат премии Paris Kanellakis Award in Theory and Practice | ||
| тэг06 = Медаль имени Блеза Паскаля | | тэг06 = Медаль имени Блеза Паскаля | ||
| + | математик | ||
}} | }} | ||
| Строка 33: | Строка 34: | ||
Является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка (Tarjan’s off-line least common ancestors algorithm). | Является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка (Tarjan’s off-line least common ancestors algorithm). | ||
| − | Также он является соавтором структур данных «Фибоначчиева куча» и «Splay-дерево». | + | Также он является соавтором структур данных «Фибоначчиева куча» и «Splay-дерево». |
==Образование== | ==Образование== | ||
Отец Роберта Тарьяна был детским врачом, специализирующимся в мозге и являлся управляющим центральной поликлиники штата. | Отец Роберта Тарьяна был детским врачом, специализирующимся в мозге и являлся управляющим центральной поликлиники штата. | ||
| − | В детстве Тарьян читал много научной фантастики и хотел стать астрономом. Он | + | В детстве Тарьян читал много научной фантастики и хотел стать астрономом. Он заинтересовался математикой после прочтения заметок Мартина Гарднера по математическим играм в журнале Scientific American. |
Пока Тарьян учился в школе ему посчастливилось поработать в IBM с сортировально-подборочной машиной для перфокарт. В летней школе в 1964 он получил первый серьёзный опыт работы с настоящими компьютерами. | Пока Тарьян учился в школе ему посчастливилось поработать в IBM с сортировально-подборочной машиной для перфокарт. В летней школе в 1964 он получил первый серьёзный опыт работы с настоящими компьютерами. | ||
| Строка 53: | Строка 54: | ||
Тарьян придумал множество эффективных алгоритмов и структур данных для решения различных прикладных задач. Он опубликовал более 228 статей в реферируемых журналах и монографиях. | Тарьян придумал множество эффективных алгоритмов и структур данных для решения различных прикладных задач. Он опубликовал более 228 статей в реферируемых журналах и монографиях. | ||
| − | Тарьян известен своими революционными работами | + | Тарьян известен своими революционными работами в области алгоритмов на графах. Наиболее яркие из них — Оффлайновый алгоритм Тарьяна поиска ближайшего общего предка для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и Алгоритм Тарьяна вычисления сильно связных компонент. Алгоритм Хопкрофта-Тарьяна стал первым линейным алгоритмом определения планарности графа. |
Тарьян разработал ряд важнейших структур данных, таких как «Фибоначчиева куча» и Расширяющееся дерево (splay tree) (один из видов сбалансированного двоичного дерева поиска; в соавторстве с Даниилом Слейтором). | Тарьян разработал ряд важнейших структур данных, таких как «Фибоначчиева куча» и Расширяющееся дерево (splay tree) (один из видов сбалансированного двоичного дерева поиска; в соавторстве с Даниилом Слейтором). | ||
Версия 08:48, 30 апреля 2011
[[Категория:Медаль имени Блеза Паскаля математик|Тарьян Роберт]]
| Тарьян Роберт | |
| Robert Endre Tarjan | |
| |
| Другие имена: | Тарьян Роберт Андре |
| На английском: | Robert Endre Tarjan |
| Дата рождения: | 30.04.1948 |
| Место рождения: | Помона, США |
| Краткая информация: Специалист в области теории вычислительных систем | |
Содержание
Биография
Родился 30 апреля 1948 года в калифорнийском городе Помона.
Является автором множества алгоритмов решения задач теории графов и дискретной математики, включая алгоритм поиска наименьшего общего предка (Tarjan’s off-line least common ancestors algorithm).
Также он является соавтором структур данных «Фибоначчиева куча» и «Splay-дерево».
Образование
Отец Роберта Тарьяна был детским врачом, специализирующимся в мозге и являлся управляющим центральной поликлиники штата. В детстве Тарьян читал много научной фантастики и хотел стать астрономом. Он заинтересовался математикой после прочтения заметок Мартина Гарднера по математическим играм в журнале Scientific American.
Пока Тарьян учился в школе ему посчастливилось поработать в IBM с сортировально-подборочной машиной для перфокарт. В летней школе в 1964 он получил первый серьёзный опыт работы с настоящими компьютерами.
Тарьян получил звание бакалавра по математике в технологическом институте Калифорнии (California Institute of Technology) в 1969. В Стендфордском университете он получил магистерскую степень по компьютерным наукам (1971) и степень доктора наук (Doctor of Philosophy) в компьютерных науках — в 1972.
Его диссертация называлась «Эффективный алгоритм определения планарности графа» (An Efficient Planarity Algorithm).
Карьера
Тарьян работает преподавателем в университете Принстона начиная с 1985 года. У него также были академическая должности в университете Корнел (1972-1973), университете Калифорнии, Беркли (1973—1975), Университете Стендфорда (1974—1980), Нью-Йоркском университете (1981—1985). Он также был членом NEC Research Institute (1989—1997) и числится (на должности Visiting Scientist) в университете Массачусетса (1996).
Тарьян работал в AT&T Bell Labs (1980—1989), InterTrust Technologies (1997—2001), Compaq (2002) и Hewlett Packard, где продолжает работать с 2006. Он избирался членом различных комитетов ACM и IEEE, а также работал редактором нескольких реферируемых журналов.
Алгоритмы и структуры данных
Тарьян придумал множество эффективных алгоритмов и структур данных для решения различных прикладных задач. Он опубликовал более 228 статей в реферируемых журналах и монографиях.
Тарьян известен своими революционными работами в области алгоритмов на графах. Наиболее яркие из них — Оффлайновый алгоритм Тарьяна поиска ближайшего общего предка для многократного быстрого поиска самого глубокого узла дерева, являющегося общим предком двух заданных узлов, и Алгоритм Тарьяна вычисления сильно связных компонент. Алгоритм Хопкрофта-Тарьяна стал первым линейным алгоритмом определения планарности графа.
Тарьян разработал ряд важнейших структур данных, таких как «Фибоначчиева куча» и Расширяющееся дерево (splay tree) (один из видов сбалансированного двоичного дерева поиска; в соавторстве с Даниилом Слейтором).
Сегодня Роберт Тарьян заслуженный профессор компьютерных наук (James S. McDonnell Distinguished University Professor of Computer Science) в университете Принстона, а также работает в Hewlett-Packard.
Публикации
- Robert E. Tarjan Data structures and network algorithms. — Philadelphia: 1983. — ISBN 978-0898711875
- Robert E. Tarjan Notes on introductory combinatorics. — Boston: 1983. — ISBN 978-0817631703
- OCLC entries for Robert E Tarjan [1]
- DBLP entry for Robert Endre Tarjan [2]
Достижения
- доктор философских наук
- заслуженный профессор компьютерных наук
Награды
- Премия Тьюринга (Вместе с Джоном Хопкрофтом в 1986. В сопроводительном тексте к награде написано За фундаментальные результаты в области разработки и анализа алгоритмов и структур данных)
- член ACM (ACM Fellow. 1994. В поздравительном тексте указано: За плодотворный труд в области разработки и анализа алгоритмов и структур данных)
- National Academy of Sciences Award (for Initiatives in Research. 1984)
- Paris Kanellakis Award in Theory and Practice (ACM. 1999)
- медаль им. Блеза Паскаля за работы в области математики и компьютерных наук (Европейской академии наук, 2004)
- Премия математика Рольфа Германа Неванлинны (1982. Золотая медаль и денежная премия)
Библиография
Контакты
- Email:robert.tarjan AT hp.com
