Введение

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

Личная жизнь и образование

Он родился в Помоне, штат Калифорния. Его отец, выросший в Венгрии, был детским психиатром, специализирующимся на лечении умственной отсталости, и руководил государственной больницей. В детстве Тарджан много читал научную фантастику и мечтал стать астрономом. Он увлекся математикой после прочтения колонки математических головоломок Мартина Гарднера в журнале Scientific American. Серьезно заниматься математикой он начал в восьмом классе, благодаря "очень вдохновляющему" учителю. Во время учебы в старшей школе Тарджан устроился на работу, где занимался обработкой перфокарт на машинах IBM. Впервые с настоящими компьютерами он познакомился, изучая астрономию в летней научной программе в 1964 году, вместе с Дональдом Кнутом.

Сейчас Тарджан живет в Принстоне, штат Нью-Джерси, и в Силиконовой долине. Он женат на Найле Ризк. У него три дочери: Алиса Тарджан, Софи Завацки и Максин Тарджан.

Карьера в области информатики

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

Патенты

Тарджан имеет по меньшей мере 18 патентов США. Среди них:

J. Bentley, D. Sleator и R. E. Tarjan, U.S. Patent 4,796,003, Data Compaction, 1989
N. Mishra, R. Schreiber и R. E. Tarjan, U.S. Patent 7,818,272, Метод обнаружения кластеров объектов в произвольном неориентированном графе, основанный на разнице между долей внутренних связей и максимальной долей связей с внешним объектом, 2010
B. Pinkas, S. Haber, R. E. Tarjan и T. Sander, U.S. Patent 8220036, Установление защищенного канала связи с пользователем, 2012