Яннакакис, Михалис

Поделись знанием:
(перенаправлено с «Михалис Яннакакис»)
Перейти к: навигация, поиск
Михалис Яннакакис
греч. Μιχάλης Γιαννακάκης
Дата рождения:

13 сентября 1953(1953-09-13) (70 лет)

Место рождения:

Афины, Греция

Научная сфера:

теория сложности вычислений,
базы данных

Место работы:

Колумбийский университет

Альма-матер:

Афинский национальный технический университет

Научный руководитель:

Джеффри Ульман

Награды и премии:

Bell Labs Distinguished Member of Technical Staff Award (1985)
Bell Labs President’s Gold Award (2000)
Премия Кнута (2005)

Миха́лис Яннака́кис (греч. Μιχάλης Γιαννακάκης, англ. Mihalis Yannakakis; род. 13 сентября 1953, Афины, Греция) — греческий учёный в области компьютерных наук, профессор Колумбийского университета (Нью-Йорк, США). Известен своими работами в области теории сложности вычислений, баз данных и других смежных областях. Лауреат Премии Кнута (2005).





Образование и карьера

Михалис Яннакакис родился в Афинах 13 сентября 1953 года и для раннего образования посещал Экспериментальную Гимназию Варвакио (греч. Βαρβάκειο Πειραματικό Γυμνάσιο) в Психико (Афины).

В 1975 году окончил Афинский национальный технический университет с дипломом в области электротехники, а в 1979 году получил степень доктора философии в области компьютерных наук в Принстонском университете (США). Его диссертация называлась «The Complexity of Maximum Subgraph Problems».[1]

В 1978 году Михалис Яннакакис присоединился к корпорации Лаборатории Белла (Мюррей Хилл, Нью-Джерси, США) и в 1991—2001 гг. был директором Отдела исследований основ информационных технологий. Затем он покинул Bell Laboratories и присоединился к Avaya Labs. Там Яннакакис был директором Отдела исследований основ информационных технологий до 2002 года.

В 2002 году Яннакакис занял пост профессора компьютерных наук в Стэнфордском университете, где оставался до 2003 года.

С 2004 года и по настоящее время работает профессором компьютерных наук в Колумбийском университете.

С 1992 по 2003 гг. Яннакакис работал в редакционной коллегии журнала SIAM Journal on Computing (SICOMP), в 1998-2003 гг. был его главным редактором. В 1986-2000 гг. он также работал в редакции Журнала Ассоциации вычислительной техники. Михалис Яннакакис работает в редакционных коллегиях ряда других журналов, включая Журнал компьютерных и системных наук (англ. Journal of Computer and System Sciences), Журнал комбинаторной оптимизации (англ. Journal of Combinatorial Optimization) и Журнал сложности (англ. Journal of Complexity). Он также был членом согласительных комитетов и возглавлял различные конференции, такие как ACM Symposium on Principles of Database Systems (PODS) и IEEE Symposium on Foundations of Computer Science.

По состоянию на ноябрь 2015 года, научные публикации Михалиса Яннакакиса были процитированы около 27000 раз, а его h-индекс составляет 86.[2]

Научно-исследовательская работа

Михалис Яннакакис известен благодаря вкладу в компьютерную науку, в такие области как теория сложности вычислений, теория баз данных, автоматизированная верификация и тестирование, а также алгоритмическая теория графов.

Особое место среди ценных достижений учёного в сфере теории сложности занимают две ключевые работы на темы теории вероятностно проверяемых доказательств и сложности аппроксимации. В 1988 году, на ежегодном, финансируемом Ассоциацией вычислительной техники (АВТ) симпозиуме по теории вычислений, Михалис Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP (является подклассом Max-NP), содержащих ряд интересных задач оптимизации. Яннакакис и Пападимитриу показали, что эти задачи имеют некоторую ограниченную ошибку. С помощью этих выводов стало возможным объяснить замеченное в научно-исследовательском сообществе отсутствие прогресса в изучении аппроксимируемости целого ряда задач оптимизации, в том числе задачи «3-выполнимость», задачи о независимом множестве, а также задачи коммивояжёра.[3]

В 1993 году, на очередном симпозиуме АВТ по теории вычислений, Михалис Яннакакис и Карстен Лунд представили ряд важных выводов относительно вопросов вычислений аппроксимаций. Эти результаты показали трудность эффективного вычисления приближенных решений ряда задач минимизации, таких как случай раскраски графов и задача о покрытии множества. Учитывая маловероятность того, что такие NP-трудные задачи будут разрешены оптимальным образом за полиномиальное время, было осуществлено много попыток разработать для них эффективные приближенные решения. Результаты, полученные Яннакакисом и Карстеном, доказали низкую вероятность достижения этой цели.[4]

В области теории баз данных основной вклад Михалиса Яннакакиса состоит в инициировании исследований ациклических баз данных и недвухфазного блокирования. Ациклические схемы базы данных - это схемы, содержащие одну ациклическую зависимость соединения и набор функциональных зависимостей.[5] Ряд исследователей, в том числе Яннакакис, отметили пригодность этих схем, продемонстрировав множество полезных свойств, которые они имеют: возможность решения многих задач, основанных на ациклических схемах за полиномиальное время, несмотря на то, что задача могла быть NP-полной для других схем.[6]

Награды и премии

Удостоен Премии Кнута (2005) за значимость, влияние и поразительную степень его вклада в теоретические основы вычислительной техники, а также стал обладателем двух наград от Bell Labs: Distinguished Member of Technical Staff Award (1985) и President’s Gold Award (2000). Является членом Ассоциации вычислительной техники и исследовательского центра Лаборатории Белла.

Напишите отзыв о статье "Яннакакис, Михалис"

Примечания

  1. [genealogy.math.ndsu.nodak.edu/id.php?id=82072 The Mathematics Genealogy Project - Mihalis Yannakakis] (accessed 9 December 2009)
  2. [scholar.google.com/citations?user=_pPy-pAAAAAJ&hl=en Googel Scholar Record of M. Yannakakis].
  3. Christos Papadimitriou , Mihalis Yannakakis, Optimization, approximation, and complexity classes, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.229-234, 2–4 May 1988.
  4. Carsten Lund , Mihalis Yannakakis, On the hardness of approximating minimization problems, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.286-293, 16–18 May 1993.
  5. Catriel Beeri , Ronald Fagin , David Maier , Alberto Mendelzon , Jeffrey Ullman , Mihalis Yannakakis, Properties of acyclic database schemes, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.355-362, 11–13 May 1981.
  6. Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983.

Ссылки

  • [datascience.columbia.edu/mihalis-yannakakis-0 Data Science Institute]
  • [www1.cs.columbia.edu/~mihalis/ Mihalis Yannakakis]

Отрывок, характеризующий Яннакакис, Михалис

– Отчего ж… – рассеянно отвечал Долохов, вглядываясь в лицо французского барабанщика.
– Давно у тебя молодчик этот? – спросил он у Денисова.
– Нынче взяли, да ничего не знает. Я оставил его пг'и себе.
– Ну, а остальных ты куда деваешь? – сказал Долохов.
– Как куда? Отсылаю под г'асписки! – вдруг покраснев, вскрикнул Денисов. – И смело скажу, что на моей совести нет ни одного человека. Разве тебе тг'удно отослать тг'идцать ли, тг'иста ли человек под конвоем в гог'од, чем маг'ать, я пг'ямо скажу, честь солдата.
– Вот молоденькому графчику в шестнадцать лет говорить эти любезности прилично, – с холодной усмешкой сказал Долохов, – а тебе то уж это оставить пора.
– Что ж, я ничего не говорю, я только говорю, что я непременно поеду с вами, – робко сказал Петя.
– А нам с тобой пора, брат, бросить эти любезности, – продолжал Долохов, как будто он находил особенное удовольствие говорить об этом предмете, раздражавшем Денисова. – Ну этого ты зачем взял к себе? – сказал он, покачивая головой. – Затем, что тебе его жалко? Ведь мы знаем эти твои расписки. Ты пошлешь их сто человек, а придут тридцать. Помрут с голоду или побьют. Так не все ли равно их и не брать?
Эсаул, щуря светлые глаза, одобрительно кивал головой.
– Это все г'авно, тут Рассуждать нечего. Я на свою душу взять не хочу. Ты говог'ишь – помг'ут. Ну, хог'ошо. Только бы не от меня.
Долохов засмеялся.
– Кто же им не велел меня двадцать раз поймать? А ведь поймают – меня и тебя, с твоим рыцарством, все равно на осинку. – Он помолчал. – Однако надо дело делать. Послать моего казака с вьюком! У меня два французских мундира. Что ж, едем со мной? – спросил он у Пети.
– Я? Да, да, непременно, – покраснев почти до слез, вскрикнул Петя, взглядывая на Денисова.
Опять в то время, как Долохов заспорил с Денисовым о том, что надо делать с пленными, Петя почувствовал неловкость и торопливость; но опять не успел понять хорошенько того, о чем они говорили. «Ежели так думают большие, известные, стало быть, так надо, стало быть, это хорошо, – думал он. – А главное, надо, чтобы Денисов не смел думать, что я послушаюсь его, что он может мной командовать. Непременно поеду с Долоховым во французский лагерь. Он может, и я могу».
На все убеждения Денисова не ездить Петя отвечал, что он тоже привык все делать аккуратно, а не наобум Лазаря, и что он об опасности себе никогда не думает.
– Потому что, – согласитесь сами, – если не знать верно, сколько там, от этого зависит жизнь, может быть, сотен, а тут мы одни, и потом мне очень этого хочется, и непременно, непременно поеду, вы уж меня не удержите, – говорил он, – только хуже будет…


Одевшись в французские шинели и кивера, Петя с Долоховым поехали на ту просеку, с которой Денисов смотрел на лагерь, и, выехав из леса в совершенной темноте, спустились в лощину. Съехав вниз, Долохов велел сопровождавшим его казакам дожидаться тут и поехал крупной рысью по дороге к мосту. Петя, замирая от волнения, ехал с ним рядом.
– Если попадемся, я живым не отдамся, у меня пистолет, – прошептал Петя.
– Не говори по русски, – быстрым шепотом сказал Долохов, и в ту же минуту в темноте послышался оклик: «Qui vive?» [Кто идет?] и звон ружья.
Кровь бросилась в лицо Пети, и он схватился за пистолет.
– Lanciers du sixieme, [Уланы шестого полка.] – проговорил Долохов, не укорачивая и не прибавляя хода лошади. Черная фигура часового стояла на мосту.
– Mot d'ordre? [Отзыв?] – Долохов придержал лошадь и поехал шагом.
– Dites donc, le colonel Gerard est ici? [Скажи, здесь ли полковник Жерар?] – сказал он.
– Mot d'ordre! – не отвечая, сказал часовой, загораживая дорогу.
– Quand un officier fait sa ronde, les sentinelles ne demandent pas le mot d'ordre… – крикнул Долохов, вдруг вспыхнув, наезжая лошадью на часового. – Je vous demande si le colonel est ici? [Когда офицер объезжает цепь, часовые не спрашивают отзыва… Я спрашиваю, тут ли полковник?]
И, не дожидаясь ответа от посторонившегося часового, Долохов шагом поехал в гору.
Заметив черную тень человека, переходящего через дорогу, Долохов остановил этого человека и спросил, где командир и офицеры? Человек этот, с мешком на плече, солдат, остановился, близко подошел к лошади Долохова, дотрогиваясь до нее рукою, и просто и дружелюбно рассказал, что командир и офицеры были выше на горе, с правой стороны, на дворе фермы (так он называл господскую усадьбу).
Проехав по дороге, с обеих сторон которой звучал от костров французский говор, Долохов повернул во двор господского дома. Проехав в ворота, он слез с лошади и подошел к большому пылавшему костру, вокруг которого, громко разговаривая, сидело несколько человек. В котелке с краю варилось что то, и солдат в колпаке и синей шинели, стоя на коленях, ярко освещенный огнем, мешал в нем шомполом.
– Oh, c'est un dur a cuire, [С этим чертом не сладишь.] – говорил один из офицеров, сидевших в тени с противоположной стороны костра.
– Il les fera marcher les lapins… [Он их проберет…] – со смехом сказал другой. Оба замолкли, вглядываясь в темноту на звук шагов Долохова и Пети, подходивших к костру с своими лошадьми.
– Bonjour, messieurs! [Здравствуйте, господа!] – громко, отчетливо выговорил Долохов.
Офицеры зашевелились в тени костра, и один, высокий офицер с длинной шеей, обойдя огонь, подошел к Долохову.
– C'est vous, Clement? – сказал он. – D'ou, diable… [Это вы, Клеман? Откуда, черт…] – но он не докончил, узнав свою ошибку, и, слегка нахмурившись, как с незнакомым, поздоровался с Долоховым, спрашивая его, чем он может служить. Долохов рассказал, что он с товарищем догонял свой полк, и спросил, обращаясь ко всем вообще, не знали ли офицеры чего нибудь о шестом полку. Никто ничего не знал; и Пете показалось, что офицеры враждебно и подозрительно стали осматривать его и Долохова. Несколько секунд все молчали.
– Si vous comptez sur la soupe du soir, vous venez trop tard, [Если вы рассчитываете на ужин, то вы опоздали.] – сказал с сдержанным смехом голос из за костра.
Долохов отвечал, что они сыты и что им надо в ночь же ехать дальше.
Он отдал лошадей солдату, мешавшему в котелке, и на корточках присел у костра рядом с офицером с длинной шеей. Офицер этот, не спуская глаз, смотрел на Долохова и переспросил его еще раз: какого он был полка? Долохов не отвечал, как будто не слыхал вопроса, и, закуривая коротенькую французскую трубку, которую он достал из кармана, спрашивал офицеров о том, в какой степени безопасна дорога от казаков впереди их.
– Les brigands sont partout, [Эти разбойники везде.] – отвечал офицер из за костра.
Долохов сказал, что казаки страшны только для таких отсталых, как он с товарищем, но что на большие отряды казаки, вероятно, не смеют нападать, прибавил он вопросительно. Никто ничего не ответил.
«Ну, теперь он уедет», – всякую минуту думал Петя, стоя перед костром и слушая его разговор.
Но Долохов начал опять прекратившийся разговор и прямо стал расспрашивать, сколько у них людей в батальоне, сколько батальонов, сколько пленных. Спрашивая про пленных русских, которые были при их отряде, Долохов сказал: