Христос Пападимитриу: выдающийся ученый в области компьютерных наук.

Введение

Греческий ученый-компьютерщик (род. 1949), греческий футболист.

Христос Харилаос Пападимитриу (Χρήστος Χαρίλαος "Χρίστος" Παπαδημητρίου; родился 16 августа 1949 года) — греческий теоретик-информатик и профессор компьютерных наук в Колумбийском университете имени Донавана.

Образование

Пападимитриу учился в Национальном техническом университете Афин, где в 1972 году получил степень бакалавра в области электротехники. Затем он продолжил обучение в аспирантуре в Принстонском университете, где в 1976 году получил степень доктора философии по электротехнике и компьютерным наукам, защитив докторскую диссертацию на тему "Сложность задач комбинаторной оптимизации".

Карьера

Пападимитриу преподавал в Гарварде, МТИ, Национальном техническом университете Афин, Стэнфорде, Калифорнийском университете в Сан-Диего, Калифорнийском университете в Беркли и в настоящее время является профессором компьютерных наук имени семьи Донован в Колумбийском университете. Пападимитриу был соавтором статьи о сортировке блинов с Биллом Гейтсом, тогда ещё студентом Гарварда. Пападимитриу вспоминает: «Через два года я позвонил ему, чтобы сообщить, что наша работа была принята к публикации в хорошем математическом журнале. Он прозвучал совершенно незаинтересованно. Он переехал в Альбукерки, штат Нью-Мексико, чтобы руководить небольшой компанией, занимавшейся написанием кода для микропроцессоров, представьте себе. Я тогда подумал: «Какой блестящий парень. Какое расточительство». Эту компанию звали Microsoft. Пападимитриу является соавтором работы «Сложность вычисления равновесия Нэша» вместе со своими студентами Константиносом Даскалакисом и Полом В. Голдбергом, за которую они получили в 2008 году премию Калаи по теории игр и компьютерным наукам от Общества теории игр за «лучшую работу на стыке теории игр и компьютерных наук», в частности «за ключевой концептуальный и технический вклад»; и премию за выдающуюся работу от Общества промышленной и прикладной математики. В 2001 году Пападимитриу был принят в члены Ассоциации вычислительной техники, а в 2002 году удостоен премии Кнута. Также в 2002 году он стал членом Национальной инженерной академии США за вклад в теорию сложности, теорию баз данных и комбинаторную оптимизацию. В 2009 году он был избран в Национальную академию наук США. В ходе 36-го Международного коллоквиума по автоматике, языкам и программированию (ICALP 2009) состоялось специальное мероприятие в честь вклада Пападимитриу в компьютерную науку. В 2012 году он вместе с Элиасом Куцупиасом был удостоен премии Гёделя за их совместную работу над концепцией цены анархии. Пападимитриу является автором учебника «Вычислительная сложность», одного из наиболее широко используемых учебников в области теории вычислительной сложности. Он также является соавтором учебника «Алгоритмы» (2008) вместе с Санджоем Дашгуптой и Умешем Вазирани, а также графического романа «Логикомикс» (2009) в соавторстве с Апостолосом Доксиадисом. Его имя занимало 19-е место в академической базе данных и цифровой библиотеке поисковой системы CiteSeer.

Papadimitriou has taught at Harvard, MIT, the National Technical University of Athens, Stanford, UCSD, University of California, Berkeley and is currently the Donovan Family Professor of Computer Science at Columbia University. Papadimitriou co authored a paper on pancake sorting with Bill Gates, then a Harvard undergraduate. Papadimitriou recalled "Two years later, I called to tell him our paper had been accepted to a fine math journal. He sounded eminently disinterested. He had moved to Albuquerque, New Mexico to run a small company writing code for microprocessors, of all things. I remember thinking: 'Such a brilliant kid. What a waste.'" The company was Microsoft. Papadimitriou co authored "The Complexity of Computing a Nash Equilibrium" with his students Constantinos Daskalakis and Paul W. Goldberg, for which they received the 2008 Kalai Game Theory and Computer Science Prize from the Game Theory Society for "the best paper at the interface of game theory and computer science", in particular "for its key conceptual and technical contributions"; and the Outstanding Paper Prize from the Society for Industrial and Applied Mathematics. In 2001, Papadimitriou was inducted as a Fellow of the Association for Computing Machinery and in 2002 he was awarded the Knuth Prize. Also in 2002, he became a member of the U. S. National Academy of Engineering for contributions to complexity theory, database theory, and combinatorial optimization. In 2009 he was elected to the US National Academy of Sciences. During the 36th International Colloquium on Automata, Languages and Programming (ICALP 2009), there was a special event honoring Papadimitriou's contributions to computer science. In 2012, he, along with Elias Koutsoupias, was awarded the Gödel Prize for their joint work on the concept of the price of anarchy. Papadimitriou is the author of the textbook Computational Complexity, one of the most widely used textbooks in the field of computational complexity theory. He has also co authored the textbook Algorithms (2008) with Sanjoy Dasgupta and Umesh Vazirani, and the graphic novel Logicomix (2009) with Apostolos Doxiadis. His name was listed in the 19th position on the CiteSeer search engine academic database and digital library.

Почести и награды

В 1997 году Пападимитриу получил степень почётного доктора ETH Zurich. В 2011 году Пападимитриу получил степень почётного доктора Национального технического университета Афин. В 2013 году Пападимитриу получил степень почётного доктора École polytechnique fédérale de Lausanne (EPFL). В 2016 году Пападимитриу был удостоен медали IEEE Джона фон Неймана, в 2015 году – премии EATCS, в 2012 году – премии Гёделя, в 2004 году – премии IEEE Computer Society Charles Babbage, а в 2002 году – премии Кнута. В 2019 году он получил премию Харви Техниона/Израиля за 2018 год.

Публикации

Элементы теории вычислений (с Гарри Р. Льюисом). Prentice Hall, 1982; второе издание, сентябрь 1997 г. Греческое издание.
Комбинаторная оптимизация: алгоритмы и сложность (с Кеннетом Штейглицем). Prentice Hall, 1982; второе издание, Dover, 1998. Теория управления конкурентным доступом к базам данных. CS Press, 1986. Вычислительная сложность. Addison Wesley, 1994. Тьюринг (роман о вычислениях). MIT Press, ноябрь 2003. «Пожизненное заключение для хакеров?» (на греческом языке). Издательство Kastaniotis Editions, 2004. Сборник статей, написанных для греческой газеты To Vima. Алгоритмы (в соавторстве с Санджоем Дашгуптой и Умешем Вазирани). McGraw Hill, сентябрь 2008.
Logicomix, Эпический поиск истины (в соавторстве с Апостолосом Доксиадисом, иллюстрации Алекоса Пападатоса и Энни ди Донны). Bloomsbury Publishing и Bloomsbury USA, сентябрь 2009. Он является соавтором статьи с Биллом Гейтсом, соучредителем Microsoft, о сортировке панкейков.

Личная жизнь

В UC Berkeley в 2006 году он присоединился к группе, состоящей из профессора и аспиранта, под названием Lady X and The Positive Eigenvalues.