Александр Воронцов (ИПМ им. М.В. Келдыша РАН, школа «Интеллектуал», Яндекс) «ADE-классификация»
Многие задачи в математике сводятся к классификации различных объектов. Удивительным образом, во многих, совершенно не связанных между собой задачах возникает одинаковая классификация: две бесконечных серии объектов (An и Dn) и три «исключительных» объекта (E6, E7 и E8).
На курсе мы обсудим различные сюжеты, в которых эта классификация возникает. Некоторые удастся рассказать подробно, некоторые – только в виде обзора.
Задача об ADE-классификации считается открытым вопросом в математике в том смысле, что пока никто не может объяснить глубинную причина сходства этих классификаций.
Олег Герман (мехмат МГУ) «Сферическая геометрия и наглядная астрономия»
Долгое время я жил в одном большом доме. Однажды, в день летнего солнцестояния, я обнаружил, что солнце встаёт прямо по курсу (если взгляд перпендикулярен плоскости окна).Чуть позже я сменил комнату – окна стали выходить в другом направлении, под углом 90 градусов по отношению к предыдущему. К своему удивлению я обнаружил, что в день зимнего солнцестояния солнце опять встаёт прямо по курсу!
Вопрос первый, простой: где север?
Вопрос второй, более сложный: на какой широте находится этот дом?
На эти и на многие другие подобные вопросы мы и научимся отвечать на занятиях.
Фёдор Ивлев (мехмат МГУ) «О расстоянии между множествами объема ε внутри n-мерного
тела единичного объема при n→∞»
Известно, что диаметр $n$-мерного тела единичного объема стремится к
бесконечности при $n \rightarrow \infty$. Тем не менее, для хороших тел
наблюдается странное явление: расстояние между подмножествами объема
$\varepsilon$ к бесконечности стремиться не может! Рассказ будет посвящен
многомерной геометрии.
Алексей Яковлевич Канель-Белов (ФИВТ МФТИ, Bar-Ilan University) «Теория информации»
Все мы сталкивались с понятием «информация» и её измерением. Мы знаем, что на флешке помещается меньше информации, чем на жестком диске. Но как выразить математически это бытовое понятие? Например, утверждается, что 15 июля в Сахаре не будет дождя. Такая фраза вызывает улыбку. Тем не менее, какая-то информация заключена в этом прогнозе. Какая именно, и как это измерить? Почему трит это $\log_2(3)$ бит?
Курс будет посвящен этим и другим проблемам теории информации.
Яна Кашинская (ФИВТ МФТИ) «Алгоритмы: куча, дерево отрезков, декартово дерево»
Ярослав Кищенко (Яндекс, ФИВТ МФТИ) «Векторное программирование»
Векторное програмирование – это стиль програмирования, когда вместо операций с отдельными переменными производят операции с векторами и матрицами. Данный стиль становится очень популярным в современных скриптовых языках, таких как Python или R. Векторное програмирование сильно связано с линейной алгеброй, поэтому с его помощью можно решать огромное количество чисто матемтических задач. Также код становится более лаконичным (исчезают циклы и ветвления), а встроеное распараллеливание позволяет обрабатывать большие объемы данных.
В курсе будут предложенны задания по сведению математических задач из теории игр и других областей к векторной форме и численному их решению с помощью библиотеки NumPy (вместо Python можно будет использовать R). Знание данной библиотеки необязательно, весь необходимый материал будет освещён в курсе.
Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Занимательная криптография»
Традиционно слово «криптография» ассоциируется с различными задачами шифрования. Однако современные приложения гораздо шире. В самом общем виде криптографическую задачу можно поставить так: нужно построить протокол обмена информацией, чтобы кто надо узнал что надо, а все остальные ничего лишнего не узнали.
В мини-курсе мы обсудим несколько конкретных задач, которые решаются без применения сложных технических приёмов. Одной из таких задач является задача об обедающих криптографах. Трое криптографов после обеда в ресторане узнали, что за всех троих заплачено заранее. Они хотят узнать, кто заплатил: кто-то из них или кто-то извне, но так, чтобы в первом случае не было известно, кто именно.
Глеб Ненашев (Стокгольмский университет) «Немного об остовных деревьях графа»
Остовное дерево графа – это связный подграф без циклов (подлес – это не обязательно связный), их изучаются очень давно. Мы затронем классические результаты и около того; к примеру, будет рассказано:
1) Теорема Кэли о том, что количество остовных лесов в полном графе на $n$ вершинах равно $n^{n-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$, а затем стереть все петли так, чтобы получился простой путь.
Мы докажем эквивалентность этих способов и немного поговорим о мотивации задачи.