Премия за лекцию Флажоле
Премия Филиппа Флажоле за лекции присуждается за вклад в аналитическую комбинаторику и анализ алгоритмов в области теоретической информатики . Эта премия названа в память о Филиппе Флажоле .
История [ править ]
Премия Флажоле за лекции вручается с 2014 года. Премия Флажоле за лекции вручается в нечетные годы. После отбора на премию лауреат в течение следующего года читает лекцию Флажоле. Эта лекция организована как основной доклад на Международной конференции по вероятностным, комбинаторным и асимптотическим методам анализа алгоритмов (AofA) . [1] AofA — это международная конференция, которая началась с серии семинаров, начатых Флажоле и другими в 1993 году. Отборочный комитет состоит из трех представителей этой области.
Научные темы [ править ]
Лауреаты Премии лекций Флажоле работают в различных областях, в том числе анализ алгоритмов , аналитическая комбинаторика , комбинаторика , протоколы связи , комплексный анализ , вычислительная биология , интеллектуальный анализ данных , базы данных , графики , теория информации , предельные распределения , карты , деревья , вероятность , статистическая физика .
Во вступительной лекции Дон Кнут обсудил пять «проблем, которые бы понравились Филиппу». [2] Кнут рассмотрел пять проблем, включая перечисление полимино , математическое разбиение на мозаику , обрезку деревьев , пути в решетке и теорию возмущений . В частности, он обсудил асимптотическое перечисление полимино (см. OEIS A001168). запись [3] для контекста и истории). Обсуждение Кнутом обрезки леса побудило Питера Лушни обнаружить связь с тропами Дейка (см. OEIS A091866). запись [4] ). Часть доклада о решетчатых путях наклона 2/5 была посвящена теореме Накамигавы и Токусигэ. [5] [6] Кнут выдвинул гипотезу о соответствующем перечислении путей в решетке, которая впоследствии была решена Сирилом Бандерье и Майклом Валлнером. [7] [8] [9] Обсуждение Кнутом путей решетки также привело к созданию двух новых записей OEIS, A322632. [10] и А322633. [11]
Лекция Роберта Седжвика в 2016 году была посвящена теме, восходящей к одной из самых ранних статей Флажоле, — методам приближенного подсчета потоковой передачи данных. В докладе были подчеркнуты связи между «практическими вычислениями» и теоретической информатикой. В качестве ключевого примера этих связей Седжвик подчеркнул, что Флажоле неоднократно в течение своей карьеры возвращался к теме приблизительного подсчета, начиная с алгоритма Флажоле-Мартена для вероятностного подсчета. [12] и возглавляет внедрение методов логарифмического подсчета. [13] и HyperLogLog . подсчет [14] В докладе Седжвика особое внимание уделялось не только базовой теории, но и экспериментальной проверке приближенного подсчета, а также его современным приложениям в облачных вычислениях. Он также представил алгоритм HyperBitBit, который подходит для приложений, требующих небольших и частых вычислений.
Получатели [ править ]
| Год отбора | Год лекций | Получатель | Картина | Название лекции | Конференция | Место проведения лекции |
|---|---|---|---|---|---|---|
| 2013 | 2014 | Дон Кнут |  | Проблемы, которые понравились бы Филиппу [2] | Конференция AofA 2014 [15] [16] [17] [18] | Париж, Франция |
| 2015 | 2016 | Боб Седжвик |  | Оценка мощности [19] | Конференция AofA 2016 [20] [21] | Краков, Польша |
| 2017 | 2018 | Люк Деврой |  | Боже мой: GW, CLT, CRT и CFTP [22] | Конференция AofA 2018 [23] [24] [25] | Уппсала, Швеция |
| 2019 | 2022 [а] | Войтек Шпанковски |  | Аналитическая информация и теория обучения: от сжатия к обучению | Конференция AofA 2022 [26] | Филадельфия, Пенсильвания, США |
| 2021 | 2022 | Сванте Янсон |  | Сумма степеней размеров поддеревьев случайных деревьев | Конференция AofA 2022 | Филадельфия, Пенсильвания, США |
| 2023 | 2024 | Майкл Дрмота |  | Еще раз о методе моментов | Конференция AofA 2024 [27] | Бат, Великобритания |
См. также [ править ]
Примечания [ править ]
- ↑ Лекция Шпанковского изначально была запланирована на конференцию AofA 2020 года, но сроки были отложены до 2022 года из-за пандемии COVID-19 .
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б «Анализ алгоритмов» . Проверено 20 марта 2021 г.
- ^ Jump up to: Перейти обратно: а б Дональд Кнут . «Проблемы, которые понравились бы Филиппу» (PDF) . Стэнфордский университет . Проверено 23 марта 2022 г.
- ^ НЯА Слоан. «Количество фиксированных полимино с n ячейками» . Электронная энциклопедия целочисленных последовательностей . Проверено 23 марта 2022 г.
- ^ Эмерик Дойч. «Количество путей Дика полудлины n, имеющих вес пирамиды k» . Электронная энциклопедия целочисленных последовательностей . Проверено 23 марта 2022 г.
- ^ Накамигава, Томоки; Токусигэ, Норихиде (2012). «Подсчет путей в решетке с помощью леммы нового цикла» . SIAM Journal по дискретной математике . 26 (2). Общество промышленной и прикладной математики: 745–754. CiteSeerX 10.1.1.220.6893 . дои : 10.1137/100796431 . Проверено 23 марта 2022 г.
- ^ Хьюго Пфертнер. "a(n) = 2*биномиал(7*n-1,2*n)/(7*n-1)" . Электронная энциклопедия целочисленных последовательностей . Проверено 23 марта 2022 г.
- ^ Бандерье, Сирил; Валлнер, Майкл (2015). «Решетчатые дорожки уклона 2/5». 2015 Материалы двенадцатого семинара по аналитической алгоритмике и комбинаторике (ANALCO) . стр. 105–113. arXiv : 1605.02967 . дои : 10.1137/1.9781611973761.10 . ISBN 978-1-61197-376-1 . S2CID 15496496 .
- ^ Бандерье, Сирил; Валлнер, Майкл (2015). «Решетчатые дорожки уклона 2/5» . Общество промышленной и прикладной математики, собрание по аналитической алгоритмике и комбинаторике . Проверено 23 марта 2022 г.
- ^ Бандерье, Сирил; Валлнер, Майкл (2019). «Метод ядра для решетчатых путей ниже линии рационального наклона» . В Эндрюсе, Джордж; Краттенталер, Кристиан; Криник, Алан (ред.). Комбинаторика путей решетки и приложения . Развитие математики. Том. 58. Спрингер. стр. 119–154. дои : 10.1007/978-3-030-11102-1 . ISBN 978-3-030-11101-4 . S2CID 197480284 . Проверено 23 марта 2022 г.
- ^ Хьюго Пфертнер. «Десятичное разложение действительного решения до 23*x^5 — 41*x^4 + 10*x^3 — 6*x^2 — x — 1 = 0» . Электронная энциклопедия целочисленных последовательностей . Проверено 23 марта 2022 г.
- ^ Хьюго Пфертнер. «Десятичное разложение действительного решения до 11571875*x^5 - 5363750*x^4 + 628250*x^3 - 97580*x^2 + 5180*x - 142 = 0, умноженное на 3/7» . Электронная энциклопедия целочисленных последовательностей . Проверено 23 марта 2022 г.
- ^ Флажоле, Филипп; Найджел Мартин, Г. (1985). «Алгоритмы вероятностного подсчета для приложений баз данных» (PDF) . Журнал компьютерных и системных наук . 31 (2): 182–209. дои : 10.1016/0022-0000(85)90041-8 .
- ^ Дюран, Марианна; Флажоле, Филипп (2003). «Логлогический подсчет больших мощностей» (PDF) . Алгоритмы – ЕКА 2003 . Конспекты лекций по информатике. Том. 2832. с. 605. дои : 10.1007/978-3-540-39658-1_55 . ISBN 978-3-540-20064-2 . Проверено 23 марта 2022 г.
- ^ Флажоле, Филипп; Фьюзи, Эрик; Гандуэ, Оливье; Менье, Фредерик (2007). «Гиперлоглог: анализ почти оптимального алгоритма оценки мощности» . Труды дискретной математики и теоретической информатики . АХ . Нанси, Франция : 137–156 . Проверено 23 марта 2022 г.
- ^ «АОФА 2014» . Проверено 20 марта 2021 г.
- ^ «Главная страница материалов конференции AofA 2014 из многопрофильного архива открытого доступа HAL в INRIA, Франция» . Проверено 20 марта 2021 г.
- ^ «Полный материал научной конференции AofA 2014 из многопрофильного архива открытого доступа HAL в INRIA, Франция» . Проверено 20 марта 2021 г.
- ^ «Публичные лекции Дона Кнута в 2014 году» . Проверено 23 марта 2022 г.
- ^ Боб Седжвик (16 октября 2020 г.). «Оценка мощности» .
- ^ «АОФА 2016» . Проверено 20 марта 2021 г.
- ^ «Полный материал научной конференции AofA 2016 Ягеллонского университета в Кракове» (PDF) . Проверено 20 марта 2021 г.
- ^ Люк Деврой. «Статьи в редакционных сборниках» .
- ^ «АОА 2018» . Архивировано из оригинала 22 августа 2019 года . Проверено 20 марта 2021 г.
- ^ «Полный материал научной конференции AofA 2018 с сервера онлайн-публикаций Dagstuhl Research» (PDF) . Проверено 20 марта 2021 г.
- ^ «Специальный выпуск журнала Algorithmica, посвященный избранным статьям AofA 2018» . Проверено 20 марта 2021 г.
- ^ «Шпанковский получает премию Флажоле» . 11 февраля 2020 г. Проверено 20 марта 2021 г.
- ^ «АофА2024» . Проверено 29 июня 2023 г.