Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Михалис Яннакакис
Михалис Яннакакис 2006.jpg
Михалис Яннакакис
Рожденный( 1953-09-13 )13 сентября 1953 г. (67 лет)
Афины , Греция
НациональностьГреческий - Американский
Альма-матерНациональный технический университет Афин
Принстонский университет
НаградыПриз Кнута (2005)
Научная карьера
ПоляИнформатика
УчрежденияКолумбийский университет
ДокторантДжеффри Уллман

Михалис Яннакакис ( греч . Μιχάλης Γιαννακάκης ; родился 13 сентября 1953 года в Афинах , Греция ) [1] - профессор компьютерных наук Колумбийского университета . Он известен своей работой в области вычислительной сложности , баз данных и других смежных областях. В 2005 году он выиграл премию Дональда Э. Кнута [2].

Образование и карьера [ править ]

Яннакакис родился в Афинах, Греция, в 1953 году и посещал среднюю школу Варвакейо для получения начального образования. В 1975 году он окончил Афинский национальный технический университет по специальности «Электротехника», а затем получил степень доктора философии. Кандидат компьютерных наук в Принстонском университете в 1979 году. [1] Его диссертация была озаглавлена ​​«Сложность задач о максимальном подграфе». [3]

В 1978 году он присоединился к Bell Laboratories и занимал должность директора исследовательского отдела вычислительных принципов с 1991 по 2001 год, когда он покинул лаборатории Bell и присоединился к 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. [4]

Исследование [ править ]

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

Среди его вкладов в теорию сложности - две статьи о теории PCP и о сложности аппроксимации . На ежегодном симпозиуме ACM по теории вычислений 1988 года Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP. Max-NP и Max-SNP (который является подклассом Max-NP) содержат ряд интересных задач оптимизации, и Яннакакис и Пападимитриу показали, что эти проблемы имеют некоторую ограниченную ошибку. Эти результаты смогли объяснить отсутствие прогресса, наблюдаемого в исследовательском сообществе в отношении аппроксимации ряда задач оптимизации, включая 3SAT , проблему независимого множества., и задача коммивояжера . [5]

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

В области теории баз данных он внес свой вклад в изучение ациклических баз данных и недвухфазной блокировки. Схемы ациклической базы данных - это схемы, которые содержат одну ациклическую зависимость соединения ( зависимость соединения - это связь, управляющую соединением таблиц базы данных) и набор функциональных зависимостей; [7] ряд исследователей, в том числе Яннакакис, указали на полезность этих схем, продемонстрировав множество полезных свойств, которыми они обладали: например, способность решать многие задачи, основанные на ациклических схемах, за полиномиальное время, в то время как задача могла легко иметь NP-полная для других схем. [8]

Что касается недвухфазной блокировки , Яннакакис продемонстрировал, как знания о структуре базы данных и формах различных транзакций, выполняемых с ней, могут быть использованы для определения того, является ли конкретная политика блокировки безопасной или нет. Обычно используемые политики двухфазной блокировки (2PL) состоят из двух этапов - для блокировки и разблокировки объектов соответственно - и чтобы избежать такой политики, необходимо наложить некоторую структуру на объекты базы данных; Результаты Яннакакиса показывают, как, выбирая гиперграф,напоминая структуру ограничений согласованности базы данных, политика блокировки, которая посещает объекты по путям этого гиперграфа, будет безопасной. Такая политика не обязательно должна быть двухэтапной, и эти политики можно классифицировать в соответствии с возможностью подключения вышеупомянутого гиперграфа, причем политики 2PL являются лишь одним из них. [9] Яннакакис далее показал, что для естественного класса политик безопасной блокировки (L-политики) свобода от тупиковых ситуаций определяется исключительно порядком, в котором к объектам обращаются транзакции, и из этого выведены простые условия, которые гарантируют свободу. из тупиков для L-политики. [10]

Он также внес свой вклад в область компьютерной проверки и тестирования, где заложил строгие алгоритмические и теоретико-сложные основы этой области. Некоторые из его вкладов включают разработку эффективных алгоритмов памяти для проверки временных свойств программ с конечным числом состояний [11], определение сложности проверки соответствия программ их спецификациям, выраженным в линейной временной логике , [12] и проверку того, что модель с временными ограничениями удовлетворяет заданному временному свойству. [13]Вместе с Алексом Гроче и Дороном Пеледом он представил адаптивную проверку модели, показав, что при наличии несоответствий между системой и соответствующей моделью результаты проверки можно использовать для улучшения модели. [14] Он также внес свой вклад в исследование диаграмм последовательности сообщений (MSC), где было показано, что слабая реализуемость неразрешима для ограниченных MSC-графов и что безопасная реализуемость находится в EXPSPACE , наряду с другими интересными результатами, связанными с проверкой MSC-графики. [15]

Награды и признание [ править ]

Яннакакис является членом Национальной инженерной академии и Национальной академии наук . Он был удостоен седьмой премии Кнута за вклад в теоретическую информатику. [2] Он также был награжден премией Bell Labs за выдающийся член технического персонала и золотой наградой президента Bell Labs в 1985 и 2000 годах соответственно. Он является членом ACM, а также членом Bell Laboratories . [1] Он был избран членом Американской академии искусств и наук (AAAS) в 2020 году. [16]

Ссылки [ править ]

  1. ^ a b c d e f g Колумбийский университет: CV: Михалис Яннакакис (по состоянию на 12 ноября 2009 г.)
  2. ^ a b Премия Кнута. Архивировано 28 января 2012 г. в Wayback Machine (по состоянию на 3 июня 2015 г.)
  3. ↑ The Mathematics Genealogy Project - Михалис Яннакакис (по состоянию на 9 декабря 2009 г.)
  4. ^ "Googel Scholar Record М. Яннакакиса" .
  5. ^ Христос Пападимитриу, Михалис Яннакакис, Оптимизация, аппроксимация и классы сложности, Труды двадцатого ежегодного симпозиума ACM по теории вычислений, стр.229-234, 2–4 мая 1988 г.
  6. ^ Карстен Лунд, Михалис Яннакакис, О сложности аппроксимации задач минимизации, Труды двадцать пятого ежегодного симпозиума ACM по теории вычислений, стр.286-293, 16–18 мая 1993 г.
  7. ^ Катриэль Бери, Рональд Фэджин, Дэвид Майер, Альберто Мендельзон, Джеффри Ульман, Михалис Яннакакис, Свойства ациклических схем баз данных, Труды тринадцатого ежегодного симпозиума ACM по теории вычислений, стр. 355-362, 11–13 мая 1981 г.
  8. ^ Catriel Биря, Рональд Феджин, Дэвид Майер, Михалис Яннкакис, о желательности ациклических баз данных схем, Журнал ACM, V.30 N.3, p.479-513, июль 1983 года.
  9. ^ Михалис Яннкакис, Теория безопасных Запорных политик в базе данных системы, Журнал ACM, V.29 N.3, p.718-740, июль 1982 года.
  10. ^ Михалис Яннакакис, Свобода от взаимоблокировок политики безопасной блокировки, SIAM J. on Computing 11 (1982), 391-408.
  11. ^ К. Куркубетис, М. Варди, П. Вольпер, М. Яннакакис, Эффективные с памятью алгоритмы для проверки временных свойств, Формальные методы в проектировании систем, v.1, п.2-3, стр.275-288, октябрь 1992 г.
  12. ^ Костас Courcoubetis, Михалис Яннкакис, сложность вероятностной верификации, Журнал ACM, V.42 n.4, p.857-907, июль 1995 года.
  13. ^ Р. Алур, А. Итаи, Р.П. Куршан, М. Яннакакис, Проверка времени с помощью последовательного приближения, Информация и вычисления, т.118, №1, стр.142-157, апрель 1995 г.
  14. ^ Groce А., Peled, Д. и Yannakakis М. 2002. Адаптивная модель проверка. В материалах 8-й международной конференции по инструментам и алгоритмам построения и анализа систем (8–12 апреля 2002 г.). Дж. Катоен и П. Стивенс, ред. Конспект лекций по информатике, т. 2280. Springer-Verlag, London, 357–370.
  15. ^ Раджив Алур, Коуша Этессами, Михалис Яннакакис, Реализуемость и проверка графов MSC, Теоретическая информатика, т. 331, № 1, стр. 97-114, 15 февраля 2005 г.
  16. ^ «Избранные стипендиаты AAAS» (PDF) . Уведомления Американского математического общества .

Внешние ссылки [ править ]

  • Домашняя страница в Колумбии