Беклемишев Лев Дмитриевич (РАН, НИУ ВШЭ, МГУ) — «Быстрорастущие функции»
Как можно коротко записывать очень большие числа? Эта задача интересовала еще Архимеда. В лекции будет рассказано о функциях катастрофически быстрого роста, которые возникают в комбинаторике и математической логике. Самые впечатляющие из них связаны с утверждениями, которые нельзя ни доказать, ни опровергнуть, используя стандартные аксиомы формальной арифметики.
Белов-Канель Алексей Яковлевич (Bar-Ilan University) — «Сферы и их отображения»
Что может быть проще сферы? Однако…
Отображения сферы в сферу высшей размерности стягиваются в точку, отображения сферы размерности выше 1 в одномерную сферу (т.е. окружность) тоже стягиваются в точку. А что произойдет, если отображать сферы высшей размерности в двумерную сферу? Наука мало что знает… И это одна из основных проблем современной математики. В последнее время значительный прогресс был достигнут Ромой Михайловым.
Предполагается рассказать конкретно об отображении сферы на себя и отображении трехмерной сферы на двумерную, а про остальные случаи – рассказать о зоопарке.
Брагин Владимир Алексеевич (ЦПМ) — «Начало спектральной теории графов»
В графе у любой вершины степень равна k, у любых двух соседних вершин нет общих соседей, а у любых двух несоседних ровно один общий сосед.
Так вот, оказывается, что такая ситуация возможна далеко не для всех k. Так точно бывает для k=2 (придумать пример элементарно), k=3 (построить пример сложнее, это так называемый граф Петерсена), k=7 (построение такого примера, графа Хоффмана-Синглтона — непростая задача для топовых олимпиадников). Неизвестно, бывает ли пример для k=57, а для всех остальных точно не бывает! Вот так!
Помогут разобраться с этим сюжетом идеи из линейной алгебры. Поймём, как матрицы связаны с отображениями линейных пространств, увидим интересные следствия из неоднозначности этой самой связи.
Если слушатель не знаком с понятием линейного пространства, то есть шанс потеряться в начале курса, но я очень постараюсь, чтобы этого не произошло.
Бурцев Михаил Сергеевич (ФПМИ МФТИ) — «Разговорный искусственный интеллект»
Сегодня, все больший и больший объем коммуникации между людьми перемещается в цифровые каналы. Это открывает новые возможности для использования диалоговых интеллектуальных агентов. Благодаря революции глубокого обучения в области нейросетевых технологий диалоговые системы в ближайшее время могут перейти на качественно новый уровень.
В лекции будет рассказано об основных принципах построения современных диалоговых систем и представлены последние достижения в данной области.
Гейн Андрей Александрович — «Reverse engineering: что делать, если вы скомпилировали программу и потеряли её исходники»
Представьте невероятное — вы написали программу на С++ и скомпилировали её. В результате получилась готовая программа, её ещё называют исполняемым файлом. В винде это файл .exe, в линуксе он чаще всего не имеет расширения. Можно ли по этому файлу, не имея исходников, узнать, что делает программа?
Оказывается, это непросто, но возможно. Это и называется reverse engineering — «обратная разработка» (ужасный перевод, да?). В частности, ревёрсом занимаются вирусные аналитики в антивирусных компаниях — изучая вирусы и других зловредов они придумывают способы защититься от них.
Во время мини-курса вы узнаете, как работают процессоры, как операционные системы запускают программы, а ещё мы, конечно, разревёрсим парочку примеров. Обязательно будет возможность развёрсить что-нибудь самостоятельно 🙂
Жуковский Максим Евгеньевич (ФПМИ МФТИ) — «Перколяции в графах»
Пусть H — остовный подграф G (т.е. у H и у G одинаковые множества вершин, а любое ребро из H является ребром и в G). Перколяцией называется процесс, в котором на каждом шаге добавляется одно ребро, и таким образом из графа H получается граф G. Пусть F — некоторый другой граф (как правило его размер сильно меньше размера графа G). Тогда F-перколяцией называется такая перколяция, при которой на каждом шаге в строящийся граф добавляется хотя бы одна новая “копия” графа F.
С помощью F-перколяции моделируют многие физические явления, а также процессы распространения эпидемий. Зададимся следующим фундаментальным вопросом. Каково наименьшее количество ребер в графе H таком, что существует F-перколяция в G? Пусть, например, G — полный граф на n вершинах, а F — треугольник. Несложно доказать, что в таком случае ответ на поставленный вопрос n-1. Рассмотренный частный случай нашей задачи можно переформулировать следующим образом. В некотором коллективе n человек, среди которых есть m пар знакомых. Если у кого-то есть пара знакомых, то когда-нибудь они познакомятся и между собой. Каково минимальное m, при котором все пары когда-нибудь познакомятся?
В нашем частном случае задача решается элементарными комбинаторными рассуждениями, но если F — не треугольник, а, скажем, полный граф на 4 вершинах, то задача становится гораздо сложнее, и для ее решения используется линейная алгебра. В курсе мы научимся решать задачу в простейших случаях, а также попробуем поговорить и про линейно–алгебраический метод.
Коновалов Василий (МФТИ) — «Введение в векторное представление слов»
Векторное представление слов это то без чего современная компьютерная лингвистика не может обойтись. Различные чатботы, автоматические переводчики, системы анализа текстов так или иначе работают с векторным представлением слов. На лекции мы рассмотрим векторные способы представления слов, и какими свойствами они должны обладать. Разберем несколько примеров применения векторных представлений слов. Изучим проблемы такого представления и наметим пути их решения.
Купавский Андрей Борисович (ФПМИ МФТИ) — «Учимся считать!»
В этом курсе мы поговорим про двойной подсчёт и усреднение (с использованием вероятности). У этих методов множество применений, и мы обсудим некоторые из числа самых изящных. Примеры будут из области комбинаторики (конечные проективные плоскости), теории графов (графы без циклов длины 4), комбинаторной геометрии (лемма о пересечениях и инциденции между прямыми и точками) и геометрической вероятности (веретено Буффона).
Мусатов Даниил Владимирович (ФПМИ МФТИ) — «Модели делегирования вычислений»
Сейчас всё больше трудоёмких вычислений выполняются не на локальных компьютерах, а на облачных ресурсах. Возникает проблема: как заказчику быть уверенным, что вычисления реально проведены и выполнены верно? Хорошо, когда ответ в задаче можно легко проверить. Например, подстановка решения в исходное уравнение обычно гораздо проще поиска. Но как быть, если задача ещё сложнее?
В курсе мы изучим различные подходы к этой проблеме. Оказывается, можно эксплуатировать тот факт, что вычисления оплачиваются, и вычислять награду так, чтобы стимулировать честную работу. Кроме того, если можно дать работу нескольким исполнителям, то становятся решаемыми ещё более сложные задачи, даже если исполнители могут заранее сговориться.
Полянский Александр Андреевич (ФПМИ МФТИ) — «О неразделимых кругах и шапочках»
Теорема Гудмана и Гудмана (1946) о неразделимых кругах утверждает, что если на плоскости есть набор кругов радиусов r_1, … , r_n таких, что не существует не пересекающей их прямой, которая их разделяет на два непустых множества, то эти круги можно покрыть одним кругом радиуса r_1+ … + r_n. На двух занятиях мы разберём эту теорему, а также её сферический аналог, доказанный недавно докладчиком.
Райгородский Андрей Михайлович (ФПМИ МФТИ, мехмат МГУ) — «Хроматическое число кнезеровского графа и его окрестности»
В курсе будет рассказано об одном из самых замечательных объектов на стыке комбинаторики и теории графов — о так называемом кнезеровском графе. Это граф, у которого вершины — все возможные r-элементные подмножества n-элементного множества, а ребра — пары непересекающихся вершин. В лекциях мы обсудим удивительную историю отыскания хроматического числа кнезеровского графа, изучим топологический метод в комбинаторике и поговорим о некоторых интересных обобщениях первоначальной постановки. Будет и пара катарсисов, и одна нерешенная проблема.
Савватеев Алексей Владимирович (ФПМИ МФТИ) — «Конечные поля»
«Конечная математика» намечает границы применимости повседневной интуиции при работе с математическими абстракциями. Сколько точек на плоскости? Сколько всего многочленов пятой степени? Сколько раз надо сложить единицу с самой собой, чтобы получить ноль? Эти, на первый взгляд абсурдные, вопросы являются прелюдией к материалу нашего миникурса из трёх лекций. Вот — примерная программа всего курса:
- Таблицы сложения и умножения остатков. Многочлены с коэффициентами в остатках. Теорема Безу над любой системой остатков. Парадоксы числа корней.
- Таблицы умножения по простому модулю. Простейшие конечные поля. Основная теорема о корнях многочленов с коэффициентами в поле.
- Поля из p элементов (p — простое). Теоретико-групповые методы: теорема Лагранжа и Малая теорема Ферма. Бином Ньютона, автоморфизм возведения в p-ю степень и второе доказательство теоремы Ферма. Теорема Вильсона.
- Некоторые применения основной теоремы: q-е степени и их количество. Для простых p=qr+1 остаток является q-й степенью тогда и только тогда, когда его r-я степень равна единице. Квадраты по модулю p.
- Критерий квадратичности (-1) (два доказательства). Описание всех простых, являющихся суммой двух квадратов. Кубические вычеты и представимость целых чисел в форме x^2 — xy + y^2. Задача Эрдёша о равных расстояниях, всё о ней.
- Проективная плоскость над конечным полем. Кубические кривые. Сложение точек и группа кривой. Кривая Шарыгина над полем из трёх элементов. Её группа.
- Если останется время, то конечные поля из p^r элементов, мультипликативная группа и структура их вложимости друг в друга. Единственность конечного поля.
Смирнов Евгений Юрьевич (ВШЭ, НМУ) — «Диаграммы Юнга и плоские разбиения»
Сколько есть способов разбить натуральное число в сумму нескольких слагаемых, если суммы, отличающиеся только порядком слагаемых, считаются одинаковыми? Такие разбиения удобно представлять в виде диаграмм Юнга — картинок на клетчатой бумаге. Правда, придумать “замкнутую” формулу для числа диаграмм Юнга с данным числом клеточек, наподобие формулы для биномиального коэффициента, не получается. Зато можно написать производящую функцию — ряд, коэффициентами которого являются интересующие нас числа. Впервые это сделал Эйлер; ему же принадлежит одна из красивейших формул в комбинаторике, знаменитая пентагональная теорема, которая позволяет очень быстро вычислять число разбиений. Этому будет посвящены первые две лекции нашего курса.
В последней лекции мы познакомимся с трехмерными аналогами диаграмм Юнга, которые удобно представлять себе как башни из детских кубиков. Число таких диаграмм можно посчитать с помощью формулы Макмагона, обобщающей формулу Эйлера для обычных диаграмм Юнга. Мы докажем эту формулу, использовав детерминантный трюк Гесселя-Вьенно, который оказывается очень полезен в массе других комбинаторных задач.
Для понимания последней лекции полезно знать, что такое определитель; для первых двух лекций достаточно знаний из “необходимого минимума”
Сорокин Алексей (МФТИ) — «Компьютерная и математическая лингвистика с “Евгения Онегина” до GPT-3»
Я расскажу об истории компьютерной и математической лингвистики в XX и начале XXI века, основных этапах их развития, а также той значительной роли, которую она играет в современном мире. Я постараюсь коснуться не столько и так находящихся на слуху приложений, сколько подробнее рассказать о связи компьютерной лингвистики с другими областями науки (прежде всего с математикой и теоретическим языкознанием), а также вкратце объяснить, почему современные модели столь эффективны, какую роль в них играют нейронные сети, машинное обучение и традиционная лингвистика, а также почему они ещё во многом далеки от идеала. Никаких предварительных знаний не требуется.
Щелчков Дмитрий Владимирович (Google), Сандлер Андрей Дмитриевич (Яндекс) — «Как компьютер играет в игры»
Достаточно ли простого увеличения мощности компьютера в несколько раз, чтобы он начал обыгрывать человека в новых играх? Можно ли взять алгоритм, победивший человека в шахматы в 1997 году, адаптировать этот алгоритм под игру в го, взять в миллиард миллиардов раз более мощный компьютер и наслаждаться его победой в новой, на порядки более сложной игре?
В рамках курса мы ответим на вышепоставленные вопросы, а также рассмотрим более подробно отдельные классы стратегий, такие как переборные стратегии (minimax с alpha-beta отсечениями, MCTS), обучение с подкреплением (генетический алгоритм, deep q-learning). Лекции будут сопровождаться практикой на питоне, где мы подготовим и запустим различные алгоритмы на некоторых играх.
Полученные знания можно будет применить в турнире программ для игры в реверси, который организует Андрей Сандлер.
Ягудин Михаил Ильсурович — «Что на что влияет в мире?»
Тема лекции — причинно-следственная связь, то есть, наше понимание того, что к чему приводит в мире.
Чтобы разобраться в сущности причинности, приходится столкнутся с множеством философских сложностей. Стандартный инструмент для её установления — хорошо задизайненный рандомизируемый контролируемый случайный эксперимент (англ. RTC), — но он не всегда возможен на практике. Например, редко получается форсировать людей принимать решения, которые они не хотят принимать сами.
Я расскажу про идеи Judea Pearl, описанные в его знаменитой книге «Causality». Это замечательный пример превращения философии в компьютерные науки.
Напоследок мы поговорим про методологию науки и разберемся почему на большинство исследований, увы, не стоит обращать внимание. Если останется время, я расскажу как теория причинности используется в недавних работы DeepMind о стимулах агентов.
Golafshan Mehdi (FPMI MIPT) — «Combinatorial Designs»
Обратите внимание, лекция будет на английском языке!