Михалис Яннакакис | |
---|---|
греч. Μιχάλης Γιαννακάκης | |
| |
Дата рождения | 13 сентября 1953 (65 лет) |
Место рождения | Афины, Греция |
Страна | |
Научная сфера |
теория сложности вычислений, базы данных |
Место работы |
|
Альма-матер | Афинский национальный технический университет |
Научный руководитель | Джеффри Ульман |
Награды и премии |
Bell Labs Distinguished Member of Technical Staff Award (1985) Bell Labs President’s Gold Award (2000) Премия Кнута (2005) |
Миха́лис Яннака́кис (греч. Μιχάλης Γιαννακάκης, англ. Mihalis Yannakakis; род. 13 сентября 1953, Афины, Греция) — греческий учёный в области компьютерных наук, профессор Колумбийского университета (Нью-Йорк, США). Известен своими работами в области теории сложности вычислений, баз данных и других смежных областях. Лауреат Премии Кнута (2005). Член Национальной академии наук США (2018)[1].
Михалис Яннакакис родился в Афинах 13 сентября 1953 года и для раннего образования посещал Экспериментальную Гимназию Варвакио (греч. Βαρβάκειο Πειραματικό Γυμνάσιο) в Психико (Афины).
В 1975 году окончил Афинский национальный технический университет с дипломом в области электротехники, а в 1979 году получил степень доктора философии в области компьютерных наук в Принстонском университете (США). Его диссертация называлась «The Complexity of Maximum Subgraph Problems».[2]
В 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.[3]
Михалис Яннакакис известен благодаря вкладу в компьютерную науку, в такие области как теория сложности вычислений, теория баз данных, автоматизированная верификация и тестирование, а также алгоритмическая теория графов.
Особое место среди ценных достижений учёного в сфере теории сложности занимают две ключевые работы на темы теории вероятностно проверяемых доказательств и сложности аппроксимации. В 1988 году, на ежегодном, финансируемом Ассоциацией вычислительной техники (АВТ) симпозиуме по теории вычислений, Михалис Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP (является подклассом Max-NP), содержащих ряд интересных задач оптимизации. Яннакакис и Пападимитриу показали, что эти задачи имеют некоторую ограниченную ошибку. С помощью этих выводов стало возможным объяснить замеченное в научно-исследовательском сообществе отсутствие прогресса в изучении аппроксимируемости целого ряда задач оптимизации, в том числе задачи «3-выполнимость», задачи о независимом множестве, а также задачи коммивояжёра.[4]
В 1993 году, на очередном симпозиуме АВТ по теории вычислений, Михалис Яннакакис и Карстен Лунд представили ряд важных выводов относительно вопросов вычислений аппроксимаций. Эти результаты показали трудность эффективного вычисления приближенных решений ряда задач минимизации, таких как случай раскраски графов и задача о покрытии множества. Учитывая маловероятность того, что такие NP-трудные задачи будут разрешены оптимальным образом за полиномиальное время, было осуществлено много попыток разработать для них эффективные приближённые решения. Результаты, полученные Яннакакисом и Карстеном, доказали низкую вероятность достижения этой цели.[5]
В области теории баз данных основной вклад Михалиса Яннакакиса состоит в инициировании исследований ациклических баз данных и недвухфазного блокирования. Ациклические схемы базы данных - это схемы, содержащие одну ациклическую зависимость соединения и набор функциональных зависимостей.[6] Ряд исследователей, в том числе Яннакакис, отметили пригодность этих схем, продемонстрировав множество полезных свойств, которые они имеют: возможность решения многих задач, основанных на ациклических схемах за полиномиальное время, несмотря на то, что задача могла быть NP-полной для других схем.[7]
Удостоен Премии Кнута (2005) за значимость, влияние и поразительную степень его вклада в теоретические основы вычислительной техники, а также стал обладателем двух наград от Bell Labs: Distinguished Member of Technical Staff Award (1985) и President’s Gold Award (2000). Является членом Ассоциации вычислительной техники и исследовательского центра Лаборатории Белла.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .