Премия Кнута
Премия Дональда Э. Кнута — это премия за выдающийся вклад в развитие информатики , названная в честь американского ученого-компьютерщика Дональда Э. Кнута .
История [ править ]
Премия Кнута вручается с 1996 года и включает премию в размере 5000 долларов США. Премия присуждается ACM SIGACT и Техническим комитетом компьютерного общества IEEE по математическим основам вычислений. Премии вручаются попеременно на симпозиуме ACM по теории вычислений и на симпозиуме IEEE по основам компьютерных наук , которые являются одними из самых престижных конференций в области теоретической информатики . Лауреат премии Кнута выступает на конференции с лекцией. [1] Например, Дэвид С. Джонсон «использовал свою лекцию на премии Кнута, чтобы продвигать практическое применение алгоритмов». [2]
В отличие от премии Гёделя , которая присуждается за выдающиеся работы, премия Кнута присуждается отдельным лицам за общий вклад в эту область.
Победители [ править ]
С момента учреждения премии в 1996 году она была вручена следующим лицам, с указанием цитаты каждой награды (не всегда полностью): [3]
| Год | Лауреат | Цитирование |
|---|---|---|
| 1996 | Эндрю Яо | «фундаментальные исследования вычислительной сложности» [4] |
| 1997 | Лесли Валиант | «далеко идущий вклад в изучение сложности вычислений, параллельных вычислений и теории обучения» [5] |
| 1999 | Ласло Ловаш | «огромное влияние на теорию алгоритмов» и «фундаментальные открытия, которые стали стандартными инструментами в теоретической информатике» [6] |
| 2000 | Джеффри Уллман | «постоянный исследовательский вклад в теоретическую информатику, особенно в том, что касается прикладных областей информатики, таких как компиляторы, параллелизм и базы данных; а также за его вклад в образование в области теоретической информатики посредством учебников и наставничества аспирантов» [7] |
| 2002 | Христос Пападимитриу | «за многолетний и плодотворный вклад в основы информатики» [8] |
| 2003 | Миклош Айтай | «За многочисленные новаторские вклады в теоретическую информатику» [9] [10] |
| 2005 | Михалис Яннакакис | «За многочисленные новаторские вклады в теоретическую информатику» [11] |
| 2007 | Нэнси Линч | «за плодотворный и влиятельный вклад в теорию распределенных вычислений» [12] |
| 2008 | Фолькер Штрассен | «за плодотворный и влиятельный вклад в создание эффективных алгоритмов» [13] |
| 2010 | Дэвид Джонсон | «за вклад в теоретический и экспериментальный анализ алгоритмов» [2] [14] [15] [16] |
| 2011 | Рави Каннан | «обеспечил теоретическую информатику множеством новых мощных алгоритмических методов» [17] |
| 2012 | Леонид Левин | «в знак признания четырех десятилетий дальновидных исследований в области сложности, криптографии и теории информации» [18] |
| 2013 | Гэри Миллер | «огромное влияние на криптографию, а также на теорию чисел, параллельные вычисления, теорию графов, создание сеток для научных вычислений и решение линейных систем» [19] |
| 2014 | Ричард Липтон | «За изобретение новой информатики и математических методов для решения фундаментальных и практических проблем в широком спектре областей графовых алгоритмов, вычислений, связи, тестирования программ и вычислений на ДНК» [20] [21] |
| 2015 | Ласло Бабай | «за фундаментальный вклад в теоретическую информатику, включая разработку алгоритмов и теорию сложности» [22] |
| 2016 | Ноам Нисан | «За фундаментальный и продолжительный вклад в теоретическую информатику в таких областях, как сложность коммуникации, генераторы псевдослучайных чисел, интерактивные доказательства и алгоритмическая теория игр» [23] |
| 2017 | Одед Гольдрейх | «за фундаментальный и продолжительный вклад в теоретическую информатику во многих областях, включая криптографию, случайность, вероятностно проверяемые доказательства, неаппроксимируемость, проверку свойств, а также теорию сложности в целом» [24] |
| 2018 | Йохан Хастад | «за его длительный и устойчивый опыт значительных прорывов в основах информатики, оказавший огромное влияние на многие области, включая оптимизацию, криптографию, параллельные вычисления и теорию сложности» [25] |
| 2019 | Ави Вигдерсон | «за фундаментальный и продолжительный вклад в основы информатики в таких областях, как рандомизированные вычисления, криптография, сложность схем, сложность доказательств, параллельные вычисления и наше понимание фундаментальных свойств графов» [26] [27] |
| 2020 | Синтия Дворк | «за фундаментальный и продолжительный вклад в информатику. Дворк — одна из самых влиятельных ученых-теоретиков в области информатики своего поколения. Ее исследования изменили несколько областей, в первую очередь распределенные системы, криптографию и конфиденциальность данных, а ее нынешняя работа обещает добавить справедливости». в алгоритмическом принятии решений по списку». [28] [29] [30] [31] |
| 2021 | Моше Варди | «За выдающийся вклад в применение математической логики во многих фундаментальных областях информатики» [32] [33] [34] |
| 2022 | Осторожный Алон | «За фундаментальный вклад в комбинаторику и теорию графов, а также приложения к фундаментальным темам информатики» [35] |
| 2023 | Ева Тардос | за «ее обширный исследовательский вклад и лидерство в этой области, а именно, за соавторство влиятельного учебника «Проектирование алгоритмов», совместное редактирование «Справочника по теории игр», работу в качестве главного редактора журнала ACM и Общества промышленных и прикладных технологий. Mathematics (SIAM) Journal of Computing и председательство в программных комитетах нескольких ведущих отраслевых конференций». [36] |
Отборочные комитеты [ править ]
| Год | Отборочный комитет |
|---|---|
| 1996 | Рональд Грэм (председатель отдела исследований AT&T), Джо Халперн (Исследовательский центр IBM в Альмадене), Курт Мельхорн (Институт информатики Макса Планка), Николас Пиппенгер (Университет Британской Колумбии), Ева Тардос (Корнелльский университет), Ави Вигдерсон (иврит) Университет) |
| 1997 | |
| 1999 | Аллан Бородин, Ашок Чандра, Герберт Эдельсбруннер, Христос Пападимитриу, Ива Тардос (председатель) и Ави Вигдерсон |
| 2000 | |
| 2002 | |
| 2003 | |
| 2005 | Ричард Ладнер, Том Лейтон, Лачи Ловаш, Гэри Миллер, Майк Патерсон и Умеш Вазирани (председатель) |
| 2007 | Майк Патерсон (председатель), Том Лейтон, Гэри Миллер, Энн Кондон, Михалис Яннакакис, Ричард Ладнер |
| 2008 | |
| 2010 | |
| 2011 | |
| 2012 | |
| 2013 | |
| 2014 | |
| 2015 | Рассел Импальяццо (председатель UCSD), Уриэль Файги (Институт науки Вейцмана), Мишель Гоеманс (MIT), Йохан Хастад (Королевский технологический институт KTH), Анна Карлин (Университет Вашингтона), Сатиш Б. Рао (Калифорнийский университет в Беркли) |
| 2016 | Аллан Бородин (Университет Торонто), Ури Файги (Институт Вейцмана), Мишель Гоеманс (MIT, председатель), Йохан Хастад (KTH), Сатиш Рао (Калифорнийский университет в Беркли) и Шан-Хуа Тенг (Университет Южной Калифорнии). |
| 2017 | Аллан Бородин (председатель Университета Торонто), Аврим Блюм (CMU), Шафи Голдвассер (MIT и Институт Вейцмана), Йохан Хастад (KTH – Королевский технологический институт), Сатиш Рао (Калифорнийский университет в Беркли) и Шанхуа Тенг (ОСК) |
| 2018 | Аллан Бородин (Университет Торонто), Алан Фриз (КМУ), Аврим Блюм (TTIC), Шафи Голдвассер (Калифорнийский университет в Беркли), Ноам Нисан (Ивритский университет) и Шан-Хуа Тенг (председатель Университета Южной Калифорнии) |
| 2019 | Аврим Блюм (председатель TTIC), Алан Фриз (CMU), Шафи Голдвассер (Калифорнийский университет в Беркли), Ноам Нисан (Еврейский университет), Ронитт Рубинфельд (MIT и Тель-Авивский университет) и Энди Яо (Университет Цинхуа). |
| 2020 | Алан Фриз, председатель (CMU), Хэл Габоу (Университет Колорадо), Ноам Нисан (Ивритский университет), Ронитт Рубинфельд (MIT), Ева Тардос (Корнеллский университет), Энди Яо (Университет Цинхуа) |
| 2021 | Гарольд Габоу (председатель Университета Колорадо), Ноам Нисан (Ивритский университет), Дана Рэндалл (Технологический институт Джорджии), Ронитт Рубинфельд (MIT), Мадху Судан (Гарвардский университет) и Энди Яо (Университет Цинхуа). |
| 2022 | Гарольд Габоу (Университет Колорадо), Моника Хензингер (Университет Вены), Курт Мельхорн (Институт Макса Планка), Дана Рэндалл (председатель Технологического института Джорджии), Мадху Судан (Гарвардский университет) и Энди Яо (Университет Цинхуа) |
| 2023 | Дэвид Эппштейн (Калифорнийский университет в Ирвайне), Моника Хенцингер (председатель ISTA/Университета Вены), Курт Мельхорн (Институт Макса Планка), Дана Рэндалл (Технологический институт Джорджии), Мадху Судан (Гарвардский университет) и Моше Варди (Университет Райса) |
См. также [ править ]
Ссылки [ править ]
- ^ Премия Кнута , Компьютерное общество IEEE
- ↑ Перейти обратно: Перейти обратно: а б Памяти Дэвида С. Джонсона , Ассоциация компьютерных исследований, апрель 2016 г.
- ^ «Премия Кнута» . АСМ СИГАКТ. 23 сентября 2021 г. . Проверено 23 сентября 2021 г.
- ^ Панельная дискуссия SMU на тему «Создание будущего посредством вычислений» с выдающимися участниками дискуссии, получившей премию Тьюринга , Сингапурский университет менеджмента
- ^ Valiant получает награду Turning Award 2010 (PDF) , Уведомления Американского математического общества (июнь/июль 2011 г.)
- ^ Шелтон, Джи (29 марта 2021 г.). «Лауреат Абелевской премии 2021 года стал оплотом математики и информатики Йельского университета» . Йельские новости . Йельский университет . Проверено 24 апреля 2022 г.
- ^ Шелтон, Джим (31 марта 2021 г.). «Премия Тьюринга ACM присуждается новаторам, которые сформировали компьютерное программирование: Ахо и Ульман разработали инструменты и оригинальные учебники, которыми пользуются миллионы программистов» . ЭврекАлерт! . АААС . Проверено 24 апреля 2022 г.
- ^ Бернадетт Янг (8 октября 2019 г.), профессор Христос Пападимитриу награжден премией Харви 2018 г. , Колумбийский университет, инженерное дело
- ^ Годовой отчет SIGACT, июль 2002 г. – июнь 2003 г.; 1. Врученные награды , ACM, 2003 г.
- ^ Премия Кнута 2003 г., Миклош Айтай , ACM, 9 октября 2003 г.
- ^ Премия Кнута 2005 г. Михалиса Яннакакиса , ACM, 1 мая 2006 г.
- ^ Нэнси Линч названа лауреатом премии ACM за вклад в надежность распределенных вычислений , Лаборатория компьютерных наук и искусственного интеллекта Массачусетского технологического института, 4 апреля 2007 г.
- ^ Премия Кнута ACM SIGACT 2008 отмечает вклад Штрассена в разработку эффективных алгоритмов , ACM, 23 октября 2008 г.
- ^ Линда Крейн, Дэвид С. Джонсон: В память о Колумбийском университете, информатика
- ^ Ли Л. Кинер, Дэвид С. Джонсон '67 , журнал Amherst Magazine
- ^ Исследователь AT&T Labs получит премию ACM SIGACT Кнута за инновации в алгоритмах , ACM, 2 марта 2010 г.
- ^ Трое исследователей Microsoft в Индии названы стипендиатами ACM , Illinois Intelligencer, 9 декабря 2016 г.
- ^ Цитирование: Премия Кнута 2012 г. (PDF) , ACM, 15 июля 2012 г.
- ^ ACM вручает премию Кнута создателю теории и алгоритмов решения проблем , ACM, 4 апреля 2013 г.
- ^ «ACM вручает премию Кнута новатору за достижения в области алгоритмов и теории сложности» . Ассоциация вычислительной техники. 15 сентября 2014 г. Архивировано из оригинала 20 сентября 2014 г.
- ^ Тайлор, Филипп (2014). «ACM, IEEE выбирает Липтона для получения престижной премии Кнута» . Центр новостей . Технологический институт Джорджии . Проверено 24 апреля 2022 г.
- ^ Награждение премии Кнута 2015 года женщине Ласло (PDF) , ACM, 17 мая 2015 г.
- ^ ACM вручает премию Кнута пионеру алгоритмической теории игр , ACM, 8 сентября 2016 г.
- ^ Премия Кнута 2017 вручена Одеду Гольдрейху (PDF) , ACM, 13 июня 2017 г.
- ^ Премия Кнута 2018 присуждена Йохану Хостаду (PDF) , ACM, 6 августа 2018 г.
- ^ Сью Джи (7 апреля 2019 г.), премия Кнута 2019 г. присуждена за вклад в теорию сложности
- ^ «Оптимизация, сложность и математика… с использованием градиента» – лекция на премию Кнута, STOC 2019 – Ави Вигдерсон , 3 марта 2020 г., заархивировано из оригинала 14 декабря 2021 г.
- ^ Элизабет Салазар (15 мая 2020 г.), Синтия Дворк получает премию Кнута за выдающийся вклад в основы компьютерных наук , Гарвардский университет
- ^ Ведущий специалист в области криптографии и конфиденциальности данных получает премию Кнута , Американская ассоциация содействия развитию науки, 2 июня 2020 г.
- ^ Лекция на премию Кнута – Синтия Дворк , 25 ноября 2020 г., заархивировано из оригинала 14 декабря 2021 г.
- ^ «Профессор Гарварда получает премию за вклад в теоретическую информатику» . Провод HPC . 2 июня 2020 г. Проверено 24 апреля 2022 г.
- ^ Премия Кнута 2021 г. вручена Моше Варди (PDF) , ACM, 9 мая 2021 г.
- ^ STOC 2021 – Доклад на премию Кнута: Логика и вычисления – Матч, заключенный на небесах – Моше Варди , 14 июля 2021 г., заархивировано из оригинала 14 декабря 2021 г.
- ^ Бойд, Джейд (27 мая 2021 г.). «Моше Варди получает премию Кнута» . Еврейский Вестник-Голос . Проверено 24 апреля 2022 г.
- ^ «Премия Кнута 2022 года вручена Ноге Алону» (PDF) . Специальная группа ACM по алгоритмам и теории вычислений . Проверено 2 июля 2022 г.
- ^ «Тардос удостоен премии Кнута 2023 года» . Проверено 24 июня 2023 г.