Перейти к навигации Перейти к поиску
 | В этой статье слишком много ссылок на первоисточники . ( Май 2013 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
Премия EATCS - IPEC Nerode Prize - это премия в области теоретической информатики, присуждаемая за выдающиеся исследования в области многомерной алгоритмики . Он был награжден Европейской ассоциацией теоретической информатики и Международным симпозиумом по параметризованным и точным вычислениям . [1] Премия была вручена впервые в 2013 году. [2]
Победители [ править ]
На данный момент победителями стали:
- 2013: Крис Калабро, Рассел Импальяццо , Валентин Кабанец, Рамамохан Патури и Фрэнсис Зейн за их исследования, формулирующие гипотезу экспоненциального времени и использующие ее для определения точной параметризованной сложности нескольких важных вариантов проблемы логической выполнимости . [3]
- 2014: Ханс Л. Бодлендер , Родни Г. Дауни , Майкл Р. Феллоуз , Дэнни Хермелин, Лэнс Фортноу и Рахул Сантханам за их работу по ядру , доказав, что некоторые проблемы с управляемыми алгоритмами с фиксированными параметрами не имеют ядер полиномиального размера если только иерархия полиномов не рухнет. [4]
- 2015: Эрик Демейн , Федор В. Фомин , Мохаммад Хаджиагайи и Димитриос Тиликос за их исследования двумерности , определяющие широкую основу для разработки алгоритмов с фиксированными параметрами для доминирования и покрытия проблем на графах. [5]
- 2016: Андреас Бьёрклунд за свою статью « Детерминантные суммы для неориентированной гамильтоничности» , показывающий, что методы, основанные на теории алгебраических графов, приводят к значительно улучшенному алгоритму поиска гамильтоновых циклов [6]
- 2017: Федор В. Фомин , Фабрицио Грандони и Дитер Крач за разработку метода «измерь и победи» для анализа алгоритмов поиска с возвратом. [7]
- 2018: Стефан Крач и Магнус Вальстрём за их работу с использованием теории матроидов для разработки ядер полиномиального размера для трансверсальных нечетных циклов и связанных с ними задач. [8]
- 2019: Нога Алон , Рафаэль Юстер и Ури Цвик за изобретение метода цветового кодирования , чрезвычайно важного ингредиента в наборе инструментов для проектирования параметризованных алгоритмов. [9]
См. Также [ править ]
Ссылки [ править ]
- ^ Премия IPEC Nerode , Европейская ассоциация теоретической информатики , получено 2015-09-03 CS1 maint: обескураженный параметр ( ссылка ).
- ^ "EATCS-IPEC Nerode Prize" , Параметризованная сложность , получено 03.09.2015. CS1 maint: обескураженный параметр ( ссылка ).
- ^ EATCS-IPEC Nerode Prize 2013 - Laudatio , Европейская ассоциация теоретической информатики , получено 2015-09-03 CS1 maint: обескураженный параметр ( ссылка ).
- ^ EATCS-IPEC Nerode Prize 2014 - Laudatio , Европейская ассоциация теоретической информатики , получено 2015-09-03 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Hajiaghayi Wins 2015 Nerode премии , Университет штата Мэриленд Института передовых компьютерных исследований, 8 мая 2015 года , восстановлена 2015-09-03 CS1 maint: обескураженный параметр ( ссылка ).
- ^ EATCS-ИПЕК Nerode премии 2016 , Европейская ассоциация по теоретической информатике , 29 августа 2016 года , восстановлена 2016-08-29 CS1 maint: обескураженный параметр ( ссылка ).
- ^ ALGO 2017 , ALGO 2017, 3 сентября 2017 , извлекаться 2017-09-03 CS1 maint: обескураженный параметр ( ссылка ).
- ^ Основные докладчики ALGO 2018 , Хельсинкский институт информационных технологий , данные получены 24 августа 2018 г. CS1 maint: обескураженный параметр ( ссылка )
- ^ EATCS-ИПЕК Nerode премии 2019 , Европейская ассоциация по теоретической информатике , 3 сентября, 2019 , извлекаться 2020-01-01 CS1 maint: обескураженный параметр ( ссылка ).