Премия Гёделя (англ. 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) |
за «сглаженный анализ» алгоритмов
|
Примечания
См. также
Ссылки
de:Gödel-Preis
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:哥德尔奖
Если вам нравится SbUP.com Сайт, вы можете поддержать его - BTC: bc1qppjcl3c2cyjazy6lepmrv3fh6ke9mxs7zpfky0 , TRC20 и ещё....
