https://wiki-de.moshellshocker.dns64.de/index.php?action=history&feed=atom&title=Robert_TarjanRobert Tarjan - Versionsgeschichte2026-06-08T22:02:47ZVersionsgeschichte dieser Seite in Wikipedia (Deutsch) – Lokale KopieMediaWiki 1.43.8https://wiki-de.moshellshocker.dns64.de/index.php?title=Robert_Tarjan&diff=588812&oldid=prev~2026-81098: Die Datenstruktur wurde falsch geschrieben, nun ist sie richtig und zur Wikipediaseite verlinkt.2026-01-04T23:13:41Z<p>Die Datenstruktur wurde falsch geschrieben, nun ist sie richtig und zur Wikipediaseite verlinkt.</p>
<p><b>Neue Seite</b></p><div>[[Datei:Bob Tarjan.jpg|mini|Robert Tarjan 2010]]<br />
'''Robert Endre „Bob“ Tarjan''' (* [[30. April]] [[1948]] in [[Pomona (Kalifornien)|Pomona]], [[Kalifornien]]) ist ein [[Vereinigte Staaten|US-amerikanischer]] [[Informatiker]]. 1986 wurde er zusammen mit [[John E. Hopcroft]] für das Design und die Analyse von [[Algorithmus|Algorithmen]] und [[Datenstruktur]]en mit dem [[Turing Award]] ausgezeichnet.<br />
<br />
== Leben ==<br />
Tarjan studierte am [[California Institute of Technology|Caltech]] im kalifornischen [[Pasadena (Kalifornien)|Pasadena]] Mathematik und schloss das Bachelor-Studium 1969 ab. Er wechselte an die [[Stanford University]], wo er 1971 seinen Master in Informatik und 1972 seinen Ph.D. in Informatik mit dem Nebenfach Mathematik machte. Seine Thesis ''An Efficient Planarity Algorithm'' wurde von [[Robert Floyd]] betreut, die Vorlesungen von [[Donald Ervin Knuth]].<br />
<br />
Anschließend war er für ein Jahr wissenschaftlicher Mitarbeiter an der [[Cornell University]], dann für zwei Jahre Miller Research Fellow an der [[University of California, Berkeley]], und von 1974 bis 1977 wissenschaftlicher Mitarbeiter und dann bis 1980 außerordentlicher Professor für Informatik an der Stanford University. 1981 bis 1985 war er außerplanmäßiger Professor an der [[New York University]]. Seit 1985 ist er ''James S. McDonnell Distinguished University Professor of Computer Science'' an der [[Princeton University]]. Von 1989 bis 1994 und wieder seit 2001 ist er dort auch Co-Director des [[National Science Foundation Center for Discrete Mathematics and Theoretical Computer Science]]. 1996 war er Gastprofessor am [[Massachusetts Institute of Technology|MIT]].<br />
<br />
Parallel begann er 1980 auch eine Karriere in der Industrie, war zunächst bis 1989 ''Member of Technical Staff'' bei den [[AT&T Bell Laboratories]], dann bis 1997 Fellow des [[NEC Corporation|NEC]] Research Institute, und danach bis 2001 Chefwissenschaftler von [[InterTrust Technologies]]. Im Jahr 2002 war er kurzzeitig Corporate Fellow von [[Compaq]] und wurde bei dessen Übernahme durch [[Hewlett-Packard]] dort Chefwissenschaftler, ab 2003 dann Senior Fellow.<br />
<br />
Unter Tarjans 25 Doktoranden sind auch die Deutschen [[Thomas Lengauer]] und [[Monika Henzinger]].<br />
<br />
== Werk ==<br />
Er ist bekannt für die Entwicklung und Analyse von Algorithmen insbesondere für [[Graph (Graphentheorie)|Graphen]] und Netzwerke.<br />
<br />
Nach ihm sind verschiedene Algorithmen benannt:<br />
* [[Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten]]<ref>Tarjan, ''Depth-first search and linear graph algorithms'', SIAM Journal on Computing, Band 1, 1972, S. 146–160.</ref><br />
* [[Algorithmus von Hopcroft und Tarjan|Algorithmen von Hopcroft und Tarjan]]<ref>John Hopcroft, Robert Tarjan, ''Efficient planarity testing'', Journal of the Association for Computing Machinery, Band 21, 1974, S. 549–568</ref><br />
* [[Goldberg-Tarjan-Algorithmus]] zur Bestimmung eines maximalen [[Flüsse und Schnitte in Netzwerken|s-t-Flusses]]<ref>A. V. Goldberg, R. E. Tarjan, ''A new approach to the maximum-flow problem'', Journal of the ACM, Band 35, 1974, S. 921–940</ref><br />
* Von ihm stammt ein nach ihm benannter Algorithmus zur Bestimmung der [[Lowest Common Ancestor]]s zweier Knoten in einer Baumstruktur.<ref> Tarjan, Applications of path compression on balanced trees, Journal of the ACM, Band 26, 1979, S. 690–715</ref> 1983 verbesserten [[Harold N. Gabow]] und Tarjan den Algorithmus auf Ausführung in linearer Zeit.<ref>Gabow, Tarjan, A linear-time algorithm for a special case of disjoint set union, Proceedings of the 15th ACM Symposium on Theory of Computing (STOC), 1983, S. 246–251</ref><br />
<br />
Von ihm und [[Harold N. Gabow]] stammt der schnellste Algorithmus für [[Matching (Graphentheorie)|Matching]] auf gewichteten Graphen.<ref>Gabow, Tarjan, Faster scaling algorithms for general graph matching problems, Journal of the ACM, Band 38, 1991, S. 815–853</ref> Mit [[Manuel Blum]], [[Robert Floyd]], [[Vaughan Pratt]] und [[Ron Rivest]]<ref>M. Blum, R. W. Floyd, V. R. Pratt, R. Rivest, R. E. Tarjan, ''Time bounds for selection'', Journal of Computer and System Sciences, Band 7, 1973, S. 448–461.</ref> entwickelte er 1973 einen approximativen Selektionsalgorithmus (Bestimmung der k-ten kleinsten Zahl in Listen und Arrays), den ''median of median'' Algorithmus. Von ihm stammt auch eine Analyse und Schranken der Zeit-Komplexität der Algorithmen zur [[Union-Find-Struktur]].<ref>Tarjan, A class of algorithms which require nonlinear time to maintain disjoint sets, Journal of Computer and System Sciences. Band 18, Nr. 2, 1979, S. 110–127</ref><ref>R. E. Tarjan, J. van Leeuwen, "Worst-case analysis of set union algorithmsm, Journal of the ACM, Band 31, 1984, S. 245–281.</ref> Mit Andrew V. Goldberg eröffnete er 1988 einen neuen Zugang zum Problem maximaler Netzwerkflüsse.<ref>Goldberg, Tarjan, A new approach to the maximum-flow problem, Journal of the ACM, Band 35, 1988, S. 921–940</ref><br />
<br />
Mit David R. Karger und Philip Klein fand er 1995 einen randomisierten, in der Zeit linearen Algorithmus zur Bestimmung minimaler [[Spannbaum|Spannbäume]] (MST-Problem).<ref> David R. Karger, Philip N. Klein, Robert E. Tarjan, ''A randomized linear-time algorithm to find minimum spanning trees'', Journal of the ACM, Band 42, 1995, S. 321–328</ref> Er basiert auf dem [[Algorithmus von Borůvka]]. Für die Analyse von Algorithmen zu MST entwickelte er eine Färbemethode (siehe [[Algorithmus von Tarjan zur Bestimmung eines minimalen Spannbaumes]]).<br />
<br />
Daneben führte er auch die Datenstrukturen [[Fibonacci-Heap]]<ref>M. L. Fredman, R. E. Tarjan, ''Fibonacci heaps and their uses in improved network optimization algorithms'', Journal of the ACM, Band 34, 1987, S. 596–615</ref> und [[Splay-Baum]]<ref>Daniel D. Sleator, Robert Tarjan: Self-Adjusting Binary Search Trees. In: Journal of the ACM, Band 32, Nr. 3, 1985, S. 652–686</ref> ein. Fibonacci-Heaps wandte er auf die Optimierung von Netzwerkflüssen an.<br />
<br />
== Auszeichnungen ==<br />
* 1978–1979: [[Guggenheim-Stipendium]]<br />
* 1983: [[Nevanlinna-Preis]] (Preisvortrag auf dem ICM in Warschau: ''Efficient algorithms for network optimization'')<br />
* 1984: [[NAS Award for Initiatives in Research]]; [[Frederick-W.-Lanchester-Preis]]<ref name="Lanchester-Preis">{{Internetquelle|url=https://www.informs.org/Recognize-Excellence/INFORMS-Prizes-Awards/Frederick-W.-Lanchester-Prize|sprache=en|zugriff=2016-02-16|titel=Frederick W. Lanchester Prize|hrsg=informs.org ([[Institute for Operations Research and the Management Sciences]])|archiv-url=https://web.archive.org/web/20151002233807/https://www.informs.org/Recognize-Excellence/INFORMS-Prizes-Awards/Frederick-W.-Lanchester-Prize|archiv-datum=2015-10-02 }}</ref><br />
* 1985: Fellow der [[American Academy of Arts and Sciences]]<br />
* 1986: [[Turing Award]]<br />
* 1987: Member der [[National Academy of Sciences]]<br />
* 1988: Member der [[National Academy of Engineering]]<br />
* 1990: Fellow der [[American Association for the Advancement of Science]] und Member der [[American Philosophical Society]]<br />
* 1994: Fellow der [[Association for Computing Machinery|ACM]] und der [[New York Academy of Sciences]]<br />
* 1999: [[Paris Kanellakis Award]] mit Sleator für den [[Splay-Baum]]<br />
* 2004: [[Blaise-Pascal-Medaille]]<br />
* 2009: Fellow der [[Society for Industrial and Applied Mathematics]]<br />
<br />
== Schriften ==<br />
* ''Data Structures and Network Algorithms,'' CBMS 44, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983, ISBN 0-89871-187-8.<br />
* mit [[George Pólya|G. Polya]], D. R. Woods: ''Notes on Introductory Combinatorics.'' Birkhäuser, Boston, MA, 1983.<br />
<br />
== Weblinks ==<br />
{{commonscat}}<br />
* [https://www.cs.princeton.edu/~ret/ Website an der Princeton University] (englisch)<br />
* [https://scholar.google.com/citations?user=lazJixIAAAAJ&hl=en Google Scholar]<br />
<br />
== Einzelnachweise ==<br />
<references /><br />
<br />
{{Navigationsleiste Träger des Turing-Awards}}<br />
<br />
{{Normdaten|TYP=p|GND=1070878286|LCCN=n83163891|NDL=00475953|VIAF=73933029}}<br />
<br />
{{SORTIERUNG:Tarjan, Robert}}<br />
[[Kategorie:Informatiker]]<br />
[[Kategorie:Träger des Turing Award]]<br />
[[Kategorie:Mitglied der National Academy of Sciences]]<br />
[[Kategorie:Fellow der American Association for the Advancement of Science]]<br />
[[Kategorie:Mitglied der American Academy of Arts and Sciences]]<br />
[[Kategorie:Mitglied der American Philosophical Society]]<br />
[[Kategorie:Mitglied der Society for Industrial and Applied Mathematics]]<br />
[[Kategorie:Hochschullehrer (Princeton University)]]<br />
[[Kategorie:Hochschullehrer (Stanford University)]]<br />
[[Kategorie:Hochschullehrer (New York University)]]<br />
[[Kategorie:Hochschullehrer (Massachusetts Institute of Technology)]]<br />
[[Kategorie:US-Amerikaner]]<br />
[[Kategorie:Geboren 1948]]<br />
[[Kategorie:Mann]]<br />
<br />
{{Personendaten<br />
|NAME=Tarjan, Robert<br />
|ALTERNATIVNAMEN=Tarjan, Robert Endre (vollständiger Name); Tarjan, Bob (Spitzname)<br />
|KURZBESCHREIBUNG=US-amerikanischer Informatiker<br />
|GEBURTSDATUM=30. April 1948<br />
|GEBURTSORT=[[Pomona (Kalifornien)|Pomona]], [[Kalifornien]]<br />
|STERBEDATUM=<br />
|STERBEORT=<br />
}}</div>~2026-81098