Роберт Андре Тар'я: біографія

Освіта

Батько Роберта Тар'я був дитячим лікарем, що спеціалізується на затримках розумового розвитку, і був керуючим центральної поліклініки штату.

У дитинстві Тар'я читав багато наукової фантастики і хотів стати астрономом. Він зацікавився математикою після прочитання нотаток Мартіна Гарднера з математичних ігор в журналі 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.

Нагороди

Тар'я отримав Премію Тьюрінга разом з Джоном Хопкрофта в 1986. У супровідному тексті до нагороди написано

Тар'я також був обраний членом ACM (ACM Fellow) у 1994. У вітальному тексті зазначено:

Інші нагороди Роберта Тар'я:

• Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences (2004)
• Paris Kanellakis Award in Theory and Practice, ACM (1999)
• National Academy of Sciences Award for Initiatives in Research (1984)
• Nevanlinna Prize in Information Science (1983) - first recipient

В кінці лютого 2009 року Тар'я займав 39 місце в списку найбільш цитованих авторів у проекті CiteSeer.

Бібліографічні посилання

• OCLC entries for Robert E Tarjan
• DBLP entry for Robert Endre Tarjan
• Robert E. TarjanData structures and network algorithms. - Philadelphia: 1983. - ISBN 978-0898711875
• Robert E. TarjanNotes on introductory combinatorics. - Boston: 1983. - ISBN 978-0817631703

Комментарии

Сайт: Википедия