Robert Tarjan

Robert Endre Tarjan
Bob Tarjan.jpg
Geboren 30. April 1948 (Alter 74)
Pomona, Kalifornien
Staatsbürgerschaft amerikanisch
Alma Mater Kalifornisches Institut der Technologie (BS)
Universität in Stanford (FRAU, PhD)
Bekannt für Algorithmen und Datenstrukturen
Auszeichnungen Paris Kanellakis Award (1999)
Turing Award (1986)
NevanLinna -Preis (1982)
Wissenschaftliche Karriere
Felder Informatik
Institutionen Princeton Universität
New Yorker Universität
Universität in Stanford
Universität von Kalifornien, Berkeley
Cornell Universität
Microsoft Research
Intertrust -Technologien
Hewlett Packard
Compaq
NEC -Forschung
Bell Labs
These Ein effizienter Planaritätsalgorithmus (1972)
Doktorand Robert W. Floyd
Andere akademische Berater Donald Knuth
Doktorand
Webseite www.cs.Princeton.edu/~ ret/

Robert Endre Tarjan (Geboren am 30. April 1948) ist ein Amerikaner Informatiker und Mathematiker. Er ist der Entdecker mehrerer Graph Algorithmen, einschließlich Tarjans offline niedrigste gemeinsame Vorfahren Algorithmusund Co-Erventor von beidem Spreizbäume und Fibonacci Heaps. Tarjan ist derzeit der James S. McDonnell Distinguished University Professor für Informatik bei Princeton Universitätund der Chefwissenschaftler bei Intertrust Technologies Corporation.[1]

Frühes Leben und Ausbildung

Er wurde geboren in Pomona, Kalifornien. Sein Vater, aufgewachsen in Ungarn,[2] war ein Kinderpsychiater, der sich auf geistige Behinderung spezialisiert hatte und ein staatliches Krankenhaus leitete.[3] Als Kind las Tarjan viel Science -Fiction und wollte ein sein Astronom. Er interessierte sich für Mathematik nach dem Lesen Martin Gardner'S Mathematical Games -Kolumne in Wissenschaftlicher Amerikaner. Dank eines "sehr anregenden" Lehrers interessierte er sich ernsthaft für Mathematik in der achten Klasse.[4]

Während er in der High School war, bekam Tarjan einen Job, bei dem er IBM Punch Card Collatoren arbeitete. Er arbeitete zum ersten Mal mit echten Computern, während er Astronomie studierte Sommerwissenschaftsprogramm 1964.[3]

Tarjan erhielt a Bachelorabschluss in Mathematik von der Kalifornisches Institut der Technologie im Jahr 1969. at Universität in StanfordEr erhielt 1971 seinen Master in Informatik und a Ph.D. In Informatik (mit einem Minderjährigen in Mathematik) im Jahr 1972. in Stanford wurde er von beaufsichtigt von Robert Floyd[5] und Donald Knuth,[6] Sowohl hochwertige Informatiker als auch sein Ph.D. Dissertation war Ein effizienter Planaritätsalgorithmus. Tarjan wählte Informatik als Interessengebiet aus, weil er glaubte, dass Informatik eine Möglichkeit war, Mathematik zu machen, die sich praktisch auswirken könnte.[7]

Informatik Karriere

Tarjan unterrichtet seit 1985 an der Princeton University.[7] Er hat auch akademische Positionen bei Cornell Universität (1972–73), Universität von Kalifornien, Berkeley (1973–1975), Universität in Stanford (1974–1980) und New Yorker Universität (1981–1985). Er war auch Fellow des NEC Research Institute (1989–1997).[8] Im April 2013 kam er neben der Position in Princeton zu Microsoft Research Silicon Valley. Im Oktober 2014 trat er als Chefwissenschaftlerin für Intertrust -Technologien zurück.

Tarjan hat bei AT & T Bell Labs (1980–1989), Intertrust Technologies (1997–2001, 2014 - Present), Compaq (2002) und Hewlett Packard (2006–2013) gearbeitet.

Algorithmen und Datenstrukturen

Tarjan ist bekannt für seine Pionierarbeit zu Graphentheoriealgorithmen und Datenstrukturen. Einige seiner bekannten Algorithmen umfassen Tarjans offline am wenigsten gemeinsame Vorfahren Algorithmus, und Tarjans stark verbundener Komponentenalgorithmusund er war einer von fünf Mitautoren der Median der Mediane lineare Zeit Auswahlalgorithmus. Der Hopcroft -Tarjan Planaritätstest Der Algorithmus war der erste Linear-Zeit-Algorithmus für Planaritätstests.[9]

Tarjan hat auch wichtige Datenstrukturen wie die entwickelt Fibonacci Heap (eine Haufen Datenstruktur, die aus einem Baumwald besteht) und die Spreizbaum (ein selbstverordneter binärer Suchbaum; gemeinsam von Tarjan und Daniel Sleator). Ein weiterer signifikanter Beitrag war die Analyse der Datenstruktur disjunkt; Er war der erste, der die optimale Laufzeit mit dem Inversen beweist Ackermann -Funktion.[10]

Auszeichnungen

Tarjan erhielt die Turing Award gemeinsam mit John Hopcroft 1986. Das Zitat für die Auszeichnung gibt an[8] dass es war:

Für grundlegende Erfolge bei der Gestaltung und Analyse von Algorithmen und Datenstrukturen.

Tarjan wurde ebenfalls gewählt ACM Fellow Im Jahr 1994. Das Zitat für diese Auszeichnung besagt:[11]

Für wegweisende Fortschritte bei der Gestaltung und Analyse von Datenstrukturen und Algorithmen.

Einige der anderen Auszeichnungen für Tarjan sind:

Patente

Tarjan hält mindestens 18 US -Patente.[6] Diese beinhalten:

  • J. Bentley, D. Sleator und R. E. Tarjan, U. S. Patent 4.796,003, Datenverdichtung, 1989[18]
  • N. Mishra, R. Schreiber und R. E. Tarjan, US -Patent 7.818,272, U. S. Methode zur Entdeckung von Objektlücken in einem willkürlichen undirezierten Graphen unter Verwendung einer Differenz zwischen einem Bruchteil interner Verbindungen und maximalem Anteil von Verbindungen durch ein externes Objekt, 2010[19]
  • B. Pinkas, S. Haber, R. E. Tarjan und T. Sander, U. S. Patent 8220036, Einrichtung eines sicheren Kanals mit einem menschlichen Benutzer, 2012[20]

Forschungsunterlagen

Entsprechend Google Scholar Er hat über 500 Forschungsarbeiten veröffentlicht, die über 80.000 Mal zitiert wurden.[21]

Einige seiner Top -Papiere umfassen:

  • 1972: Tiefe-First-Such- und Lineare Graph-Algorithmen, R Tarjan, Siam Journal über Computing 1 (2), 146-160[22]
  • 1987: Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen, ML Fredman, Re Tarjan, Journal of the ACM (JACM) 34 (3), 596-615[23]
  • 1983: Datenstrukturen und Netzwerkalgorithmen, Re Tarjan, Gesellschaft für industrielle und angewandte Mathematik[24]
  • 1988: Ein neuer Ansatz zum Maximum-Flow-Problem, V Goldberg, Re Tarjan, Journal of the ACM (JACM) 35 (4), 921-940[25]

Anmerkungen

  1. ^ "Intertrust -Führung". InterTrust.com.
  2. ^ "Jüdische Empfänger des ACM A.M. Turing Award". Jinfo.org.
  3. ^ a b Shasha, Dennis Elliott; Lazere, Cathy A. (1998) [1995]. "Robert E. Tarjan: Auf der Suche nach guter Struktur". Aus ihren Köpfen: Das Leben und Entdeckungen von 15 großen Informatikern. Copernicus/Springer. pp.102–119. ISBN 978-0-387-97992-2. OCLC 32240355.
  4. ^ "Robert Tarjan: Die Kunst des Algorithmus". Hewlett Packard. Abgerufen 2010-09-05.
  5. ^ "Robert Endre Tarjan". Mathematik Genealogie -Projekt. Abgerufen 2008-01-09.
  6. ^ a b Tarjan, Robert Endre (15. November 2019). "Lebenslauf" (PDF). Archiviert von das Original (PDF) Am 2019-11-23. Abgerufen 2019-11-23.
  7. ^ a b "Robert Endre Tarjan: Die Kunst des Algorithmus (Interview)". Hewlett Packard. September 2004. Abgerufen 2008-01-09.
  8. ^ a b c d e König, V. "Robert E Tarjan - A. M. Turing Award Laureate". ACM. Abgerufen 2014-01-19.
  9. ^ Kocay, William; Kreher, Donald L (2005). "Planare Diagramme". Grafiken, Algorithmen und Optimierung. Boca Raton: Chapman & Hall/CRC. p.312. ISBN 978-1-58488-396-8. OCLC 56319851.
  10. ^ Tarjan, Robert E.; Van Leeuwen, Januar (1984). "Worst-Case-Analyse von festgelegten Unionalgorithmen". Journal of the ACM. 31 (2): 245–281. doi:10.1145/62.2160. S2CID 5363073.
  11. ^ "Fellows Award - Robert E. Tarjan". ACM. 25. September 1998. Abgerufen 2005-11-18.
  12. ^ "Rolf NevanLinna -Preisträger". Internationale mathematische Union. Archiviert von das Original am 2008-12-27. Abgerufen 2014-01-19.
  13. ^ "Robert Endre Tarjan". Amerikanische Akademie für Kunst und Wissenschaften. Abgerufen 2020-06-15.
  14. ^ "Robert Tarjan". www.nasonline.org. Abgerufen 2020-06-15.
  15. ^ "Dr. Robert E. Tarjan". NAE -Website. Abgerufen 2020-06-15.
  16. ^ "APS -Mitgliedsgeschichte". Search.amphilsoc.org. Abgerufen 2022-04-19.
  17. ^ "Caltech nennt fünf angesehene Alumni" (Pressemitteilung). Kalifornisches Institut der Technologie. 2010-03-15. Archiviert von das Original Am 2010-10-10. Abgerufen 2010-08-26.
  18. ^ Bentley, Jon L.; Sleator, Daniel D. K.; Tarjan, Robert E. (3. Januar 1989). "US -Patent 4796003 - Datenverdichtung".
  19. ^ Nina, Mishra; Schreiber, Robert Samuel; Robert E., Tarjan (19. Oktober 2010). "United States Patent 7818272 - Methode zur Entdeckung von Cluster von Objekten in einem willkürlichen, undirezierten Graphen unter Verwendung eines Unterschieds zwischen einem Bruchteil interner Verbindungen und maximaler Bruchteil von Verbindungen durch ein externes Objekt".
  20. ^ Pinkas, Binyamin; Haber, Stuart A.; Tarjan, Robert E.; Sander, Tomas (10. Juli 2012). "US -Patent 8220036 - Einrichtung eines sicheren Kanals mit einem menschlichen Benutzer".
  21. ^ "Robert Tarjan". Scholar.google.com. Abgerufen 2021-02-02.
  22. ^ Tarjan, Robert (1972-06-01). "Tiefe-First-Suche und lineare Graphenalgorithmen". Siam Journal über Computing. 1 (2): 146–160. doi:10.1137/0201010. ISSN 0097-5397.
  23. ^ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). "Fibonacci Heaps und ihre Verwendung in verbesserten Netzwerkoptimierungsalgorithmen". Journal of the ACM. 34 (3): 596–615. doi:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.
  24. ^ "Rückenmaterie". Datenstrukturen und Netzwerkalgorithmen: 125–131. Januar 1983. doi:10.1137/1.9781611970265.bm. ISBN 978-0-89871-187-5.
  25. ^ Goldberg, Andrew V.; Tarjan, Robert E. (1988-10-01). "Ein neuer Ansatz für das Problem des Maximum-Flow-Problems". Journal of the ACM. 35 (4): 921–940. doi:10.1145/48014.61051. ISSN 0004-5411. S2CID 14492800.

Verweise

Externe Links