Войти
| Михалис Яннакакис | |
|---|---|
 Михалис Яннакакис | |
| Родился | (1953-09-13) 13 сентября 1953 г. (возраст 67). Афины, Греция |
| Национальность | грек - американец |
| Alma mater | Национальный технический университет Афин. Принстонский университет |
| Награды | Премия Кнута (2005) |
| Научная карьера | |
| Области | Компьютерные науки |
| Учреждения | Колумбийский университет |
| Советник доктора | Джеффри Уллман |
Михалис Яннакакис (греч. : Μιχάλης Γιαννακάκης; родился 13 сентября 1953 г. в Афинах, Греция ) - профессор компьютерных наук в Колумбийском университете.. Он известен своей работой в вычислительной сложности, базах данных и других смежных областях. Он получил премию Дональда Э. Кнута в 2005 году.
Яннакакис родился в Афинах, Греция, в 1953 году и учился в средней школе Варвакейо. Он окончил Афинский национальный технический университет в 1975 году по специальности «Электротехника», а затем получил степень доктора философии. получил степень бакалавра компьютерных наук в Принстонском университете в 1979 году. Его диссертация была озаглавлена «Сложность максимальных проблем подграфов».
В 1978 году он присоединился к Bell Laboratories и занимал должность директора из отдела исследования принципов вычислений с 1991 по 2001 год, когда он покинул лабораторию Bell и присоединился к Avaya Laboratories. Там он работал директором отдела исследования принципов вычислений до 2002 года.
В 2002 году он поступил в Стэнфордский университет, где он был профессором компьютерных наук, и ушел в 2003 году, чтобы присоединиться к Колумбийский университет в 2004 году, где он в настоящее время работает в качестве Перси К. и Виды Л.В. Хадсон профессор компьютерных наук.
С 1992 по 2003 год Яннакакис работал в редакционной коллегии журнала SIAM Journal on Computing и был главным редактором с 1998 по 2003 год. Он также был членом редакционной коллегии Journal of the ACM с 1986 по 2000 год. В состав других членов редакционной коллегии входят Journal of Computer and System Sciences, Journal of Combinatorial Optimization и Journal of Complexity. Он также работал в комитетах конференций и председательствовал на различных конференциях, таких как Симпозиум ACM по принципам систем баз данных и Симпозиум IEEE по основам компьютерных наук.
По состоянию на июнь 2020 года его публикации цитировались почти 35 000 раз, и его индекс Хирша равен 93.
Яннакакис известен своим вкладом в информатику в области теория сложности вычислений, теория баз данных, автоматизированная проверка и тестирование и теория алгоритмических графов.
Среди его вкладов в теорию сложности - две статьи о PCP теория и о твердость приближения. На ежегодном симпозиуме ACM по теории вычислений 1988 года Яннакакис и Христос Пападимитриу представили определения классов сложности Max-NP и Max-SNP. Max-NP и Max-SNP (который является подклассом Max-NP) содержат ряд интересных задач оптимизации, и Яннакакис и Пападимитриу показали, что эти проблемы имеют некоторую ограниченную ошибку. Эти результаты смогли объяснить отсутствие прогресса, наблюдаемого в исследовательском сообществе в отношении аппроксимируемости ряда задач оптимизации, включая 3SAT, проблему независимого множества и Задача коммивояжера.
Яннакакис и Карстен Лунд представили ряд выводов относительно сложности вычислений приближений на ежегодном симпозиуме ACM по теории вычислений в 1993 г. Эти выводы продемонстрировали сложность эффективных вычислений приблизительные решения ряда задач минимизации, таких как Раскраска графика и Задать покрытие. Учитывая маловероятный сценарий, при котором NP-сложные задачи, такие как раскраска графа и покрытие множества, будут оптимально решены за полиномиальное время, было много попыток разработать для них эффективные аппроксимационные решения; результаты, полученные Яннакакисом и Карстеном, доказали маловероятность достижения этой задачи.
В области теории баз данных его вклад включает начало исследования ациклических баз данных и недвухфазной блокировки. Схемы ациклической базы данных - это схемы, которые содержат единственную ациклическую зависимость соединения (зависимость соединения - это связь, управляющую соединением таблиц базы данных) и набор функциональных зависимостей; ряд исследователей, в том числе Яннакакис, указали на полезность этих схем, продемонстрировав множество полезных свойств, которыми они обладали: например, способность решать многие задачи, основанные на ациклических схемах, за полиномиальное время, в то время как проблема легко могла быть NP- полная для других схем.
Что касается не двухфазной блокировки, Яннакакис продемонстрировал, как знания о структуре базы данных и формах различных транзакций, выполняемых на них, могут быть использованы для установления является ли конкретная политика блокировки безопасной или нет. Обычно используемые политики двухфазной блокировки (2PL) состоят из двух этапов - для блокировки и разблокировки объектов соответственно - и чтобы избежать такой политики, необходимо наложить некоторую структуру на объекты базы данных; Результаты Яннакакиса показывают, что при выборе гиперграфа, напоминающего структуру ограничения согласованности базы данных, политика блокировки, которая посещает объекты на путях этого гиперграфа, будет безопасной. Такая политика не обязательно должна быть двухэтапной, и эти политики могут быть классифицированы в соответствии с возможностью подключения вышеупомянутого гиперграфа, причем политики 2PL являются лишь одним из них. Далее Яннакакис показал, что для естественного класса политик безопасной блокировки (L-политик) свобода от взаимоблокировок определяется исключительно порядком, в котором к объектам обращаются транзакции, и из этих полученных простых условий, которые гарантируют свободу от взаимоблокировок для L-политика.
Он также внес свой вклад в область компьютерной проверки и тестирования, где он заложил строгие алгоритмические и теоретико-сложные основы этой области. Некоторые из его вкладов включают разработку эффективных алгоритмов памяти для проверки временных свойств программ с конечным числом состояний, определение сложности проверки соответствия программ их спецификациям, выраженным в линейном времени темпоральной логике, и проверка того, что модель с временными ограничениями удовлетворяет заданному временному свойству. Вместе с Алексом Гроче и Дороном Пеледом он представил адаптивную проверку модели, показав, что при наличии несоответствий между системой и соответствующей моделью результаты проверки можно использовать для улучшения модели. Он также участвовал в исследовании диаграмм последовательности сообщений (MSC), где было показано, что слабая реализуемость неразрешима для ограниченных MSC-графов и что безопасная реализуемость находится в EXPSPACE, наряду с другими интересными результатами, относящимися к верификации MSC-графиков.
Яннакакис является членом Национальной инженерной академии и Национальной академии наук. Ему была присуждена седьмая премия Кнута за вклад в теоретическую информатику. Он также был награжден премией Bell Labs за выдающийся член технического персонала и золотой наградой президента Bell Labs в 1985 и 2000 годах соответственно. Он является членом ACM, а также членом Bell Laboratories. Он был избран членом Американской академии искусств и наук (AAAS) в 2020 году.
