Алексей Яковлевич Белов-Канель (ФИВТ МФТИ, Bar-Ilan University), Филипп Рухович (МФТИ) «Внешние бильярды»
Рассмотрим многоугольник M. Из точки A на плоскости проведем касательную (т.е. опорную прямую) к M и отразим относительно точки касания. C новой точкой проделаем ту же процедуру и т.д. Как устроены
периодические, апериодические и вырожденные точки? Возникают разные интересные фрактальные структуры.
Всеволод Воронов (ИДСТУ СО РАН) «Игра в камешки»
На плоскости расположены несколько фигур, соединенных стержнями, причем все соединения шарнирные, а фигуры и стержни имеют пренебрежимо малую толщину и свободно скользят по поверхности. При каком условии данная конструкция будет жесткой? Как проверить, существует ли нетривиальная деформация? Курс посвящен так называемой “игре в камешки” (pebble game), которая дает удивительно простой ответ на эти вопросы. Если позволит время, мы коснемся применений алгоритмов “игры в камешки” в молекулярной биологии и задачи о просачивании жесткости в случайном графе. Для понимания большей части материала не требуется каких-либо предварительных знаний.
Андрей Гейн (УрФУ) «Компьютерная безопасность»
Будущие программисты — этот курс для вас. Скорее всего, однажды вы будете писать часть большого веб-проекта. Оказывается, для этого недостаточно знать язык программирования и алгоритмы. Опыт показывает, что около 80-90 процентов современных самописных сайтов уязвимы и по вине программистов позволяют украсть данные всех пользователей, начиная личными сообщениями и заканчивая паролями. Я расскажу, как так получилось, и почему программистам надо быть аккуратнее.
Первая лекция будет посвящена SQL-инъекциям. Эта уязвимость позволяет украсть информацию из базы данных сайта. Обязательно попрактикуемся (на аконных условиях, конечно)
Вторая лекция будет посвящена аббревиатурам XSS и CSRF, которые тоже являются названиями уязвимостей.
Они сложнее и отличаются от SQL-инъекций тем, что атакуют не сервер, а конкретного пользователя (и крадут, например, доступ к его профилю на сайте).
На лекции покажу примеры, и обязательно попробуем найти такую уязвимость сами.
Олег Герман (мехмат МГУ) «Палиндромы, цепные дроби и двумерная линейная алгебра»
Обычно цепные дроби определяют арифметически и так же доказывают их основные свойства. В курсе мы опишем геометрический подход, который делает многие утверждения про цепные дроби “по-древнегречески” очевидными. Особое внимание мы уделим квадратичным иррациональностям (т.е. иррациональным корням квадратных уравнений с целыми коэффициентами). На эти числа можно посмотреть с точки зрения такой содержательной науки, как линейная алгебра, что мы и сделаем. А почему первое слово в названии курса – “палиндромы”, станет понятно на первой лекции.
Яна Кашинская (ФИВТ МФТИ, Сколтех) «Безопасность данных (Data Security)»
Лекция 1. Безопасность баз данных (Security in Outsourced DB).
Мы живем во время больших данных, почти каждая организация сталкивается с проблемой хранения данных. Покупать и обслуживать оборудование очень дорого, поэтому данные часто хранятся удаленно на серверах гугл, амазон и других. Можем ли мы доверять гуглу и амазону? Как зашрифровать и защитить базу данных, но не потерять возможность удаленного поиска по ней?
Для понимая лекции следует предварительно познакомиться со следующими понятиями: база данных, какой-нибудь один метод шифрования (например, простая перестановка, RSA, …).
Лекция 2. Конфиденциальность данных (Data Privacy)
Многие организация публикуют данные на своих сайтах. Например, на сайте нашей школы вы можете найти списки участников за различные года. Давайте поговорим не о сайте школы, а сайте больницы. С одной стороны, больнице нужно опубликовать данные о больных, чтобы общество знало о заболеваниях и частоте их встречаемости среди различных слоев населения. С другой стороны, по этим данным должно быть сложно вычислить личности пациентов, т.е. должна быть соблюдена конфиденциальность. На лекции мы сформулируем эту задачу формально, обсудим алгоритмы и эвристики её решения.
Для понимая лекции специальных знаний не требуется.
Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Как поделить сундук с сокровищами»
Всем известно, как по-честному поделить шоколадку: один делит на две части, другой выбирает понравившуюся. А что делать, если делящих больше двух? А если нужно поделить две разных шоколадки, а у делящих разные вкусы? Наконец, как договориться о разделе группы неделимых объектов (например, шоколадных яиц с игрушками)? Мы обсудим все эти вопросы с алгоритмической и теоретико-игровой точек зрения: как вычислить нужный раздел и как стимулировать участников честно рассказать о своих вкусах.
Хайдар Нурлигареев (57 школа) «Паркеты и замощения»
Искусство замощения плоскости различными фигурами известно с незапамятных времён;
начавшись, должно быть, когда человек научился использовать камни для строительства домов и
прочих сооружений, оно не угасало ни на мгновение. Со времён средневековья до нашего времени
дошли великолепные арабские и римские мозаики, украшающие культовые сооружения, мостовые
городов всего мира покрыты брусчаткой различных форм и цветов, о кафельной плитке можно и
не говорить. Замощения встречаются и в природе – стоит вспомнить, скажем, о пчелиных сотах
или кристаллах соли, – и в искусстве, – например, в работах голландского художника М.К. Эшера.
Настоящий курс будет посвящён математическому подходу к вопросам, касающимся различных
замощений плоскости многоугольниками. В нём мы разберём некоторые общие законы, которым
подчиняются все «достаточно хорошие» замощения, а также обсудим возможные критерии
классификации замощений. Особое место будет отведено построению различных апериодических
мозаик и изучению некоторых их свойств, а если останется время – затронем и некоторое
количество других смежных с этой темой задач.
Роман Просанов (мехмат МГУ) «Теория множеств»
«Никто не изгонит нас из рая, который основал Кантор» – Д. Гильберт
В 19 веке некоторым математикам стало очень интересно разобраться в том, чем они вообще занимаются, и почему математика работает.
Господствующей стала следующая точка зрения: мы будем строить все математические объекты на базе каких-то совсем элементарных кирпичиков – множеств,
примем за основу некоторые базовые утверждения о них – аксиомы, которые мы считаем интуитивно верными; и правила вывода, в которые мы верим, – некоторые правила,
как из одних верных утверждений строить другие верные. Оставалось только убедиться, что всё в этой схеме работает как надо. (И это было начало очень долгой истории.)
Даже для того, чтобы разобраться в устройстве множеств – наших кирпичиков, пришлось изрядно поработать (некоторым эта работа даже стоила душевного здоровья),
и определённые споры вокруг этой деятельности не утихают до сих пор. На наших занятиях мы попробуем разобраться, как выглядит теория множеств сегодня,
и каким образом на ней покоится здание современной математики.
Если вам интересно узнать, какие бывают размеры у бесконечностей, что такое трансфинитное число, и откуда столько шума вокруг аксиомы выбора, то приходите.
Андрей Михайлович Райгородский (ФИВТ МФТИ, Яндекс) «Дистанционные графы с большим хроматическим числом и без треугольников»
Дистанционный граф – это одно из важнейших понятий комбинаторной геометрии, возникающее в связи с классической задачей о раскраске пространства.
Мы обсудим хроматические числа дистанционных графов, т.е. минимальные количества цветов, в которые можно так покрасить все вершины этих графов,
чтобы вершины, соединенные ребрами, имели разные цвета. Мы покажем, что есть дистанционные графы с очень большими хроматическими числами.
Но это-то для многих не новость. А катарсис будет в том, что, оказывается, бывают даже дистанционные графы без треугольников, у которых по-прежнему огромные хроматические числа!
Алексей Савватеев «Конечные поля»
“Конечная математика” намечает границы применимости повседневной интуиции
при работе с математическими абстракциями. Сколько точек на плоскости? Сколько
всего многочленов пятой степени? Сколько раз надо сложить единицу с самой собой,
чтобы получить ноль? Эти, на первых взгляд абсурдные, вопросы являются прелюдией
к материалу нашего миникурса из трёх лекций. Вот – примерная программа всего курса:
1. Таблицы сложения и умножения остатков. Многочлены с коэфффициентами в
остатках. Теорема Безу над любой системой остатков. Парадоксы числа корней.
2. Таблицы умножения по простому модулю. Простейшие конечные поля.
Основная теорема о корнях многочленов с коэффициентами в поле.
3. Поля из p элементов (p – простое). Теоретико-групповые методы: теорема
Лагранжа и Малая теорема Ферма. Бином Ньютона, автоморфизм возведения в
$p$-ю степень и второе доказательство теоремы Ферма. Теорема Вильсона.
3. Некоторые применения основной теоремы: q-е степени и их количество.
Для простых p=qr+1 остаток является q-й степенью тогда и только тогда,
когда его r-я степень равна единице. Квадраты по модулю p.
4. Критерий квадратичности (-1) (два доказательства). Описание всех простых,
являющихся суммой двух квадратов. Кубические вычеты и представимость целых
чисел в форме x^2 – xy + y^2. Задача Эрдёша о равных расстояниях, всё о ней.
5. Проективная плоскость над конечным полем. Кубические кривые. Сложение
точек и группа кривой. Кривая Шарыгина над полем из трёх элементов. Её группа.
6. Если останется время, то конечные поля из p^r элементов, мультипликативная
группа и структура их вложимости друг в друга. Единственность конечного поля.
Евгений Юрьевич Смирнов (ВШЭ, НМУ) «Диаграммы Юнга и плоские разбиения»
Разобьем натуральное число на слагаемые и запишем эти слагаемые в клетках прямоугольной таблицы так, чтобы они нестрого убывали по строчкам и столбцам.
Полученный объект называется плоским разбиением (plane partition).
Плоские разбиения удобно представлять себе как башни из детских кубиков (трёхмерные диаграммы Юнга):
для этого каждое слагаемое нужно заменить на столбик кубиков соответствующей высоты.
Производящая функция для количества плоских разбиений числа n была вычислена П.Макмагоном в конце XIX в.
Она обобщает знаменитую производящую функцию Эйлера для числа разбиений (т.е. обычных диаграмм Юнга).
Первая часть курса будет посвящена обычным разбиениям и диаграммам Юнга.
Мы выведем эйлеровскую производящую функцию для их числа, обсудим возникающие в связи с ней q-аналоги биномиальных коэффициентов
и докажем пентагональную теорему Эйлера, позволяющую очень быстро вычислять числа разбиений.
Во второй части речь пойдет о трехмерных диаграммах Юнга и формуле Макмагона.
Для доказательства последней мы используем детерминантный трюк Гесселя-Вьенно; о похожих вещах пойдет речь в курсе Миши Ягудина
(тем не менее, наши курсы можно слушать независимо друг от друга).
Михаил Тихомиров (ФИВТ МФТИ) «Потоки в сетях»
Рассмотрим ориентированный граф и представим его как сеть труб, по которым может течь жидкость из истока
(вершины, где жидкость откуда-то появляется) в сток (вершину, где жидкость вытекает куда-то наружу).
Жидкость не может скапливаться в вершинах, и у каждой трубы есть своя пропускная способность — максимальное количество жидкости,
которое может протечь по трубе в единицу времени. Какое максимальное количество жидкости может протечь сквозь заданную сеть труб в единицу времени?
Эта задача носит название задачи о максимальном потоке в сети и занимает важное место в современной теории алгоритмов.
Мы рассмотрим несколько красивых подходов к ее решению и проанализируем их эффективность.
Знакомство с простыми алгоритмами на графах (обход в ширину/глубину) будет полезным, но не требуется для восприятия материала.
Михаил Ягудин (мехмат МГУ) «Детерминанты в перечислительной комбинаторике»
Перечислительная комбинаторика изучает последовательности обычно натуральных чисел, примеры можно посмотреть в энциклопедии OEIS.
Естественное желание — найти замечательную формулу, описывающую числа этой последовательности.
В ряде задач такой замечательной формулой является определитель некоторой матрицы.
Слушатели познакомятся с азами линейной алгебры, мотивирующей понятие определителя.
А в последующем мы научимся перечислять пути на решетках, остовные деревья и перестановки специального типа;
разберём несколько смежных вопросов и применим наши новые знания на практике в неожиданных ситуациях.