Анонсы курсов

Алексей Яковлевич Белов-Канель (Bar-Ilan University, ФИВТ МФТИ) «Группы и мозаики»

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


Всеволод Александрович Воронов (ИДСТУ СО РАН) «Упаковки шаров»

С древнейших времен люди старались уложить бревна в сарае или поместить апельсины в ящик наиболее экономным способом.Старейшая математическая постановка данной задачи принадлежит Кеплеру. Как следует располагать одинаковые шары, чтобы они занимали максимальную долю объема при размерах ящика, стремящихся к бесконечности? Эта задача вошла в число знаменитых благодаря обманчиво простой формулировке и долгой истории безуспешных попыток её решения. В двумерном случае доказательство оптимальности гексагональной упаковки было закончено в 1940 году, в трехмерном — лишь к концу XX века. Если для плоскости доказательство было впоследствии значительно упрощено, то в пространственном случае и по сей день нет разумного и доступного для непосредственной проверки рассуждения, не использующего компьютерный перебор.

Мы разберем лучшие из известных доказательств для плоскости и постараемся приблизиться к пониманию техники, позволившей М. Вязовской и соавторам в 2016 году доказать, что аномально плотные упаковки шаров в размерностях 8 и 24 являются наилучшими. На этом пути нам встретятся многомерные решетки и преобразования Фурье. Первая часть курса не требует предварительных знаний; для понимания второй части желательно знать, что такое интеграл, и ориентироваться в \mathbb{R}^n.


Антон Сергеевич Гусев (мехмат МГУ) «Уравнения Пелля»

Задачи

Уравнения Пелля – это уравнения вида x^2 - my^2 = 1, где m — натуральное число, не являющееся точным квадратом. Они представляют собой класс диофантовых уравнений второй степени и связаны со многими важными задачами теории чисел.

Решение уравнений Пелля – задача непростая, хотя и выполнимая методами элементарной математики. Полное описание решений этих уравнений и является нашей конечной целью.

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


Алексей Вадимович Доледенок (мехмат МГУ) «Покрытие полосами»

Задачи

Конспект лекций

Представьте, что вы пробили в полу дырку. Чтобы не свалиться на голову соседям, вы эту дырку должны как-то заделать, а у вас есть только дощечки разной ширины. В этой щекотливой ситуации вам на помощь придёт теорема Банга-Тарского, которая расскажет, что надо делать. В первой части курса мы рассмотрим проблему с разных сторон: если дощечек много, если дощечек мало, если дощечки хрупкие. Во второй части с помощью выработанных методов мы научимся решать ещё несколько интересных родственных задач.

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


Дмитрий Ильинский (ФИВТ МФТИ) «Формула обращения Мёбиуса»

Задачи

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


Даниил Мусатов (ФИВТ МФТИ, РЭШ) «Интерактивные системы доказательств»

Задачи

Привычная форма доказательства, особенно математического, — это некоторый текст, убеждающий в справедливости заданного утверждения. Такой текст в идеале существует сам по себе, независимо от личностей его создателя и читателя. Требуется лишь общее соглашение о системе аксиом и правилах логики. Мы изучим три альтернативных подхода к понятию доказательства, где уверенность в справедливости утверждения возникает после общения доказывающего (прувера) и проверяющего (верификатора). В этих подходах очень важна вычислительная ограниченность верификатора по сравнению с прувером, а также использование случайных битов и связанная с этим небольшая вероятность ошибки.

Первый подход называется «интерактивные доказательства»: в ходе общения по некоторому протоколу прувер с вероятностью 99\% убедит верификатора в верном утверждении и лишь с вероятностью 1\% — в неверном. Второй подход — «доказательства с нулевым разглашением» — расширяет первый. Здесь протокол построен таким образом, что верификатор не узнаёт ничего сверх истинности утверждения. В частности, никакого текста доказательства у него не остаётся. В третьем подходе — «вероятностно проверяемых доказательствах» — текст как раз есть, но очень и очень длинный. Верификатор читает лишь небольшую часть и тем не менее удостоверяется в его справедливости.


Андрей Михайлович Райгородкий (ФИВТ МФТИ, мехмат МГУ) «Решетки в пространствах: на стыке комбинаторики, геометриии теории чисел»}

Задачи 1 Задачи 2

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


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

Задачи

Если число, состоящее из одних единиц («десятичный репьюнит»), делится на 2017, то оно делится также и на 9. Это удивительно, если учесть тот факт, что 2017 на 9 не делится. Однако верно. Почему?

Объяснение кроется в свойствах мультипликативной группы конечного поля остатков по модулю 2017 (наш год — простой!).Кроме того, если решать «вручную», возникает необходимость формулировать и доказывать «кубический закон взаимности» Эйзенштейна. Это всё — красивейшие разделы математики.

На лекции мы пройдёмся по всем основным пунктам решения поставленной выше задачки, заодно делая экскурс в кубический мир Эйзенштейна. До кучи, может быть, вспомним и квадратичный закон взаимности Гаусса, его «Золотую теорему».


Андрей Сандлер (Яндекс) «Задача достижимости в полигональных гибридных системах»

Задачи

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

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

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


Артемий Соколов (мехмат МГУ) «Цепные дроби и константа Хинчина»

Задачи

Любое вещественное число \alpha можно представить в виде

\alpha = a_0+\cfrac{1}{a_1+\cfrac{1}{a_2+\cfrac{1}{a_3+\cfrac{1}{\ddots}}}}

которое называется цепной, или непрерывной дробью.
Оказывается, что для почти всех \alpha последовательность x_n = \sqrt[n]{a_0 \ldots a_n} имеет предел K, которой при этом не зависит от числа \alpha и K\approx2{.}685452.

Этот удивительный факт несложно вытекает из эргодической теоремы Биргхофа-Хинчина, о которой по большей части и пойдет речь.

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


Михаил Тихомиров (ФИВТ МФТИ) «Как играть в комбинаторные игры»

Речь пойдет о последовательных антагонистических играх для двух игроков с полной информацией. Что все это значит?

— В игре с полной информацией игроки не могут иметь друг от друга секретной информации (в отличие, например, от покера, где игроки не знают карт друг друга).
— В антагонистической игре результатом является победа ровно одного из игроков (в том же покере результатом является количество выигранных/проигранных денег).
— В последовательной игре игроки совершают ходы по очереди, а не одновременно (как, например, в игре «камень-ножницы-бумага»).

Мы обсудим некоторые интересные классы таких игр и возникающие при их анализе теории (нимберы и их аналоги для циклических игр, сюрреальные числа Конвея и пр.). Кроме этого, уделим отдельное внимание тому, как подходить к вопросу алгоритмически и писать эффективные программы для их анализа.


Лев Шабанов (ФИВТ МФТИ) «Дистанционные графы и теоремы типа Турана»

Задачи

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

Дистанционные графы — один из наиболее интересных классов в графов, возникающих в комбинаторной геометрии. С дистанционными графами связана открытая проблема Нельсона—Хадвигера о наименьшем числе цветов, в которое можно покрасить плоскость или пространство так, чтобы любые две точки на расстоянии 1 были разноцветными.

В данном курсе будет рассказана теорема Турана, некоторые ее обощения, помимо этого вы узнаете, что такое дистанционные графы и некоторые интересные факты о них, а главный результат, который мы получим в данном курсе это аналог турановской оценки для дистанционных графов. От слушателей требуется владение базовыми терминами теории графов. Зачет по курсу будет в форме листков с задачами.