Воронов Всеволод Александрович (КМЦ АГУ) — «Хроматические числа двумерных поверхностей»
В классической задаче о хроматическом числе плоскости требуется найти наименьшее число цветов, которое понадобится, чтобы покрасить плоскость при условии, что никакие две точки на единичном расстоянии не будут покрашены одинаково.
За прошедшие с появления этой задачи 70 лет было придумано множество ее вариантов: измеримое хроматическое число, хроматическое число плоскости при раскрасках карты, хроматическое число при интервале запрещенных расстояний и т.д.
Мы поговорим о задачах, в которых недавно удалось найти окончательный ответ, и, если позволит время, об их обобщениях на случаи тора и сферы.
Канель-Белов Алексей Яковлевич (ФПМИ МФТИ, Bar-Ilan University, Shenzhen University) — «Иррациональность и трансцендентность»
Всем говорят в школе, что число $\pi$ иррационально и даже – трансцендентно, т. е. не является корнем многочлена с целыми коэффициентами. Имеется изящное и вполне элементарное доказательство Эрмита иррациональности числа $\pi$ (требующее только знания интегрирования по частям – понимания как вычислить интеграл $\int_a^b x^k\sin(x) dx$).
Наша цель – доказательство трансцендентности числа $e$,
Мы поговорим о теореме Линдемана–Вейерштрасса (если $\alpha_i$ линейно независимые над $\mathbb Q$ алгебраические числа, то $e^{\alpha_i}$ алгебраически независимы), а также теореме Гельфонда (если числа $\alpha\ne 0,1$; $\beta\notin{\mathbb Q}$ алгебраические, то $\alpha^\beta$ есть число трансцендентное).
Метелев Дмитрий (ФПМИ МФТИ) — «Производящие функции и количество неупорядоченных разбиений натуральных чисел»
На курсе мы познакомимся с аппаратом производящих функций, с помощью которого можно легко доказывать некоторые тождества, минуя комбинаторные рассуждения.
Также будет рассмотрено приложение данной техники к задаче вычисления $p(n)$ количества неупорядоченных разбиений натурального числа $n$, что позволит нам улучшить асимптотику алгоритма до $O(n^{3/2})$, по сравнению с наивной реализация за $O(n^2)$.
Ближе к концу мы поговорим об интересных свойствах последовательности $p(n)$, которая сложна в анализе, но от этого не менее интересна.
Неустроева Елизавета (ФПМИ МФТИ, ЦПМ) — «Сколько независимых множеств?»
Независимым множеством в графе называется непустое множество его вершин, никакие две из которых не соединены ребром. Сложная и интересная задача — найти по графу размер его самого большого независимого множества, но мы займемся другим вопросом: какое максимальное количество независимых множеств может быть в графе? А точнее, какое максимальное количество независимых множеств может быть в графе на n вершинах, степень каждой из которых равна d?
В 1990-х годах математиком Алоном была выдвинута гипотеза о том, что это число не превосходит 
В рамках курса мы разберем это доказательство и увидим, как элегантно случайность помогает в задачах, которые на первый взгляд никак с ней не связаны.
Для понимания курса желательно не бояться логарифма (можно только двоичного), знания теории вероятностей не предполагаются, все необходимые определения будут рассказаны на лекциях.
Райгородский Андрей Михайлович (ФПМИ МФТИ) — «Решётки и их приложения в комбинаторике»
Рябичев Андрей Дмитриевич (матфак ВШЭ, НМУ, школа 179) — «Алгоритм распознавания планарности графов»
Пусть задан граф G без петель и кратных рёбер. Можно придумать алгоритм, проверяющий, планарен G или нет. Предлагаю слушателям решить следующие подготовительные задачи: (а) запишите какой-нибудь такой алгоритм; (б) оцените время его работы в зависимости от количества вершин n.
Оказывается, можно предъявить полиномиальный алгоритм (работающий за O(n^6)). В этом удивительным образом помогают приёмы из алгебраической топологии — группы когомологий и препятствующие коциклы. При этом полученный алгоритм легко реализовать, а также несложно обосновать без использования топологии.
Использованный подход непосредственно обобщается на высшие размерности, становясь уже технически более запутанным. Например, некоторые 3-циклы можно заклеить треугольниками и спросить, вложим ли полученный гиперграф в трёхмерное пространство. Об этих обобщениях мы поговорим, если останется время.
Для понимания курса требуется уметь решать системы линейных уравнений с произвольным количеством неизвестных, предварительные знания топологии у слушателей не предполагаются.
Савватеев Алексей Владимирович (ФПМИ МФТИ) — «Квадратичная математика»
Квадратичные расширения полей и колец позволят нам :
- решить уравнение $y^2 = x^3 – 1$ в целых числах;
- решить уравнение Пелля $y^2 – 2 x^2 = 1$ (и план решения остальных уравнений Пелля);
- доказать Рождественскую теорему Ферма $p=x^2+y^2$ для простых $p$ вида $4k+1$;
- в одну строчку найти все Пифагоровы тройки
- обсудить одну из самых красивых элементарных нерешённых задач — задачу Эрдёша о равных расстояниях (отрезках).
На закуску останется квадратичный закон взаимности, но это уже как пойдёт.
Савватеев Михаил (ФПМИ МФТИ, школа 179) — «Разделение слов КС-грамматиками»
Скорее всего, вы знаете про ПСП (правильные скобочные последовательности) и умеете их задавать простым набором правил: $S \rightarrow \varepsilon;\; S \rightarrow (S);\; S \rightarrow SS$.
Например: $()\,, ()()\,, ()((())())()$ являются ПСП, а $()(\,$, $)\,$, $())($ – нет.
В науке такой способ называется КС-грамматикой, а множество строк, которые можно породить соответствующими правилами – языком.
А теперь представьте, что у вас уже есть 2 строки, например, $aba$ и $aab$.
И вам хочется найти достаточно маленькую (что бы это ни значило 🙂 КС-грамматику, которая бы разделяла их – содержала в порождённом ею языке ровно одну строку из двух.
В итоге, мы докажем следующие верхние и нижние оценки:
- Если слова имеют разную длину $\leqslant\!n$, мы всегда можем найти грамматику размера $O(\log(\log(n)))$, при этом оценка не улучшаема.
- Если длина слов одинаковая, существует разделяющая их грамматика размера $O(\log(n))$, при этом всегда есть какая-то пара слов, не разделяемых никакими грамматиками размера $o\big(\frac{\log(n)}{\log(\log(n))}\big)$.
Пререквизиты: желательно достаточно свободно понимать логарифмы.
Садовников Александр Владимирович (Сириус) — «Основы исследовательского анализа данных»
Развитие современных технологических компаний невозможно без анализа данных. Например, если речь идёт про онлайн-сервисы, решения об их изменениях принимаются на основе анализа того, как ведут себя пользователи. С целью понять, как клиенты отреагирует на те или иные нововведения, компании даже проводят специальные эксперименты.
Специалисты, которые занимаются анализом данных, называются аналитиками. В силу специфики своей работы аналитик должен обладать абсолютно разными компетенциями: уметь общаться с заказчиками исследований, формулировать исследовательские гипотезы и проверять их с помощью данных.
В этом мини-курсе вы изучите основные подходы, которые применяют аналитики при исследовании данных, а также узнаете, почему аналитик — это в первую очередь математик.
Сандлер Андрей Дмитриевич (Nebius AI) — «Разбираем ChatGPT на запчасти»
Совершенно недавно в мире “искусственного интеллекта” произошёл очередной прорыв, связанный с появлением больших языковых моделей (ChatGPT, Google Bard, Bing AI). На данном мини-курсе, не вдаваясь в детали обучения таких систем, доступных только самым большим IT-компаниям, мы всё же постараемся осветить некоторые интересные вопросы из этой области.
Что внутри у ChatGPT? Может ли нейронная сеть сделать математическое открытие? В чём принципиальное различие между текстом, написанным нейросетью, и текстом, написанным человеком, и почему пока рано бояться того, что нейросети отнимут у всех работу?
Предварительных знаний для понимания курса не требуется. Будет немножко мат. анализа и data science, все непонятные моменты разберём подробно.
Трушков Владимир Викторович (школа 2101) — «Задача Иосифа Флавия»
По легенде, во время Иудейской войны за независимость в одной крепости осталось совсем мало воинов. И чтобы не попасть римлянам в плен, они выстроились в круг и начали убивать каждого третьего. Но двое, среди которых был Иосиф Флавий, вычислили места, которые будут у выживших, и встали туда.
Решение почти этой задачи (когда убивают не каждого третьего, а каждого второго) приводит к интересным рекуррентным соотношениям, которые удаётся даже до конца решить, используя различные системы счисления.
Собственно, про решения рекуррент и будет говориться в мини-курсе.