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

Архив задач

Александр Воронцов (ИПМ им. М.В. Келдыша РАН, школа «Интеллектуал», Яндекс) «ADE-классификация»

Многие задачи в математике сводятся к классификации различных объектов. Удивительным образом, во многих, совершенно не
связанных между собой задачах возникает одинаковая классификация: две бесконечных серии объектов (An и Dn) и три
«исключительных» объекта (E6, E7 и E8).

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

Задача об ADE-классификации считается открытым вопросом в математике в том смысле, что пока никто не может объяснить глубинную причина сходства этих классификаций.


Олег Герман (мехмат МГУ) «Сферическая геометрия и наглядная астрономия»

Долгое время я жил в одном большом доме. Однажды, в день летнего солнцестояния, я обнаружил, что солнце встаёт прямо по курсу (если взгляд перпендикулярен плоскости окна). Чуть позже я сменил комнату – окна стали выходить в другом направлении, под углом 90 градусов по отношению к предыдущему. К своему удивлению я обнаружил, что в день зимнего солнцестояния солнце опять встаёт прямо по курсу!
Вопрос первый, простой: где север?
Вопрос второй, более сложный: на какой широте находится этот дом?
На эти и на многие другие подобные вопросы мы и научимся отвечать на занятиях.


Фёдор Ивлев (мехмат МГУ) «О расстоянии между множествами объема ε внутри n-мерного
тела единичного объема при n→∞»

Известно, что диаметр n-мерного тела единичного объема стремится к
бесконечности при n→∞. Тем не менее, для хороших тел
наблюдается странное явление: расстояние между подмножествами объема
ε к бесконечности стремиться не может! Рассказ будет посвящен
многомерной геометрии.


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

Все мы сталкивались с понятием «информация» и её измерением. Мы
знаем, что на флешке помещается меньше информации, чем на жестком
диске. Но как выразить математически это бытовое понятие? Например,
утверждается, что 15 июля в Сахаре не будет дождя. Такая фраза
вызывает улыбку. Тем не менее, какая-то информация заключена в этом
прогнозе. Какая именно, и как это измерить? Почему трит это log_2(3)
бит?

Курс будет посвящен этим и другим проблемам теории информации.


Яна Кашинская (ФИВТ МФТИ) «Алгоритмы: куча, дерево отрезков, декартово дерево»

Анонс (PDF)


Ярослав Кищенко (Яндекс, ФИВТ МФТИ) «Векторное программирование»

Векторное програмирование – это стиль програмирования, когда вместо операций с отдельными переменными производят операции с векторами и матрицами. Данный стиль становится очень популярным в современных скриптовых языках, таких как Python или R. Векторное програмирование сильно связано с линейной алгеброй, поэтому с его помощью можно решать огромное количество чисто матемтических задач. Также код становится более лаконичным (исчезают циклы и ветвления), а встроеное распараллеливание позволяет обрабатывать большие объемы данных.

В курсе будут предложенны задания по сведению математических задач из теории игр и других областей к векторной форме и численному их решению с помощью библиотеки NumPy (вместо Python можно будет использовать R). Знание данной библиотеки необязательно, весь необходимый материал будет освещён в курсе.


Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Занимательная криптография»

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

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


Глеб Ненашев (Стокгольмский университет) «Немного об остовных деревьях графа»

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

1) Теорема Кэли о том, что количество остовных лесов в полном графе на n вершинах равно nn-2.

2) Пусть дан граф c некоторым полным порядком на ребрах. Ребро графа называется активным для подлеса, если, добавив его к подлесу, мы получим цикл, причем в этом цикле добавленное ребро окажется минимальным. Будет рассказано, как перечислить количество остовных деревьев с фиксированной активностью через полином Татта; в частности, это количество не зависит от выбранного порядка ребер.

3) О G-parking`ах: откуда они возникают; биекциях между ними и остовными лесами. Об этом подробнее уже на лекции.


Роман Просанов (мехмат МГУ) «Двумерные поверхности и графы на них»

Многие из вас знают, что такое графы. Некоторые также наверняка сталкивались с таким понятием, как планарные графы: те графы, которые можно нарисовать на плоскости без самопересечений по рёбрам. Это очень интересный и довольно хорошо изученный объект. Но помимо обычной плоскости, графы можно рисовать на любых двумерных поверхностях. Здесь, для простоты, под двумерной поверхностью можно понимать границу какого-нибудь твёрдого тела в трёхмерном пространстве: например, границу шара (это, конечно, сфера) или границу бублика (называемую тором). Реализации графов на них связана с фундаментальными характеристиками этих поверхностей, изучаемых таким разделом математики, как топология. Ими мы и займёмся. Для курса достаточно базового представления о том, что такое граф, хотя бы на уровне определения.


Андрей Михайлович Райгородский (ФИВТ МФТИ, Яндекс) «Проблема Борсука»

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


Алексей Савватеев «Геометрия, евклидова и неевклидова»

Андре Вейль сказал однажды, что за душу каждого математика борются ангел

топологии и дьявол абстрактной алгебры. Все предыдущие созывы школы я был

формально на стороне дьявола, хотя и не очень ему потакал (в любой алгебре

всегда прячется красивая геометрия). Нынче я буду целиком на белой стороне!

Конкретно, мы рассмотрим группы движений трёх основных геометрий – обычной
плоской евклидовой геометрии, сферической геометрии и геометрии Лобачевского.

По пути к последней из трёх мы пройдём через проективные преобразования нашей
обычной плоскости. Геометрические постулаты Евклида, история создания геометрии
Лобачевского, теорема о трёх гвоздях для всех трёх геометрий, порождение групп
движений отражениями, классификация движений (теорема Шаля), арифметика
композиций движений, углы и площади, двойное отношение – вот круг вопросов,
который будет в идеале освещён в течение миникурса. Насколько мы сможем
продвинуться, зависит от аудитории. Приходите все!


Михаил Тихомиров (Яндекс) «Алгебра и алгоритмы»

Наверняка многие из слушателей знакомы с базовыми алгебраическими объектами (векторы, матрицы, многочлены, кольца, поля и т.д.); кроме того, вы можете знать некоторые алгоритмы, связанные с ними (например, метод Гаусса для решения системы линейных уравнений, или алгоритм Евклида для нахождения наибольшего общего делителя чисел или многочленов). Мы подробно поговорим про эти и другие алгоритмы, связанные с различными областями алгебры; помимо этого, мы увидим, как алгебра может использоваться в продвинутых алгоритмах для решения сложных задач, самих по себе с алгеброй не связанных.

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


Тома Ферник (CNRS, University Paris 13) «Как долго нужно тасовать карты?»

В рифлёной (или американской) тасовке используется тасовка двух половин колоды карт. Это – тщательное и быстрое смешивание. Но насколько быстрое? Сколько раз надо тасовать половины колоды карт?
Мы разберём этот вопрос, который затрагивает перемешивание цепи Маркова – живой и центральной части современной теории вероятностей.
Программа курса:
– Введение в цепи Маркова
– Рифлёная тасовка
– Были бы три руки…


Данила Черкашин (СПбГУ) «Случайные пути в графах»

Рассмотрим конечный граф и зафиксируем две различные его вершины x и y.
Теперь рассмотрим два различных способа определить случайный простой (без самопересечений) путь
между x и y.

Первый способ (uniform spanning tree) заключается в рассмотрении случайного (с равными вероятностями) остовного дерева – в нём будет ровно один путь между x и y.

Второй же способ (loop-erased random walk) – выйти из вершины x и ходить по случайным рёбрам, пока не придём в y, а затем стереть все петли так, чтобы получился простой путь.

Мы докажем эквивалентность этих способов и немного поговорим о мотивации задачи.