Буланкина Вера Валерьевна (школа 444, школа 2007) — «Разбиения на доминошки и всякое-разное»
Знакомясь с рекуррентными соотношениями вы все почти наверняка решали задачу про количество замощения доминошками полоски . Возможно где-то в этот момент вы задумывались, сколькими способами можно разбить на доминошки произвольный прямоугольник или хотя бы квадрат… В 1961 году было доказано, что число замощений прямоуголь ника размера доминошками задаётся далеко не самой очевидной формулой. Подход к доказательству этой формулы весьма симпатичен: он связывает разбиения на доминошки с числом совершенных паросочетаний графа и линейной алгеброй. Кроме того, он достаточно универсален и обобщаем на другие интересные объекты, в частности на так называемый Ацтекский бриллиант. На первой лекции мы рассмотрим именно этот подход, а дальше, в зависимости от наших успехов, посмотрим, куда можно развиваться вокруг этой задачи и какие есть тенденции новее, чем 1961 год =)
Ильинский Дмитрий Геннадиевич (ФПМИ МФТИ, школа 179) — «Теория общественного выбора»
Мини-курс будет посвящён изучению и анализу свойств различных систем выборов. Довольно длительное время (основы теории были заложены ещё в конце 18-го века) велись поиски идеальной системы выборов, которая бы удовлетворяла некоторым “естественным” требованиям. В 1952-м году было доказано, что для случая двух кандидатов под такие критерии подходит простое большинство. А в 1970-м году Кеннет Эрроу доказал, что для случая трёх (и большего количества) кандидатов “идеальной” системы выборов не существует. В частности за этот результат Эрроу получил Нобелевскую премию по экономике в 1972-м году.
Мы обсудим разные механизмы выборов и их свойства, теорему Эрроу и различные её вариации. Если останется время, также обсудим выборы с несколькими победителями, когда нужно выбрать не одну альтернативу, а несколько.
Предварительных знаний не требуется (за исключением базовой теории множеств), всё необходимое будет определено в рамках курса.
Канель-Белов Алексей Яковлевич (ФПМИ МФТИ, Bar-Ilan University, Shenzhen University) — «Теорема Жордана»
Миникурс посвящен доказательству утверждения, очевидного для каждого математика — но нетривиального для математика: кривая (гомеоморфный образ окружности) делит плоскость на две части, а также родственных утверждений: теорема Брауэра о неподвижной точке, теоремы Лебега о покрытиях (клетки клетчатого куба раскрашены в 3 цвета, тогда существует одноцветный путь, соединяющий противоположные грани) и некоторых других.
Климанова Ирина (ФПМИ МФТИ) — «Криптография на эллиптических кривых»
Наверное, все слышали что-нибудь о криптографии. На основе криптографических протоколов решаются всевозможные задачи шифрования, создаются методы безопасного хранения и передачи данных, организуются интернет-платежи и даже онлайн выборы.
Для того, чтобы успешно передавать информацию, не боясь взлома, хочется, чтобы тот, кто “подслушивает”, не смог бы расшифровать послание. Для этого пользуются так называемой “трудностью” некоторых задач. Довольно часто под этим понимается, что человечество еще не научилось решать задачу за разумное время (какой смысл перебирать пароль от чьего-то аккаунта в одноклассниках, если это займет 1000 лет? тут уже и взламывать расхочется). Но прогресс не стоит на месте, и есть риск, что какие-то задачи со временем начнут решаться быстрее. Это делает имеющиеся алгоритмы менее эффективными и более медленными.
Тогда на помощь приходят другие методы. Один из них — криптография на эллиптических кривых.
В рамках курса мы обсудим некоторые классические алгоритмы шифрования, поймем как перенести их на эллиптические кривые и при чем здесь сложение точек.
Если вам нравятся: алгоритмы, шифры, теория чисел, проективная геометрия, смело приходите! Для понимания курса желательно комфортно себя чувствовать при работе с остатками. Специальных знаний не требуется, все необходимые определения введем на лекциях.
Мещерин Илья Семирович (ФПМИ МФТИ) — «Алгоритмы быстрого разложения чисел на множители»
Одна из важных задач теории чисел – задача факторизации, то есть разложения чисел на множители. Эта задача важна хотя бы потому, что на ее трудности основывается криптостойкость популярного алгоритма шифрования RSA. Если научиться достаточно быстро раскладывать длинные числа на множители, то мы научимся так же быстро взламывать RSA. В отличие от задачи проверки простоты, для задачи факторизации до сих пор не известно полиномиального алгоритма, но и не доказано, что эта задача NP-полная. Наивный алгоритм (перебор делителей до корня) имеет экспоненциальную сложность. В нашем миникурсе мы рассмотрим некоторые алгоритмы разложения на множители, более быстрые, чем наивный (например, алгоритм Ро Полларда). В планах рассмотреть субэкспоненциальный алгоритм квадратичного решета, позволяющий за приемлемое время факторизовать числа длиной до 100 цифр.
Молодцов Филипп (ФПМИ МФТИ) — «Прямо-двойственный метод или как линейное программирование позволяет решать нерешаемые задачи из программирования»
Большое количество исследовательских алгоритмических задач, которые приходится решать на практике часто оказываются NP-трудными. На текущем уровне понимания человеком это значит, что скорее всего такие задачи нельзя решить за полиномиальное время. Однако тот факт, что их нельзя решить точно, не ставит крест на попытках получить хорошие результаты. Зачастую их можно решать приближенно с любой наперёд заданной точностью.
Этот курс будет посвящён Линейному Программированию – разделу на стыке оптимизации и алгоритмов. Первая часть будет посвящена краткому введению в линейную алгебру. Затем с помощью этих идей мы научимся решать большой класс задач, в которых возникает линейность. Кроме того, мы получим другой универсальный взгляд на традиционные комбинаторные результаты связанных с паросочетаниями и потоками. Под конец курса мы рассмотрим практический алгоритм, который позволит решать задачу о максимальном потоке с несколькими парами стоков и истоков приближённо.
Для меня применения линейной алгебры в неожиданных алгоритмических задачах оказались невероятно красивыми, хоть и немного техничными. Надеюсь окажутся они таковыми и для вас.
Неустроева Елизавета (ФПМИ МФТИ, ЦПМ) — «Безошибочная передача информации»
Представьте, что у вас есть канал связи, по которому можно передавать сообщения, используя ограниченный набор символов, например, нули и единицы или буквы русского алфавита. При этом некоторые символы можно перепутать при приеме сообщения. Например, при плохой телефонной связи можно на слух перепутать «Б» и «П». Для каждого набора символов можно построить граф, в котором вершины — это символы, а ребрами соединяются пары символов, которые можно перепутать.
Мы исследуем, как свойства этого графа влияют на максимальную скорость передачи информации, а точнее, изучим шенноновскую емкость различных графов — величину, по которой скорость определяется. Самому Шеннону удалось найти емкости многих маленьких графов, но вопрос о емкости цикла на пяти вершинах долгое время оставался открытым, пока Ласло Ловас не нашел удивительно изящное решение. Мы познакомимся с этим решением и его обобщениями.
Также мы обсудим другой подход к вопросу безошибочной передачи информации: что, если если при передаче некоторые символы могут замениться на другие, но такие замены происходят не очень часто? В этом случае помогут «коды, исправляющие ошибки» — красивые с комбинаторной точки зрения структуры.
Некоторые доказательства курса будут основываться на линейно-алгебраических идеях, но никаких предварительных знаний не предполагается: будем обсуждать интересные и сложные вещи в комфортном для слушателей темпе.
Райгородский Андрей Михайлович (ФПМИ МФТИ) — «Топологические методы в комбинаторике»
Рябичев Андрей Дмитриевич (матфак ВШЭ, НМУ, школа 179) — «Бесконечные графы и грубая геометрия»
Обычно геометрия — евклидова, аффинная, конформная, проективная,… — изучает преобразования и их инварианты. Указанные преобразования объединяет то, что все они по меньшей мере непрерывны, то есть, говоря неформально, переводят близкие точки в близкие. Но что если сосредоточить внимание не на “близких” точках, а, наоборот, следить за “далёкими”? Этим как раз и занимается грубая геометрия, изоморфизмы в которой (например такие как взятие целой части R→Z) могут быть разрывны, а инварианты и методы позволяют описывать пространства в широком (large scale) масштабе. Инструменты грубой геометрии хорошо приспособлены также для работы с дискретными пространствами, такими как графы или конечно порождённые группы.
Мы поговорим о том, как построить грубую структуру на пространстве и как описать инварианты грубых преобразований — такие как кривизна, размерность или “устройство на бесконечности”. В числе прочего, если позволит время, мы докажем теорему Столлингса и поговорим про аменабельность. Мини-курс планируется насыщенным, но вполне элементарным, для понимания не помешает знать определения группы и метрического пространства, но даже они будут наполнены при необходимости.
Савватеев Алексей Владимирович (ФПМИ МФТИ) — «Школьная теория групп»
Начальную теорию групп можно (на факультативных занятиях) изучать в средних классах – примерно тогда же, когда вводится символьное обозначение (буквы x,y,z и т.п.). Потому что ступень абстракции, ведущая к общему понятию группы от систем остатков по данному модулю (с одной стороны) и перестановок (с другой), не выше, чем ступень абстракции от чисел 3,4,5 к символам. Остатки и перестановки же являются излюбленными кружковыми темами.
В миникурсе я ликвидирую пробелы школьного образования, относящиеся к теории групп (и к конкретным примерам групп). Будут установлены базовые факты про вычеты, доказана малая теорема Ферма, исследованы подгруппы групп перестановок на трёх и четырёх символах, введено понятие нормальной подгруппы данной группы и простоты группы.
Если будет время, то мы далее докажем, что группа чётных перестановок на пяти символах – простая (что откроет желающим дорогу к изучению вопросов о разрешимости алгебраических уравнений в радикалах), разберём теорему Шаля, группу Эйлера и RSA-шифрование и др.
Садовников Александр Владимирович (Сириус.Курсы) — «Введение в машинное обучение»
В рамках курса вы познакомитесь с азами машинного обучения — науки, которая лежит в основе современных технологий искусственного интеллекта. Машинное обучение исследует алгоритмы, которые буквально учатся решать поставленную задачу на основе реальных примеров.
Из курса вы научитесь формулировать задачу в терминах машинного обучения, поймёте, из каких этапов состоит её решение и какие математические модели для этого используются. В частности, познакомитесь с одними из самых распространённых моделей — моделями линейной и логистической регрессии.
Если успеем, то также изучим принцип работы механизма внимания и архитектуру «трансформер», на которой основаны современные большие языковые модели 🙂
Соболевский Андрей Николаевич (ВШСМ МФТИ) — «Базельская задача: как ее решил Леонард Эйлер и как еще ее можно решать»
Базельская задача — это общепринятое, но исторически не совсем верное название вопроса о величине суммы обратных квадратов натуральных чисел. Мы начнем с небольшого обсуждения того, почему это вопрос является осмысленным. Оказывается, что даже приближенная численная оценка этой суммы очень трудна и быстро превратилась в вид спорта, популярный среди математиков XVII-XVIII веков.
После этого мы увидим, как Леонард Эйлер, которому в тот момент было чуть больше двадцати лет, сначала поставил в этом виде спорта мировой рекорд, который и сейчас кажется сверхчеловеческим (если не знать секрет его достижения), а через четыре года смог получить окончательный ответ к самой Базельской задаче: искомая сумма равна одной шестой квадрата константы «пи» — отношения длины окружности к ее диаметру. Мы детально проследим за тем, как Эйлер добрался до обоих этих результатов.
Основная идея решения, найденного Эйлером, требует строгого обоснования, которое появилось лишь около ста лет спустя благодаря Карлу Вейерштрассу. Самому Эйлеру и его современникам пришлось удовлетвориться тем, что нестрого полученный ответ с любой точностью воспроизводится аккуратными численными оценками — а значит, он не может быть ошибочным. Однако спустя 86 лет Огюстен-Луи Коши опубликовал в своем «Курсе анализа» другое, элементарное и притом строгое решение Базельской задачи. Мы расскажем о решении Коши и, если останется время, еще об одном решении, основанном на рядах Фурье, которые тоже были изобретены в начале XIX века.
Стырт Олег Григорьевич (ФПМИ МФТИ) — «Цепные дроби»
Планируется получить разложение произвольного числа в цепную дробь и его свойства, такие как взаимная однозначность и преимущество как приближения: сходимость подходящих дробей и её скорость. Ряд доказательств особенно удобны и красивы на матричном языке, но в случае недостаточной осведомлённости аудитории они будут проделаны непосредственно. Дополнительное время, при его наличии, уйдёт на критерий периодичности цепной дроби.
Шубин Яков Константинович (ФПМИ МФТИ) — «Семейства множеств с запрещенными пересечениями»
Рассмотрим классический вопрос экстремальной теории множеств. Какое наибольшее число k-элементных подмножеств n-элементного множества можно выбрать, если попарные пересечения множеств не могут принимать значения из множества L? В общем виде данный вопрос остаётся открытым, однако для разных частных случаев существуют изящные способы решения этой задачи. Например, если множество L состоит только из нуля, то задача красиво решается двойным подсчётом (теорема Эрдеша-Ко-Радо). Саму теорему ЭКР А.М. Райгородский уже доказал на своей лекции, а мы же найдём решение поставленной задачи в менее тривиальных случаях, а также рассмотрим некоторые обобщения.
Яровиков Юрий Николаевич (ФПМИ МФТИ) — «Теорема Банаха-Тарского и инвариант Дена»
Мини-курс будет посвящён двум весьма увлекательным математическим теоремам, которые связаны ровно двумя вещами. Во-первых, обе теоремы — про то, можно ли трёхмерное тело разрезать на части и сложить из этих частей что-то другое. Во-вторых, для доказательства теорем (а мы обе теоремы докажем) нам понадобится аксиома выбора.
Сюжет 1. Можно ли разрезать апельсин на несколько частей и сложить из этих частей два апельсина того же размера? Оказывается, можно, и когда впервые слышишь формулировку этого факта, кажется, что собеседник оговорился. Но нет: мы разберём теорему Банаха-Тарского, которая показывает, что шар радиуса 1 можно разделить на конечное количество частей, из которых можно собрать два шара того же радиуса. Обсуждение этой теоремы затронет различные области математики: теорию меры, аксиоматику теории множеств и теорию групп. Этому сюжету будут посвящены первые две лекции.
Сюжет 2. Если даны два многогранника одинакового объёма, всегда ли можно разрезать один из них на части и собрать из них другой? Ответ отрицательный. Эта задача — третья проблема Гильберта, и её решение, несмотря на сложность, доступно для понимания старшими школьниками. Этому сюжету будет посвящена третья лекция.
Курс обещает быть насыщенным и непростым, но не потребует особых знаний. Будет полезно понимать, что такое бесконечность и почему точек на отрезке [0, 1] больше, чем натуральных чисел.