Михалис Яннакакис
Михалис Яннакакис | |
|---|---|
 Михалис Яннакакис | |
| Рожденный | 13 сентября 1953 г. |
| Национальность | Греческий - Американский |
| Альма-матер | Национальный технический университет Афин Принстонский университет |
| Награды | Премия Кнута (2005) |
| Научная карьера | |
| Поля | Информатика |
| Учреждения | Колумбийский университет |
| Докторантура | Джеффри Уллман |
Михалис Яннакакис ( греч . Михалис Гианнакакис ; родился 13 сентября 1953 года в Афинах , Греция ) [1] — профессор информатики в Колумбийском университете . Он известен своей работой в области вычислительной сложности , баз данных и других смежных областях. Он выиграл премию Дональда Э. Кнута в 2005 году. [2] [3]
Образование и карьера [ править ]
Яннакакис родился в Афинах, Греция, в 1953 году и учился в средней школе Варвакейо , где получил начальное образование. Он окончил Афинский национальный технический университет в 1975 году по специальности «инженер-электрик», а затем получил степень доктора компьютерных наук в Принстонском университете в 1979 году. [1] Его диссертация называлась «Сложность задач о максимальном подграфе». [4]
В 1978 году он присоединился к Bell Laboratories и занимал должность директора отдела исследований принципов вычислений с 1991 по 2001 год, когда он покинул Bell Laboratories и присоединился к Avaya Laboratories. Там он занимал должность директора отдела исследований принципов вычислений до 2002 года. [1]
В 2002 году он поступил в Стэнфордский университет , где был профессором информатики, а в 2003 году ушел, чтобы поступить в Колумбийский университет в 2004 году, где в настоящее время работает профессором Перси К. и Виды Л.В. Хадсон . компьютерных наук [1]
С 1992 по 2003 год Яннакакис входил в редакционную коллегию журнала SIAM Journal on Computing и был главным редактором с 1998 по 2003 год. Он также был членом редакционной коллегии журнала ACM с 1986 по 2000 год. [1] Другие члены редакционного совета включают Журнал компьютерных и системных наук , Журнал комбинаторной оптимизации и Журнал сложности . Он также работал в комитетах конференций и возглавлял различные конференции, такие как Симпозиум ACM по принципам систем баз данных и Симпозиум IEEE по основам компьютерных наук . [1]
По состоянию на июнь 2020 года его публикации цитировались около 35 000 раз, а его индекс Хирша составил 93. [5]
Исследования [ править ]
Яннакакис известен своим вкладом в информатику в области теории сложности вычислений , теории баз данных , компьютерной верификации и тестирования, а также алгоритмической теории графов .
Среди его вкладов в теорию сложности — две статьи о теории PCP и о сложности аппроксимации .На ежегодном симпозиуме ACM по теории вычислений 1988 года Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP. Max-NP и Max-SNP (который является подклассом Max-NP) содержат ряд интересных задач оптимизации, и Яннакакис и Пападимитриу показали, что эти задачи имеют некоторую ограниченную ошибку. Эти результаты смогли объяснить отсутствие прогресса, наблюдавшегося в исследовательском сообществе в отношении аппроксимируемости ряда задач оптимизации, включая 3SAT , задачу независимого множества и задачу коммивояжера . [6]
Яннакакис и Карстен Лунд представили ряд результатов, касающихся сложности вычислительных аппроксимаций, на ежегодном симпозиуме ACM по теории вычислений в 1993 году. Эти результаты продемонстрировали сложность эффективного вычисления приближенных решений ряда задач минимизации, таких как раскраска графов и покрытие множеств. . Учитывая маловероятный сценарий того, что NP-сложные задачи, такие как раскраска графов и покрытие множеств, будут решены оптимально за полиномиальное время , было предпринято много попыток разработать для них эффективные аппроксимационные решения; результаты, полученные Яннакакисом и Карстеном, доказали маловероятность решения этой задачи. [7]
В области теории баз данных его вклад включает начало изучения ациклических схем баз данных, ациклических конъюнктивных запросов и недвухфазных блокировок. Ациклические схемы базы данных — это схемы, которые содержат одну зависимость ациклического соединения (зависимость соединения — это связь, управляющая объединением таблиц базы данных) и набор функциональных зависимостей; [8] ряд исследователей, в том числе Яннакакис, указали на полезность этих схем, продемонстрировав множество полезных свойств, которыми они обладали: например, способность решать многие проблемы, основанные на ациклических схемах, за полиномиальное время, тогда как проблема легко могла быть NP- полный для других схем. [9]
Что касается не двухфазной блокировки , Яннакакис продемонстрировал, как знания о структуре базы данных и формах различных транзакций, выполняемых в ней, могут быть использованы для определения того, безопасна ли конкретная политика блокировки или нет. Обычно используемые политики двухфазной блокировки (2PL) состоят из двух этапов – для блокировки и разблокировки объектов соответственно – и чтобы избежать такой политики, необходимо наложить некоторую структуру на объекты базы данных; Результаты Яннакакиса показывают, как при выборе гиперграфа , напоминающего структуру ограничений согласованности базы данных, политика блокировки, которая посещает объекты по путям этого гиперграфа, будет безопасной. Такая политика не обязательно должна быть двухфазной, и эти политики могут быть классифицированы в соответствии с связностью вышеупомянутого гиперграфа, причем политики 2PL являются лишь одним из них. [10] Яннакакис далее показал, что для естественного класса политик безопасной блокировки (L-политик) свобода от взаимоблокировок определяется исключительно порядком, в котором транзакции получают доступ к объектам, и из этого выведены простые условия, которые гарантировали бы свободу от взаимоблокировок для L-политика. [11]
Он также внес свой вклад в область компьютерной проверки и тестирования, где заложил строгие алгоритмические и теоретические основы этой области. Некоторые из его вкладов включают разработку алгоритмов с эффективным использованием памяти для проверки временных свойств программ с конечным числом состояний. [12] определение сложности проверки того, удовлетворяют ли программы своим спецификациям, выраженным во линейного времени временной логике , [13] и проверка того, что модель с временными ограничениями удовлетворяет заданному временному свойству. [14] Вместе с Алексом Гросом и Дороном Пеледом он представил адаптивную проверку модели, показав, что при наличии несоответствий между системой и соответствующей моделью результаты проверки можно использовать для улучшения модели. [15] Он также внес вклад в исследование диаграмм последовательности сообщений (MSC), где было показано, что слабая реализуемость неразрешима для ограниченных MSC-графов и что безопасная реализуемость находится в EXPSPACE , а также другие интересные результаты, связанные с проверкой MSC-графов. . [16]
Награды и признание [ править ]
Яннакакис является членом Национальной инженерной академии и Национальной академии наук . Он был удостоен седьмой премии Кнута за вклад в теоретическую информатику. [3] Он также был награжден премией «Выдающийся технический персонал Bell Labs» и золотой наградой президента Bell Labs в 1985 и 2000 годах соответственно. Он является членом ACM, а также членом Bell Laboratories . [1] В 2020 году он был избран членом Американской академии искусств и наук (AAAS) . [17]
Ссылки [ править ]
- ↑ Перейти обратно: Перейти обратно: а б с д и ж г Колумбийский университет: резюме: Михалис Яннакакис (по состоянию на 12 ноября 2009 г.)
- ^ Премия Кнута 2005 г. Михалиса Яннакакиса , ACM, 1 мая 2006 г.
- ↑ Перейти обратно: Перейти обратно: а б Премия Кнута
- ^ Проект математической генеалогии - Михалис Яннакакис (по состоянию на 9 декабря 2009 г.)
- ^ "Запись Google Scholar М. Яннакакиса" .
- ^ Христос Пападимитриу, Михалис Яннакакис, Классы оптимизации, аппроксимации и сложности, Труды двадцатого ежегодного симпозиума ACM по теории вычислений, стр. 229–234, 2–4 мая 1988 г.
- ^ Карстен Лунд, Михалис Яннакакис, О сложности аппроксимации задач минимизации, Труды двадцать пятого ежегодного симпозиума ACM по теории вычислений, стр. 286–293, 16–18 мая 1993 г.
- ^ Катриэль Бери, Рональд Феджин, Дэвид Майер, Альберто Мендельзон, Джеффри Ульман, Михалис Яннакакис, Свойства ациклических схем баз данных, Труды тринадцатого ежегодного симпозиума ACM по теории вычислений, стр. 355–362, 11–13 мая 1981 г.
- ^ Катриэль Бири, Рональд Феджин, Дэвид Майер, Михалис Яннакакис, О желательности ациклических схем баз данных, Журнал ACM, т.30, №3, стр. 479–513, июль 1983 г.
- ^ Михалис Яннакакис, Теория политик безопасной блокировки в системах баз данных, Журнал ACM, т. 29, № 3, стр. 718–740, июль 1982 г.
- ^ Михалис Яннакакис, Свобода от тупиков политики безопасной блокировки, SIAM J. on Computing 11 (1982), 391-408.
- ^ К. Куркубетис, М. Варди, П. Вольпер, М. Яннакакис, Алгоритмы с эффективным использованием памяти для проверки временных свойств, Формальные методы проектирования систем, т.1, № 2-3, стр. 275–288, октябрь 1992.
- ^ Костас Куркубетис, Михалис Яннакакис, Сложность вероятностной проверки, Журнал ACM, т. 42, № 4, стр. 857–907, июль 1995 г.
- ^ Р. Алур, А. Итай, Р. П. Куршан, М. Яннакакис, Проверка синхронизации методом последовательного приближения, Информация и вычисления, т. 118, № 1, стр. 142–157, апрель 1995 г.
- ^ Грос А., Пелед Д. и Яннакакис М. 2002. Проверка адаптивной модели. В материалах 8-й международной конференции по инструментам и алгоритмам построения и анализа систем (8–12 апреля 2002 г.). Дж. Катоен и П. Стивенс, ред. Конспекты лекций по информатике, том. 2280. Спрингер-Верлаг, Лондон, 357–370.
- ^ Раджив Алур, Куша Этессами, Михалис Яннакакис, Реализуемость и проверка графов MSC, Theoretical Computer Science, v.331 n.1, стр. 97–114, 15 февраля 2005 г.
- ^ «Избраны стипендиаты AAAS» (PDF) . Уведомления Американского математического общества .
Внешние ссылки [ править ]
- 1953 года рождения
- Живые люди
- Греческие ученые-компьютерщики
- Американские ученые-компьютерщики
- Факультет Колумбийской школы инженерии и прикладных наук
- Лауреаты премии Кнута
- 1998 г. Члены Ассоциации вычислительной техники.
- Теоретики-компьютерщики
- Выпускники Афинского национального технического университета
- Греческие ученые
- Члены Национальной инженерной академии США
- Члены Национальной академии наук США
- Люди из Афин