Ильинский Дмитрий Геннадиевич (ФПМИ МФТИ, школа 179) — «Вероятностные тесты на простоту»
В современной криптографии важную роль играют эффективные алгоритмы для проверки большого случайного числа на простоту. Все такие алгоритмы можно разделить на две группы: детерминированные и вероятностные. В нашем курсе мы изучим несколько различных примеров, в частности тесты Ферма и Миллера-Рабина. Для понимания алгоритмов мы изучим (повторим, если необходимо) базовые утверждения про системы вычетов (остатков): малую теорему Ферма, теорему Эйлера, теорему Вильсона, существование первообразного корня.
Канель-Белов Алексей Яковлевич (ФПМИ МФТИ, Bar-Ilan University, Shenzhen University) — «Апериодические точки внешних бильярдов вокруг правильных многоугольников. Применение инвариантов Дена, Хадвигера. »
Разберем метод численных инвариантов в геометрии (Дена, Хадвигера, и т. п.). Рассмотрим такие задачи как, перекладывание отрезка, третья проблема Гильберта, перекройка круга в квадрат.
Для внешних бильярдов вокруг правильных многоугольников, при помощи похожих инвариантов, получим достаточное условие существования апериодической точки в области. Покажем существование апериодической точки для всех n-угольников, кроме нескольких частных случаев.
Комаров Станислав Игоревич (школа 179) — «Введение в теорию полей. Конечные поля»
Кошелев Михаил Михайлович (ФПМИ МФТИ) — «Паросочетания на графах»
Пусть есть n юношей и n девушек, некоторые из которых знакомы друг с другом. Как определить, есть ли способ поженить их между собой таким образом, чтобы каждый жених был знаком со своей невестой? Ответ на этот вопрос дает классическая теорема Холла или теорема о свадьбах. В курсе мы обсудим, как доказывать эту теорему и как быстро построить такое разбиение на пары. Помимо этого, мы разберемся, что делать с аналогичной задачей, если нам надо разбивать на пары не юношей и девушек, а, например, n сотрудников для выполнения проектов. Кроме того, мы посмотрим и на приложения этой теории вроде поиска минимальных вершинных покрытий и максимальных независимых множеств в двудольных графах.
Для понимания курса предварительных знаний не требуется, разве что, возможно, на последней лекции нам потребуется немного теории вероятностей.
Куссев Андрей Станиславович (ФПМИ МФТИ) — «Эргодическая теория и алгоритм Метрополиса-Гастингса»
Генерация случайных сущностей иногда может представлять собой далеко не простую задачу. Как, например, построить случайную перестановку чисел от 1 до n да так, чтобы сумма циклов в ней было больше определённого числа, да так, чтобы всякая такая перестановка могла появиться равновероятно, притом что количество этих перестановок нам точно неизвестно?
В этом нам поможет случайное блуждание по графу, которое (более формально) называют марковской цепью: при грамотном ее построении можно приблизить даже такие изощренные распределения.
Куда примечательнее, что под капотом сего алгоритма (именуемого в честь Метрополиса и Гастингса) скрывается фундаментальный результат, известный в теории вероятностей как эргодическая теорема. На лекции мы обсудим одно из её доказательств, которое включает в себя множество изобретательных техник и представляет самостоятельный интерес.
От слушателей требуется лишь толика усидчивости и знание базовой теории вероятности (которую мы, впрочем, всё равно слегка повторим в начале)
Мусатов Даниил Владимирович (ФПМИ МФТИ) — «Доказательства с нулевым разглашением»
В детских книгах-гляделках «Где Уолли?» нужно найти Уолли на картинке с огромным количеством других персонажей. Представьте, что у маленького ребёнка никак не получается решить эту задачу. Он начинает отчаиваться и думает, что Уолли на картинке вообще нет. Как его ободрить, доказав, что Уолли есть, но не давая подсказку? Есть такой вариант: сделать достаточно большую непрозрачную картонку с маленьким окошком по центру, через которое показать только Уолли. Если картонка вдвое шире и выше страницы, то она в любом случае накроет страницу, и никакой подсказки не будет. Такой подход называется доказательством с нулевым разглашением: слушатель убеждается, что утверждение верное, но доказательства не узнаёт. В мини-курсе мы познакомимся с другими подобными примерами, изложенными как метафорически, так и математически, а затем поговорим об их приложениях в современной криптографии: для безопасной идентификации, распределённых вычислений, обработки чувствительных данных и т.д.
Райгородский Андрей Михайлович (ФПМИ МФТИ) — «Случайные графы»
Рябичев Андрей Дмитриевич (ВШМ МФТИ, НМУ, школа 179) — «Автоморфизмы римановых поверхностей»
Самые известные примеры римановых поверхностей — сфера Римана (род 0) и эллиптическая кривая (род 1). Я расскажу, какие ещё бывают римановы поверхности, как их можно строить и под какими углами на них можно смотреть.
Также мы поговорим про автоморфизмы римановых поверхностей, что бы это ни значило, и попробуем доказать 84(g-1)-теорему. Наконец, если останется время, мы немного обсудим разветвленные накрытия, проблему Гурвица и детские рисунки Гротендика — оказывается, топология и комплексный анализ таят в глубине неожиданно богатую комбинаторику.
Слушателям предлагается подумать над следующей задачей: сколько перестановок на n элементах можно представить в виде fhf-1h-1, где f — цикл на n элементах, а h — произвольная перестановка?
Савватеев Алексей Владимирович (ФПМИ МФТИ) — «Кубическая математика: Шарыгинские треугольники и другие сюжеты, приводящие к эллиптическим кривым»
Я расскажу про самую красивую область математики, так или иначе касающуюся практически всех других областей (в том числе, практики — через функционирование криптовалюты биткойн). Это теория эллиптических кривых. Сложение точек на кривой третьего порядка придумал Диофант Александрийский, но он не понял, что там кроется групповая операция (ибо не дошел всё-таки до понятия группы, либо дошел, но поместил в 7-13 тома своих сочинений, которые сгорели и до нас не дошли). Пуанкаре это понял. Самое сложное — это то, что сложение точек ассоциативно. Мы попробуем это доказать. Заодно я расскажу о нескольких красивейших задачах из жизни, сводящихся к эллиптическим кривым. Кстати, и Великая Теорема Ферма доказана именно на базе развиваемой техники!!
Савватеев Михаил Алексеевич (ФПМИ МФТИ) — «Нижние границы оракульной сложности алгоритмов для поиска минимального значения функции»
Представьте, что у вас есть “относительно хорошая” функция, и вы хотите уметь быстро находить ее минимум. Например, наименьшее кол-во денег, которое придётся потратить на дорогу до Комбалга, или наименьшее кол-во усилий, которое придётся приложить на побег обратно домой.
Конечно, на практике не так важно, потратить на дорогу 1000 рублей или 1003, более того, время вычисления ответа тоже может варьироваться в зависимости от того, насколько вам повезло с функцией, данными и т.д.
Попробуем решать более размытую задачу: как бы побыстрее найти значение, отличающееся от минимума функции не более, чем на , ещё и допуская при этом ошибку любой величины с вероятностью не больше P.
Универсальный ответ: никак! Оказывается, совершенно не важно, как выглядит алгоритм, что ему разрешается такая свобода и подаются на вход достаточно “неплохие” [выпуклые и L-липшицевы] функции — всё равно можно сконструировать некоторое семейство данных, на котором он почти всегда будет отрабатывать не меньше, чем за const(1)… Чего?
Вызовов оракула 🙂 В первом приближении можно считать, что обращений к функции с целью узнать в очередной точке её значение и производную.
А ведь я ещё никак не ввёл понятие алгоритма… В общем, вы могли заметить, что нюансов много. Их аккуратным описанием, а после относительно строгим конструированием таких “плохих” для алгоритмов функций я и займусь на курсе 🙂
Пререквизиты: для комфортного прохождения курса желательно достаточно уверенно работать с логарифмами и экспонентами, а также представлять себе, что такое производная и вероятность.