Премия Гёделя

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

Премия Гёделя (англ. Gödel Prize) — премия в области теории вычислительных систем имени Курта Гёделя, вручаемая ежегодно организациями ACM SIGACT (Special Interest Group on Algorithms and Computation Theory) и EATCS (European Association for Theoretical Computer Science) за выдающиеся труды по логике и теоретической информатике.

Премия вручается с 1993 года и сопровождается денежным вознаграждением размером в 5000 долларов США. Награждение проходит либо на американском симпозиуме STOC (Symposium on Theory of Computing), либо на европейской конференции ICALP (International Colloquium on Automata, Languages and Programming).[1] Основным требованием к работе является дата первой публикации — к номинации допускаются лишь труды не старше 14 лет.

Содержание

Лауреаты

Год Имя Примечания
1993 Ласло Бабаи, Шафи Гольдвассер, Сильвио Микали, Шломо Моран и Чарльз Ракофф (László Babai, Shafi Goldwasser, Silvio Micali, Shlomo Moran, Charles Rackoff) за разработку интерактивные системы доказательств
1994 Йохан Хостад (Johan Håstad) за доказательство принадлежности функции чётности (на boolean circuits) к экспоненциальному классу сложности
1995 Нил Иммермэн, Роберт Шелепчени (Neil Immerman, Róbert Szelepcsényi) за теорему Иммермэна-Шелепчени (теория сложности вычислений)
1996 Марк Джеррам, Элистер Синклер (Mark Jerrum, Alistair Sinclair) за исследования цепей Маркова и аппроксимацию перманента матриц
1997 Джозеф Хэлперн, Йорам Мосес (Joseph Halpern, Yoram Moses) за формальное определение понятия «знание» в распределённых средах
1998 Сейносуке Тода (Seinosuke Toda) за теорему Тода, которая показала связь между классами сложности PP и PH
1999 Питер Шор (Peter Shor) за алгоритм Шора для факторизации чисел за полиномиальное количество времени на квантовом компьютере
2000 Мойше Варди, Пьер Вольпер (Moshe Y. Vardi, Pierre Wolper) за исследование проверки моделей с помощью конечных автоматов
2001 Санджив Арора, Уриель Фейге, Шафи Гольдвассер, Карстен Лунд, Ласло Ловас, Раджив Мотвани, Шмуель Сафра, Мадху Судан и Марио Шегеди (Sanjeev Arora, Uriel Feige, Shafi Goldwasser, Carsten Lund, László Lovász, Rajeev Motwani, Shmuel Safra, Madhu Sudan, Mario Szegedy) за теорему PCP и её приложение
2002 Джеро Сенизергуес (Géraud Sénizergues) за доказательство разрешимости эквивалентности детерминированных автоматов с магазинной памятью
2003 Йоав Фрейнд и Роберт Шапире (Yoav Freund, Robert Schapire) за алгоритм AdaBoost
2004 Морис Херлихи, Майк Сакс, Нир Шавит и Фотиос Захароглу (Maurice Herlihy, Mike Saks, Nir Shavit, Fotios Zaharoglou) за приложение топологии в теории распределённых вычислений
2005 Нога Алон, Йосси Матиас, Марио Шегеди (Noga Alon, Yossi Matias, Mario Szegedy) за основополагающие исследования в области потоковых алгоритмов
2006 Маниндра Агравал, Нирадж Кайал, Нитин Саксена (Manindra Agrawal, Neeraj Kayal, Nitin Saxena) за тест Агравала — Каяла — Саксены
2007 Александр Разборов,[2] Стивен Рудик (Alexander Razborov, Steven Rudich) за «естественные доказательства»[3]
2008 Шангуа Тенг, Дэниел Спилмэн, Стивен Рудик (Shanghua Teng, Daniel Spielman, Steven Rudich) за «сглаженный анализ» алгоритмов

Примечания

См. также

Ссылки

en:Gödel Prize es:Premio Gödel fr:Prix Gödel he:פרס גדל it:Premio Gödel ja:ゲーデル賞 pl:Nagroda Gödla sk:Gödelova cena uk:Премія Геделя zh:哥德尔奖

Личные инструменты

Served in 0.200 secs.