Quelltext der Seite Christos Papadimitriou

{{Dieser Artikel|behandelt den griechischen Informatiker Christos Papadimitriou; zum gleichnamigen Fußballspieler siehe [[Christos Papadimitriou (Fußballspieler)]].}}
'''Christos Charilaos Papadimitriou''' ({{elS|Χρήστος Χαρίλαος Παπαδημητρίου}}) (* [[1949]] in [[Athen]]) ist ein [[Griechenland|griechischer]] [[Informatik]]er.
[[Datei:Christos Papadimitriou mg 7721-b.cr2.jpg|miniatur|Papadimitriou 2009]]

== Werdegang und Forschung ==
Papadimitriou machte 1972 sein Diplom in [[Elektrotechnik]] an der [[Nationale Technische Universität Athen|Nationalen Technischen Universität]] in [[Athen]] und studierte dann an der [[Princeton University]], wo er 1974 seinen Master-Abschluss machte und 1976 [[Promotion (Doktor)|promoviert]] wurde.<ref>{{MathGenealogyProject|id=46289|name=Christos Charilaos Papadimitriou}} abgerufen am 6. September 2024.</ref> Danach lehrte er an der [[Harvard University]], der TU Athen, am [[Massachusetts Institute of Technology]] (MIT), der [[Stanford University]] sowie der [[University of California, San Diego]] (UCSD). Ab 1996 war er Professor an der [[University of California, Berkeley]], wo er schon 1978 als ''Miller Fellow'' war.

Papadimitriou befasst sich mit [[Komplexitätstheorie]], [[Algorithmus|Algorithmentheorie]], [[Datenbank]]en, [[Künstliche Intelligenz|Künstlicher Intelligenz]], [[Optimierung]], [[Spieltheorie]], Netzwerktheorie sowie Evolutionstheorie unter informationstheoretischen Aspekten. Mit [[Mihalis Yannakakis]] führte er 1988 neue [[Komplexitätsklasse]]n ein (''Max-NP'' und dessen Unterklasse ''Max-SNP''), zu denen auch bekannte Probleme wie das [[Problem des Handlungsreisenden]] und [[3-SAT]] gehören.<ref>Papadimitriou, Yannakakis: ''Optimization, approximation, and complexity classes'', Proceedings of the 20th annual ACM symposium on Theory of computing, Mai 1988, S.&nbsp;229–234</ref>

2001 wurde er Fellow der [[Association for Computing Machinery]] (ACM) sowie der [[American Academy of Arts and Sciences]].<ref>{{Internetquelle|url=https://www.amacad.org/publications/BookofMembers/ChapterP.pdf|titel=Book of Members|autor=|hrsg=|werk=|datum=|sprache=en|zugriff=2016-07-27}}</ref> Er ist Fellow der [[National Academy of Engineering]] und der [[National Academy of Sciences]] (2009) sowie auswärtiges Mitglied der [[Academia Europaea]] (2006).

Für seine Arbeiten wurde Papadimitriou mehrfach ausgezeichnet. 2002 erhielt er den [[Knuth-Preis]], 2008 zusammen mit [[Paul W. Goldberg]] und [[Constantinos Daskalakis]] den [[Kalai-Preis]] der [[Game Theory Society]]. 2012 erhielt er den [[Gödel-Preis]] mit seinem Doktoranden [[Elias Koutsoupias]] für Arbeiten zur Algorithmischen Spieltheorie, speziell des ''Price of Anarchy'' Konzepts in ihrem Aufsatz ''Worst-Case Equilibria''. 2015 wurde er mit dem [[EATCS-Award]] ausgezeichnet. Für 2016 wurde ihm die [[IEEE John von Neumann Medal]] zugesprochen und für 2018 der [[Harvey-Preis]],<ref>[https://www.technion.ac.il/en/2019/10/technion-to-award-harvey-prize/ Harvey-Preis 2018]</ref> für 2022 der [[Computer Pioneer Award]] und für 2023 der [[John-von-Neumann-Theorie-Preis]].

Mit seinem Doktoranden [[Constantinos Daskalakis]] (2018 Gewinner des [[Nevanlinna-Preis]]es) wandte er Komplexitätstheorie auf die Berechnung des [[Nash-Gleichgewicht]]s in der Spieltheorie (und den Wirtschaftswissenschaften) an. 

1979 veröffentlichte er eine Arbeit zusammen mit [[Bill Gates]] über das [[Pfannkuchen-Sortierproblem]].<ref>''Bounds for sorting by prefix reversal'', Discrete Mathematics, Band 27, 1979, S.&nbsp;47–57.</ref> Er spielt Keyboard und singt in einer Campus-Rockband in Berkeley (''Lady X and the Positive Eigenvalues''), schrieb einen Roman und einen Comic (mit [[Apostolos Doxiadis]]) und veröffentlichte eine Sammlung seiner Artikel in der griechischen Tageszeitung [[To Vima]].<ref>''Lebenslang für Hacker?'', Kastaniotis Verlag 2004 (griechisch)</ref>

== Schriften ==
* mit Harry R. Lewis: ''Elements of the theory of computation'', Prentice-Hall 1982, 2.&nbsp;Auflage 1997
* mit Kenneth Steiglitz: ''Combinatorial Optimization'', Prentice Hall 1982, Dover 1998
* ''Computational Complexity'', Addison-Wesley 1994
* mit Sanjoy Dasgupta, [[Umesh Vazirani]]: ''Algorithms'', McGraw Hill 2006
* ''The theory of database concurrency control'', Computer Science Press 1986
* ''Turing—a novel about computation'', MIT Press
* mit [[Apostolos Doxiadis]], [[Alecos Papadatos]], Annie di Donna: ''Logicomix : eine epische Suche nach Wahrheit''. Aus dem Engl. von Ebi Naumann. Zürich : Atrium-Verlag, 2012
*mit Elias Koutsoupias: Worst-case equilibria, Computer Science Review, Band 3, 2009, S. 65–69
*mit Koutsoupias: Worst-case equilibria, Proceedings of the 16th annual conference on Theoretical aspects of computer science, 1999, 404–413
*mit Koutsoupias: On the k-server conjecture, Journal of the ACM, Band 43, 1995, S. 971–983
*mit Koutsoupias: Beyond competitive analysis, SIAM Journal on Computing Band 30, 2000, S. 300–317

== Weblinks ==
{{Commonscat}}
* {{DNB-Portal|135731909}}
* [http://www.cs.berkeley.edu/~christos/ Homepage]
* [https://zbmath.org/authors/papadimitriou.christos-h Christos Harilaos Papadimitriou] in der Datenbank [[zbMATH]]

== Einzelnachweise ==
<references />

{{Normdaten|TYP=p|GND=135731909|LCCN=n80102786|VIAF=37007186}}

{{SORTIERUNG:Papadimitriou, Christos}}
[[Kategorie:Informatiker]]
[[Kategorie:Mathematiker (20. Jahrhundert)]]
[[Kategorie:Hochschullehrer (University of California, Berkeley)]]
[[Kategorie:Hochschullehrer (University of California, San Diego)]]
[[Kategorie:Mitglied der Academia Europaea]]
[[Kategorie:Mitglied der American Academy of Arts and Sciences]]
[[Kategorie:Mitglied der National Academy of Sciences]]
[[Kategorie:Mitglied der Association for Computing Machinery]]
[[Kategorie:Mitglied der National Academy of Engineering]]
[[Kategorie:Griechischer Emigrant in den Vereinigten Staaten]]
[[Kategorie:Grieche]]
[[Kategorie:Geboren 1949]]
[[Kategorie:Mann]]

{{Personendaten
|NAME=Papadimitriou, Christos
|ALTERNATIVNAMEN=Papadimitriou, Christos Charilaos (vollständiger Name); Παπαδημητρίου, Χρήστος Χαρίλαος (griechisch)
|KURZBESCHREIBUNG=griechischer Informatiker
|GEBURTSDATUM=1949
|GEBURTSORT=[[Athen]]
|STERBEDATUM=
|STERBEORT=
}}