Робърт Тарьян

Снимка на Робърт Тарьян (photo Robert Tarjan)

Robert Tarjan

  • Дата на раждане: 30.04.1948 г.
  • Възраст: 68 години
  • Място на раждане: Помона, САЩ
  • Националност: САЩ

Биография

Той е автор на множество алгоритми за решаване на задачи по теория на зигмунд фройд и дискретна математика, включително алгоритъм за търсене на най-малкия общ прародител (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). Той също така е бил член на НЕК 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. В поздравително текста се казва:

За плодотворен труд в областта на дизайн и анализ на алгоритми и структури от данни.

Други награди Робърт Тарьяна:

Награда Неванлинны (1982) — първият лауреат на тази премия

National Academy of Sciences Award for Initiatives in Research (1984)

Paris Kanellakis Award in Theory and Practice, ACM (1999)

Blaise Pascal Medal in Mathematics and Computer Science, European Academy of Sciences (2004)

В края на февруари 2009 г. Тарьян заема 39 място в списъка на най-цитираните автори в проекта CiteSeer.