Главная » Летние и зимние школы » Летняя школа 2019 » Анонсы курсов и задачи

Анонсы курсов и задачи

Алексей Яковлевич Белов-Канель (Bar-Ilan University) — «Небеса» 

Кажется, что небосвод есть двумерная евклидова сфера, «хрустальный купол небес «. На самом деле это комплексная проективная прямая.

Мы поясним почему это так и при чем тут неевклидова геометрия и теория относительности.




Борис Сергеевич Бычков (НИУ ВШЭ, ФПМИ МФТИ) — «От хроматического многочлена к дифференциальным уравнениям»

Хроматический многочлен строится по графу с помощью рекурсивного соотношения удаления-стягивания. Его можно естественно обобщить на взвешенные графы, получив тем самым симметрическую функцию от бесконечного числа переменных. Оказывается, такая функция является решением бесконечной системы дифференциальных уравнений. Про уравнения говорить будем мало — в основном графы и многочлены. Курс состоит из двух занятий — будем двигаться быстро, но основательно.

Этот сюжет является примером не до конца изученной связи производящих функций полиномиальных инвариантов графов и интегрируемых иерархий.




Всеволод Александрович Воронов (КМЦ АГУ)— «Перечисление графов»

Сколько существует различных графов на N вершинах? Нетрудно понять, что происходит, если вершины перенумерованы числами от 1 до N, и номера вершин фиксированы. Но в том случае, если графы, отличающиеся друг от друга нумерацией, считаются одинаковыми (изоморфными) задача принципиально усложняется, и ответ уже не удается записать в виде выражения, зависящего от N. Можно задать бесчисленное множество похожих вопросов. Например, сколько существует различных связных графов? Сколько деревьев? Сколько бинарных деревьев с корнем? Некоторые из этих задач намного проще названной выше, некоторые сложнее, а некоторые еще не решены. Курс посвящен классическим методам их исследования, опирающимся на производящие функции и теорему Пойа о перечислении. Предварительных знаний, кроме базовой информации о графах, не потребуется.




Михаил Александрович Григорьев (ФПМИ МФТИ) — «Теорема о бутерброде и ее применения в комбинаторике»

Теорема о бутерброде утверждает, что любой бутерброд из хлеба, масла и сыра можно разрезать плоскостью на две части равные по массе и хлеба и сыра и масла. В миникурсе мы рассмотрим ее приложения в различных комбинаторных задачах, докажем ее с помощью теоремы Борсука-Уллама и рассмотрим другие приложения топологических методов к комбинаторике и геометрии. Требуются базовые знания математического анализа (непрерывность, сходимость в d-мерном пространстве) и линейной алгебры (линейная зависимость, гиперплоскости)




Антон Сергеевич Гусев (мехмат МГУ) — «Раскраски графов. Теорема Брукса и ее усиления»

Раскраски графов являются одним из важнейших и красивейших разделов теории графов. И если вы ранее сталкивались с их изучением, то наверняка слышали про теорему Брукса, которая показывает связь между минимальным количеством цветов для правильной раскраски и степенями вершин графа.  

Теорема Брукса уникальна тем, что способна улучшать сама себя. Так, применяя к семейству графов теорему Брукса, можно получить усиление теоремы Брукса. 

Для освоения курса никаких предварительных знаний не требуется, весь необходимый материал будет рассказан на занятиях.




Максим Евгеньевич Жуковский (ФПМИ МФТИ) — «Описательная сложность задачи об изоморфизме»

Пусть pastedGraphic.png — некоторый граф. Каким образом можно формализовать графовое свойство «содержать подграф, изоморфный графу pastedGraphic_1.png»? И вообще говоря, что подразумевается под словом «свойство»? В так называемой теории моделей свойством принято называть множество графов, замкнутое относительно изоморфизма. Иными словами, два одинаковых (изоморфных) графа должны обладать свойством одновременно, т.е. не может так случиться, что один из них обладает свойством, а второй — нет. Например, свойство «содержать треугольник» — это множество всех графов, содержащих треугольник. Попробуем теперь это свойство формализовать. Сделать это можно следующим образом:

pastedGraphic_2.png

Это формула языка первого порядка. Разумеется, формула истинна на некотором графе тогда и только тогда, когда этот граф обладает рассматриваемым свойстве. Одним из основных параметров формулы первого порядка является кванторная глубина формулы. Известно, что истинность формулы первого порядка глубины pastedGraphic_3.png проверяется на pastedGraphic_4.png-вершинном графе за pastedGraphic_5.png. В этой связи возникает естественный вопрос: какова наименьшая кванторная глубина формулы, записывающей свойство «содержать подграф, изоморфный графу pastedGraphic_1.png»? Об этом и подобных вопросах и пойдет речь в нашем курсе.




Дмитрий Андреевич Захаров (матфак ВШЭ) — «Нулевые суммы векторов»

Известная задача: пусть дано 2n-1 целое число, тогда среди них можно выбрать ровно n, которые в сумме делятся на n. Легко понять, что число 2n-1 в этой задаче не улучшаемо. В курсе я расскажу про доказательства этого утверждения, а также мы будем заниматься многомерным обобщением этой задачи. А именно, пусть в d-мерном пространстве дано m целочисленных векторов; спрашивается, каким большим должно быть m, чтобы среди этих векторов обязательно нашлись ровно n векторов, сумма которых делится на n (иными словами, центр масс этих n точек тоже является целочисленной точкой). Естественно перейти от целых чисел к остаткам по модулю n, тогда нашей целью будет нахождение набора из n векторов, дающих в сумме ноль (откуда и происходит название курса).

Задача была поставлена в семидесятых годах прошлого века, но до сих пор широко открыта, например, точный ответ известен только при размерности d=1, 2. Тем не менее, человечеству известно довольно много красивых результатов на эту тему, о которых я и собираюсь рассказать.

Доказательства теорем курса будут по большей части алгебраические. Поэтому от слушателей необходимо понимание того, что такое кольцо остатков по модулю n, знакомство с базовыми вещами типа Малой Теоремы Ферма. Желательно, но не обязательно понимание более продвинутых понятий: поле, кольцо многочленов, ранг матрицы. Определения этих понятий я напомню на лекции. 




Дмитрий Геннадьевич Ильинский (ФПМИ МФТИ, школа 179) — «Алгоритмы проверки простых чисел»

В современной криптографии важную роль играют эффективные алгоритмы для проверки большого случайного числа на простоту. Мы поговорим о нескольких алгоритмах (тест Ферма, тест Соловея-Штрассена, тест Миллера-Рабина, тест Люка-Лемерра), о задаче дискретного логарифмирования, где они применяются. Если останется время, поговорим о полиномиальном алгоритме проверки простоты чисел.




Алексей Константинович Ковалев (НИУ ВШЭ, ФИЦ ИУ РАН) — «Введение в методы искусственного интеллекта»

Словосочетание «искусственный интеллект» часто встречается в заголовках новостей, но не всегда ясно, что оно означает. На этом курсе мы постараемся разобраться, о чём всё-таки идёт речь. И для этого мы познакомимся с историей возникновения этой области и популярными сейчас направлениями, такими как машинное обучение, планирование и обучение с подкреплением. Подробно разберемся в некоторых используемых методах. Также мы поговорим о современных тенденциях в этой области: объяснимом (XAI) и общем (AGI) искусственном интеллекте.




Даниил Владимирович Мусатов (ФПМИ МФТИ) — «Задача о выборах комитета»

Вопросы общественного выбора волновали человечество со времён позднего средневековья. О них писали каталонский мыслитель Рамон Льюль, французские просветители XVIII века, британец Чарльз Доджсон (более известный как Льюис Кэрролл) и множество математиков и экономистов XX и XXI веков. В мини-курсе мы поговорим про задачу о выборах комитета, когда нужно выбрать не одну альтернативу, а набор из нескольких. Даже постановка задачи может быть принципиально разной в зависимости от целей. Мы рассмотрим 3 подхода:

– нужно выбрать набор из самых лучших альтернатив. Например, составляется шорт-лист претендентов на какую-нибудь премию или список соискателей вакансии, которых позовут на интервью.

– нужно выбрать самый разнообразный набор. Например, авиакомпания выбирает, какие фильмы загрузить в развлекательную систему, чтобы наибольшему числу пассажиров понравилось.

– нужно пропорционально представить интересы общества. Такая постановка часто встречается в политике при выборах парламента.

Разные постановки требуют разных алгоритмов. Мы опишем несколько процедур, изучим их свойства и посмотрим, как они работают на различных примерах.




Андрей Михайлович Райгородский (ФПМИ МФТИ, мехмат МГУ, Яндекс) — «Проблема изоморфизма графов»

Речь пойдет о классической проблеме теории графов — проблеме изоморфизма графов. Графы называются изоморфными, если существует такая нумерация их вершин, в которой множества их ребер совпадают. Можно ли по двум данным графам быстро понять, изоморфны ли они? Это до сих пор не решенная задача является одной из самых важных в теории графов и в теории алгоритмов. Мы расскажем о некоторых ее аспектах, в том числе о том, что произойдет, если рассмотреть случайные графы.




Алексей Владимирович Савватеев (Университет Дмитрия Пожарского, ФПМИ МФТИ) — «Первообразные корни и построение правильных многоугольников с помощью циркуля и линейки»

Ненулевые остатки по модулю простого числа всегда могут быть перечислены путём возведения в квадрат, куб, четвёртую и более высокие степени одного из них; это — очень красивое и весьма нетривиальное утверждение. Более того, указать на тот остаток, который таким образом породит все остальные, тоже непросто.

Я расскажу пару доказательств существования такого остатка, который называется первообразным корнем по модулю данного простого числа. На основании полученных результатов я покажу, как строить с помощью циркуля и линейки правильные многоугольники.




Андрей Дмитриевич Сандлер (ФИВТ МФТИ, Яндекс) — «Задача достижимости на полигональных динамических системах»

Гибридные системы — это особый класс динамических систем, которые развиваются одновременно в дискретном и в непрерывном пространствах. Приложения таких систем находятся во многих задачах, где исследуемый объект развивается во времени. Простым случаем гибридной системы является полигональная динамическая система, где динамика в каждой выпуклой области задаётся некоторым константным потоком.

Задача достижимости формулируется для таких систем с целью проверить, попадёт ли интересующая нас система в определённое состояние после старта. Если какие-то состояния системы считаются небезопасными, то проверка достижимости таких состояний — это важная задача, называемая в иностранной литературе «safety verification». Вот о методах решения такой задачи мы в целом и поговорим. Разберём классический плоский случай, которым занимался ещё Пуанкаре, докажем невычислимость для задачи достижимости в pastedGraphic_6.png и придём к совсем открытой проблеме в пространстве двумерных многообразий, где лектором только что получен интересный результат, использующий конструкцию графов Рози.

Курс не подразумевает каких-либо специальных знаний, постараюсь рассказать все основные понятия по ходу дела. Однако, знание того, что такое конечный автомат и машина Тьюринга, будет полезным.




Евгений Юрьевич Смирнов (матфак ВШЭ, НМУ) — «Замощения доминошками»

Всякий, кто ходил на математический кружок, знает, что если из доски 8х8 вырезать два противоположных угла, то оставшуюся фигуру нельзя замостить в один слой доминошками 2х1. Более интересно изучать фигуры, которые замостить можно; про них можно выяснять, сколькими способами это можно сделать (подумайте, например, сколько способов замостить прямоугольник 2 x n). А еще можно брать фигуры не на клетчатой бумаге, а на бумаге “в треугольничек”, и доминошки в форме ромба с углами 120 и 60 градусов.

Мы поговорим про примеры таких задач, в частности, про подсчет числа замощений “ацтекского бриллианта” на клетчатой бумаге и шестиугольника на бумаге “в треугольник”, а также разберем различные методы подсчёта числа замощений фигур: конденсацию Доджсона (этот английский математик более известен как писатель Льюис Кэрролл), метод непересекающихся путей и др.




Артемий Алексеевич Соколов (мехмат МГУ) — «Диаграммы Фарея, цепные дроби и топокарты»

Диаграмма Фарея строится итерационно — сначала в ней есть числа 0 и 1, затем между каждыми двумя рациональными числами добавляется их сумма по «правилу двоечника» — между числами a / b и c / d записывается число (a + c) / (b + d). 

Цепной дробью называется выражение вида  

Топокарты — картинки, которые возникают при изучении целых квадратичных форм (выражений 

вида ax^2+bxy+cy^2, где a, b, c — целые).

На лекциях мы поймем, каким удивительным образом эти три понятия между собой связаны.




Thomas Fernique (CNRS, University Paris 13) — «Упаковки шаров»

Как положить как можно больше монеток на стол так, чтобы одна на другую не накладывалась? Мы все знаем (хотя это было доказано только в 1940), что центры монет нужно расположить в вершинах треугольной решëтки. В

этой лекции мы рассмотрим, что случится, если мы меняем размерность (шары вместо дисков) или количество разных радиусов. В первом случае мы будем говорить о теореме Kepler–Hales (1610–2014) и о теории самокорректирующихся кодов, а во втором о физике конденсированного состояния и апериодическом порядке.




Дмитрий Владимирович Щелчков (Google) — «Поиск оптимальной стратегии в дереве игры»

Большое количество игр можно представить в виде графа, где вершины – это состояния в игре, а ребра – это действия игроков. Поиск оптимальной стратегии в таком случае становится поиском некоторого пути на графе, но при этом поиск “в лоб” зачастую работает непозволительно долго. Для решения этой проблемы используют прунинг (отсечение путей, которые заведомо не приведут к выигрышной стратегии), а также различные эвристики или оценочные функции.

В рамках этого курса вы реализуете алгоритм для игры “змейку”. На лекциях мы будем изучать различные идеи и алгоритмы, которые помогут вам в создании бота, а в конце курса будет проведен турнир между лучшими стратегиями.