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

Тимур Аминов (ФУПМ МФТИ) — «Введение в теорию алгоритмов»
Все мы знакомы с интуитивным понятием алгоритма. Строгое формальное определение дать не так легко, и с ходу неясно, зачем оно нужно. В курсе мы познакомимся с двумя сюжетами, где без формализации не обойтись. Первый сюжет – неразрешимые проблемы, т.е. задачи, у которых в принципе не может быть алгоритмического решения. Почему такие существуют и как в принципе можно доказать отсутствие решения? Второй сюжет – сложность алгоритмических задач. Как понять, когда одна задача принципиально сложнее, чем другая, или имеет ровно такую же сложность? На простых и интересных примерах мы познакомимся с этими вопросами, важными для понимания сути понятия алгоритма.


Алексей Яковлевич Белов (Bar-Ilan University) — «Быстрое умножение матриц и многозначных чисел и тензорный ранг»

Курс посвящен компьютерной алгебре и сложности вычислений. Всем известно, как умножать числа в столбик. На первый взгляд кажется, что для умножения n-значных чисел нужно n^2 элементарных операций. Однако неожиданно в 1960 году А. Карацуба придумал алгоритм делать это за n^{\log_2(3)} операций. Позднее Тоом усовершенствовал этот алгоритм.

На первый взгляд кажется что для умножения матриц n-го порядка нужно n^3 умножений, однако неожиданно Штрассен обнаружил что хватает n^{\log_2(7)} уножений.


Всеволод Воронов (ИДСТУ СО РАН) — «Геометрия сходящихся рядов и число Пи»

В курсе будет рассказано о способах вычисления Пи при помощи бесконечных рядов и о доказательствах корректности этих способов, в том числе придуманных совсем недавно. Почему, к примеру, сумма ряда обратных квадратов равна \frac{\pi^2}{6} и как это связано с окружностью? В одних случаях формулы, изобретенные при помощи запутанных преобразований, получили неожиданную геометрическую интерпретацию; в других вывод изначально был основан на геометрических соображениях; в третьих не найдено какого-либо элементарного подхода к доказательству и трудно представить, что такой подход существует. Мы обсудим некоторые замечательные формулы и их доказательства, элементарные и не очень.

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


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

Теорема Хелли широка известна, но также заслуживают внимания ее обобщения и теоремы нужные для ее доказательства.

Мы познакомимся с теоремами Радона, Каратеодори, Хелли, Тверберга и обобщим их до “цветных” и “частичных” аналогов.

На плоскости эти аналоги звучат так:

1.  На плоскости дано несколько выпуклых множества трех цветов. Известно, что любые три множества разных цветов пересекаются. Тогда существует цвет такой, что все множества этого цвета пересекаются.

2. На плоскости дано несколько выпуклых множества. Известно, что случайно выбранные три множества пересекаются с вероятностью хотя бы p. Тогда существует точка, которая принадлежит хотя бы \alpha(p) n фигурам.


Дмитрий Захаров (матфак ВШЭ) — «Некоторые задачи дистанционных графов»

Мы будем изучать граф G(n, r, s): его множество вершин — это все r-элементные подмножества \{1, \ldots, n\}, причем мы соединяем ребром пары множеств, пересекающихся ровно по s элементам. Важной его характеристикой является хроматическое число — наименьшее число цветов, в которое можно покрасить вершины графа так, чтобы все ребра были разноцветными. Я постараюсь объяснить, что задача поиска хроматического числа $G(n, r, s)$ важна, и расскажу, как можно пытаться ее искать.  Для понимания курса будет полезно знать основы линейной алгебры.


Даниил Мусатов (ФИВТ МФТИ) — «Вероятностные алгоритмы»

Использование случайности при вычислениях позволяет значительно ускорить решение некоторых задач, хотя и добавляет возможность ошибки. В мини-курсе мы познакомимся с основами теории вероятностных вычислений. На первой лекции мы подробно изучим два вероятностных теста на простоту: Миллера-Рабина и Соловея-Штрассена. На второй лекции мы познакомимся с разными классами задач, которые решаются вероятностными алгоритмами, и соотношениями между ними. На третьей лекции мы обсудим, как можно уменьшить число использованных случайных битов (в идеале до нуля) и откуда брать случайные биты в реальности, если до нуля уменьшить не получилось. Лекции почти не зависят друг от друга, можно приходить на любую комбинацию.


Александр Панов (МФТИ) — «Искусственный интеллект: наука или технология?»

На серии занятий мы рассмотрим с вами, что сейчас понимаю под научным направлением искусственного интеллекта. Проведём обзор основных направлений и рассмотрим два примера практических задач: обучение с подкреплением и эвристическое планирование.


Андрей Михайловий Райгородский (ФПМИ МФТИ, Яндекс, мехмат МГУ) — «Об одной задаче теории графов»

Назовем лесом граф, у которого все связные компоненты – деревья. Сколько нужно лесов, чтобы покрыть все ребра заданного графа? Это один из глубоких вопросов теории графов, имеющий отношение к оценке сложности алгоритмов. Очень быстро мы поймем, что ответ как будто совсем простой и лежит на поверхности. Но вот неприятность: доказать, что наш ответ правильный, – нерешенная проблема! В курсе мы изучим несколько чрезвычайно красивых инструментов на стыке теории графов, теории чисел и теории вероятностей, которые позволят нам приблизиться к решению этой проблемы.


Филипп Рухович (ФИВТ МФТИ) — «Комбинаторная теория игр»

Данный курс содержит основы активно развивающейся отрасли математики – комбинаторной теории игр. В первую очередь, будут рассматриваться детерминированные игры для двух игроков с конечным числом состояний и нулевой скрытой информацией. Мы рассмотрим, как можно обобщить игры, изучим теории Шпрага-Гранди и Смита, а также поймем, каким образом можно применять эти теории для программирования эффективных алгоритмов построения выигрышных стратегий.


Алексей Владимирович Савватеев (Университет Дмитрия Пожарского, ФИВТ МФТИ) — «Квадратичный закон взаимности»

Квадратичный закон взаимности является утверждением о том, что из разрешимости сравнения p=x^2 (\mod q) можно вывести разрешимость или неразрешимость сравнения q=y^2 (\mod p), где p,q~— различные нечётные простые числа (то есть, не равные 2). Конкретно, достаточно хотя бы одному из этих простых чисел давать остаток 1 при делении на 4, чтобы разрешимость этих двух сравнений наступала одновременно; если же оба имеют вид 4k+3, то разрешимость одного сравнения будет, напротив, эквивалентна неразрешимости второго. Дополнительно нечто утверждается про квадратичный характер числа 2, после чего возможно быстро и эффективно проверить квадратичный характер любого числа по модулю любого другого. Мы рассмотрим примеры, а также докажем все сформулированные утверждения (воздав честь и хвалу Гауссу!).


Абдурахмон Садиев (ФУПМ МФТИ) — «Дискретное преобразование Фурье»

На лекциях мы познакомимся с важным вычислительным инструментом: дискретным преобразованием Фурье (ДПФ), – а также с алгоритмом его вычисления, быстрым преобразованием Фурье (БПФ). Данное преобразование широко применяется в алгоритмах цифровой обработки, а также при анализе частот дискретного сигнала. На лекциях мы научимся применять БПФ и ДПФ для поиска подстрок, перемножения многочленов и решения систем линейных уравнений.


Андрей Сандлер (ФИВТ МФТИ, Яндекс) — «Гибридные системы»

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

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

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


Артемий Соколов (мехмат МГУ) — «Спектральная теория графов»

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

Изюминкой курса станет доказательство того, что гипотеза Борсука о разбиении множества на меньшие части неверна в размерности 65.

Никаких особых знаний для освоения курса не требуется.


Дмитрий Щелчков (ФИВТ МФТИ, Яндекс) — «Геометрия слов»

Похожи ли по смыслу слова “отпечатки” и “опечатки”? А “основание” и “фундамент”? Любому школьнику легко ответить на эти вопросы, однако компьютеру ответы на них отнюдь не очевидны. Один из способов обучения компьютера такому знанию – модель word2vec. В ней каждому слову сопоставляется точка в многомерном пространстве так, чтобы близкие по смыслу слова были рядом, а разные – далеко. О ней и будет рассказ.

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

Лекции рассчитаны на широкую аудиторию, однако для выполнения практических заданий нужен будет ноутбук и базовое знание Python.


Константин Яковлев (МФТИ) — «Алгоритм A* для планирования траектории мобильного робота»

В рамках мини-курса мы рассмотрим как задача планирования траектории робота сводится к задаче поиска пути на графе специального вида. Поговорим о том, что это за графы, откуда они берутся и как выглядят.
Детально разберем алгоритм A*, который наиболее часто используется для поиска на подобных графах. Разберём примеры. В завершении запрограммируем A* на Python.