Белов-Канель Алексей Яковлевич (Bar-Ilan University), Golafshan Mehdi (ФПМИ МФТИ) — «Mathematical billiards»
Голованов Александр Игоревич (ФПМИ МФТИ) — «Свёртки на любой вкус»
Рассмотрим следующую задачу: даны две последовательности $(a_0, \ldots, a_n)$ и $(b_0, \ldots, b_n)$, найти последовательность $(c_0, \ldots, c_n)$, для которой $\displaystyle c_k = \sum_{f(i, j) = k}a_ib_j$. Говорят, что $c$ является результатом свёртки последовательностей $a$ и $b$. В зависимости от выбора функции $f$ и пространства, в котором находятся объекты, эта задача может представлять разный интерес, иметь различные решения и приложения. Например, если $f(x, y) = x + y$, то это просто задача о перемножении многочленов, и с её помощью можно решать задачи о делении многочленов, интерполяции и многие другие. Если $f(x, y) = xy$, то такая свёртка называется свёрткой Дирихле, и с её помощью можно находить сумму функции Эйлера на префиксе натурального ряда за $O(n^{2/3})$. Наконец, если $f(x, y) = x\oplus y$ или другая битовая операция, то такой свёрткой можно эффективно решать различные задачи подсчёта.
Мы рассмотрим эти три вида свёрток и научимся производить их быстро. Курс рассчитан на людей, увлекающихся как математикой, так и олимпиадным программированием.
Жуковский Максим Евгеньевич (ФПМИ МФТИ) — «Описательная сложность графовых свойств»
Каким образом можно формализовать графовое свойства “содержать подграф, изоморфный заданному”, “быть связанным”, “быть двудольным”? Мы поговорим о формализациях этих свойств с помощью различных логических языков, а также о связи этих формализаций со сложностью проверки свойств. Оказывается, что все результаты, о которых пойдет речь, можно получать с помощью некоторой игры на графах, известной под названием “игра Эренфойхта”. Благодаря этой игре утверждения, относящиеся к формальной логике, удается доказать комбинаторно.
Мусатов Даниил Владимирович (ФПМИ МФТИ) — «Теоремы о неподвижных точках и их вычислительная сложность»
Простейшая модель экономического равновесия заключается в том, что кривые спроса и предложения пересекаются в одной точке, которая даёт равновесную цену. Однако если товаров много, и цены одних влияют на спрос на другие, то ситуация становится значительно сложнее. В середине XX века был доказан ряд теорем о существовании равновесных цен. В них использовались теоремы о неподвижных точках, которые разрабатывались к тому времени уже несколько десятилетий. В мини-курсе мы изучим несколько базовых теорем о неподвижных точках (лемму Шпернера, ККМ-лемму, теорему Брауэра и др.), а также обсудим вопрос об их вычислительной сложности: как можно не просто доказать существование неподвижной точки, а найти её алгоритмически, и насколько сложно это сделать. Специальных предварительных знаний не требуется, всё необходимое будет рассказано в самом курсе.
Райгородский Андрей Михайлович (ФПМИ МФТИ, мехмат МГУ) — «Системы общих представителей»
Савватеев Алексей Владимирович (ФПМИ МФТИ) — «ПИ и Е. Жизнь двух констант математики»
Между Пи и Е существует незримая связь, обеспечиваемая Формулой Эйлера — главной формулой математики. Помимо этой связи, их роднит сложнейшая арифметическая природа — оба они «трансцендентные», то есть ни одно из них двоих не является корнем никакого многочлена с целыми коэффициентами.
Тонкости приближения числа Пи вскрыты Эйлером (а число Е и так прекрасно приближается «своим» рядом обратных факториалов). Об этом и обо многом другом я и расскажу в миникурсе! Бонус-трек: трансцендентность Е (особенно ПИ) доказывается муторно, но иррациональность обеих констант мы докажем!
Садовников Александр Владимирович (Сириус) — «Анализ данных в Python»
Аналитик — это человек, который занимается анализом данных пользовательского сервиса. Одним из главных навыков аналитика является умение быстро и качественно отвечать на вопросы про аудиторию платформы. И зачастую для того, чтобы ответить на какой-то вопрос, в распоряжении аналитика есть только данные, ограниченное количество времени и любимая среда разработки.
В рамках курса мы поставим себя на место аналитиков и изучим основные технологии, которые позволяют быстро и эффективно анализировать данные в Python. В частности, познакомимся с библиотекой pandas, предназначенной для анализа табличных данных, а также с самыми популярными библиотеками для визуализации данных — matplotlib и seaborn.
Смирнов Евгений Юрьевич (ВШЭ, НМУ) — «Суммы степеней и числа Бернулли»
Скорее всего, все знают формулы для нахождения суммы первых n чисел:
$$1 + 2 + … + n = n(n+1)/2,$$
их квадратов:
$$1^2 + 2^2 + … + n^2 = n(n+1)(2n+1)/6,$$
кубов:
$$1^3 + 2^3 + … + n^3 = n^2 (n+1)^2 / 4.$$
А как найти сумму $1^k + 2^k + … + n^k$ для произвольного $k$?
Мы попробуем угадать, как должен выглядеть ответ в этой задаче, а потом обсудим и объясним полученные закономерности. Общий ответ можно сформулировать в терминах чисел Бернулли; в курсе будет объяснено, что это за числа и как их вычислять. Кстати, сам Якоб Бернулли писал, что с помощью изобретенного им метода нашёл сумму десятых степеней первой тысячи натуральных чисел в течение “менее половины четверти часа”.
Соколов Артемий Алексеевич (ФПМИ МФТИ, 179 школа) — «Диаграммы Фарея, цепные дроби и топокарты»
Диаграмма Фарея строится итерационно — сначала в ней есть числа 0 и 1, затем между каждыми двумя рациональными числами добавляется их сумма по «правилу двоечника» — между числами a / b и c / d записывается число (a + c) / (b + d).
Цепной дробью называется выражение вида $\displaystyle a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots}}}}}$
Топокарты — картинки, которые возникают при изучении целых квадратичных форм (выражений вида $ax^2+bxy+cy^2$, где $a$, $b$, $c$ — целые).
На лекциях мы поймем, каким удивительным образом эти три понятия между собой связаны.
Черкашин Данила Дмитриевич (СпбГУ) — «Вокруг ёмкости Шеннона графа С_5»