Алексей Яковлевич Белов (ФИВТ МФТИ, Bar-Ilan University) «Комбинаторные и геометрические свойства неевклидовой плоскости»
Многие факты школьной геометрии оказываются понятными в неевклидовом контексте. Мы расскажем о том, как естественно строится неевклидова геометрия, как придумывалась модель Кэли-Клейна и какова комбинаторика неевклидовой плоскости.
Предполагается знакомство с понятиями производной, логарифма и экспоненты.
Борис Бычков (ВШЭ, 179 школа) «Инварианты узлов»
Я расскажу, что такое узел, какие у него бывают инварианты и зачем они нужны. Вслед за Райдемайстером, мы узнаем как двигать узлы. Научимся различать левый и правый трилистник и считать некоторые полиномиальные инварианты. Кроме того, познакомимся со знаменитыми инвариантами Васильева. Будем много рисовать и не очень много считать. Для понимания основной части лекций никаких специальных знаний не потребуется.
Всеволод Воронов (ИДСТУ СО РАН) «Клетчатые фигуры, квадратичные формы и class number»
В первой части курса речь пойдет об элементарных доказательствах существования решения диофантовых уравнений 2-й степени, основанных на разрезании клетчатых фигур. Такие доказательства по каким-то причинам не были придуманы в Древней Греции, и первое из них – вернее, геометрическую форму записи другого рассуждения – недавно обнаружил А.В. Спивак.
Далее мы убедимся, что существует связь между геометрией клетчатых фигур и классификацией целых квадратичных форм, т.е. выражений вида ax^2+bxy+cy^2, где a,b,c – целые. Формы назовем эквивалентными, если они принимают одно и то же множество значений. Около 200 лет назад Гаусс придумал алгоритм приведения любой целой квадратичной формы к некому стандартному виду. Оказывается, у этого алгоритма есть наглядное геометрическое представление. Каждому значению дискриминанта d=4ac-b^2 соответствует один или несколько неэквивалентных классов квадратичных форм. Число таких классов n(d) – это и есть одно из определений class number. С этой функцией связан ряд нерешенных задач, предложенных еще Гауссом.
Антон Сергеевич Гусев (мехмат МГУ) «Cops and robbers»
Полицейские и воры – это игра на графе. Пусть есть два игрока, один из которых играет за множество полицейских, а второй за единственного грабителя. Далее происходит пошаговая игра. Сначала каждый коп занимает по вершине графа, а затем то же самое проделывает вор. Далее они по очереди могут перемещаться по ребрам графа: сначала каждый полицейский перемещается в соседнюю по ребру вершину или остается на месте, затем коп, после чего все снова повторяется. Цель проста и понятна – полицейские должны поймать вора, то есть оказаться с ним в одной вершине. Вопрос состоит в том, какое минимальное количество полицейских необходимо, что бы гарантированно поймать вора.
Понятно, что ответ сильно зависит от устройства графа. В рамках курса мы научимся решать данную задачу для некоторых классов графов. Интересен данный курс в первую очередь тем, что для решения задачи нам потребуются нетривиальные комбинаторные рассуждения и углубленное понимание того, как же устроены различные классы графов.
Для освоения курса никаких предварительных знаний не требуется.
Алексей Доледенок (Мехмат МГУ) «Многогранники»
“Наверняка, каждый из вас хоть раз в жизни склеивал из бумаги кубик. Кубик является простейшим примером многогранника, о многогранниках и пойдет речь на наших занятиях.
Чем многогранники отличаются от многоугольников? Как можно задавать многогранники? Почему склеенный кубик сохраняет свою форму? Правда ли, что у любого многогранника есть развертка? Что можно склеить из обычного прямоугольного листочка бумаги? Является ли баян многогранником?
На эти и многие другие вопросы мы научимся отвечать, попутно узнав, что такое теорема Коши о жесткости, теорема Александрова о развертке, теорема Минковского, гипотеза кузнечных мехов. Если останется время, мы поговорим о третьей проблеме Гильберта.”
Максим Евгеньевич Жуковский (ФИВТ МФТИ) «Описательная сложность задачи об изоморфизме»
Пусть H – некоторый граф. Каким образом можно записать графовое свойство “содержать подграф, изоморфный графу H”? Для этих целей подходит так называемый язык первого порядка. На формулах, записанных на этом языке, основаны алгоритмы проверки, обладает ли граф соответствующим свойством. Сложность алгоритма проверки такого свойства это, грубо говоря, и есть описательная сложность свойства (мы будем определять сложность алгоритма монотонно зависящей от описательной сложности функцией). Возникает естественный вопрос: какова описательная сложность свойства “содержать подграф, изоморфный графу H”? Или, иными словами, какова минимальная сложность формальной записи, с помощью которой это свойство может быть выражено? Ответ на этот вопрос таков: сложность равна числу вершин в графе H. Но ситуация меняется, если мы заранее знаем, что граф, для которого мы проверяем наше свойство, является, скажем, связным (ну или обладает еще каким-нибудь естественным свойством). В случае связности ситуация меняется настолько сильно, что в общем случае ответа на вопрос, чему равна описательная сложность, до сих пор нет. Тем не менее для некоторых графов H (например, для цепей и звезд) точный ответ известен, для многих других получены оценки. Об этих результатах и пойдет речь в нашем курсе.
Виктор Кантор (ФИВТ МФТИ, ABBYY) «Машинное обучение и наука о данных»
Всю свою историю человечество ставит перед собой все более амбициозные задачи и сталкивается со все более сложными проблемами. Еще совсем недавно нужно было беспокоиться о том, как не умереть от голода, а уже сегодня, благодаря техническому прогрессу, мы заботимся о том, чтобы успевать просматривать френдленту и побольше смешных картинок в интернете. Хотя, кроме шуток, еще и запускаем корабли в космос, создаем беспилотные автомобили, да и проблемы голода и болезней тоже решаем с привлечением высоких технологий.
Новых вершин нам помогает достигать здравый смысл и автоматизация многих задач, которые совсем недавно решали люди. В начале ХХ века появилось конвеерное производство, в середине – первые промышленные роботы, а конец века и начало следующего связаны с новой вехой – активным и повсеместным внедрением интеллектуальных систем.
Понять смысл текста, распознать речь, найти объекты на снимках со спутника, оптимизировать затраты на производстве, обнаружить места вероятного нахождения полезных ископаемых, спрогнозировать автокатастрофу, проанализировать геном человека – все это и многое другое позволяют в той или иной степени делать методы машинного обучения и анализа данных. Что-то до недавних пор могли делать только люди, а что-то было недоступно и им, ведь многие выводы требуют обработки очень большого объема данных, что не всегда по силам человеку, и уж точно занимает у него больше времени, чем у компьютера. Как же решать такие задачи, что за алгоритмы с ними могут справиться, и какие опасности подстерегают при их применении – обо всем этом мы поговорим на мини-курсе.
Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Скорость работы программ и колмогоровская сложность»
Есть два способа оценки скорости работы программы: в худшем случае и в среднем. Например, “быстрая сортировка” быстра только в среднем, а в худшем случае работает столько же, сколько и сортировка “пузырьком”, а сортировка “кучей” эффективна всегда. Впрочем, средняя скорость зависит от того, какие входы встречаются часто, а какие редко. Ведь если “плохие” входы встречаются гораздо чаще “хороших”, то средняя скорость будет не сильно отличаться от худшей. Оказывается, что существует универсальное распределение входов, при котором сложности в среднем и в худшем случае совпадают для любой программы! Для его построения используется концепция колмогоровской сложности – кратчайшего описания данной строки. В мини-курсе мы познакомимся с этой красивой теорией и построим заявленное универсальное распределение
Роман Просанов (мехмат МГУ) «Пересечения выпуклых множеств»
Многие из вас могут быть знакомы (но если не знакомы, то это не страшно) с известной теоремой Хелли: пусть дано конечной семейство выпуклых тел на плоскости (либо в пространстве) и известно, что любые три из них (четыре в случае трёхмерного пространства) пересекаются в одной точке; тогда всё семейство пересекается в одной точке. Этот достаточно простой результат является первым в большом ряду разнообразных теорем о том, как устроены пересечения семейств выпуклых тел.
На наших занятиях мы попытаемся добраться до следующей задачи, известной как (p,q)-проблема: пусть для семейства выпуклых тел верно, что среди любых p из них, как минимум q пересекаются в одной точке; что тогда можно сказать о минимальном размере множества точек, которое пересекает всё наше семейство? Например, в такой формулировке теорема Хелли на плоскости является частным случаем при p=q=3, она утверждает, что соответствующее множество имеет размер 1, т.е. все тела пересекаются в одной точке. Общая (p, q)-задача, однако, является достаточно сложной, и для подготовки к ней нам потребуется много интересных промежуточных результатов, которые будут весьма красивы и сами по себе.
Андрей Михайлович Райгородский (МФТИ, Яндекс) «Случайные подграфы кнезеровских графов»
В этом году я предложил 6ую задачу в вариант 9ого класса Московской Математической Олимпиады.
Эта задача связана с оценкой числа ребер у графа с заданными числом вершин и числом независимости. В курсе я расскажу об этой задаче и о ее связи с удивительными свойствами случайных подграфов Кнезеровских графов.
Алексей Владимирович Савватеев «Простые числа в арифметических прогрессиях»
Более 100 лет назад Дирихле доказал следующую теорему:
“В любой арифметической прогрессии со взаимно-простыми начальным членом и разностью содержится бесконечное количество простых чисел.” Мы докажем кустарными методами бесконечность числа простых вида(4k+1) и (4k+3), а затем на этом примере познакомимся с методом Дирихле.
Слушатели узнают, что такое ряд Дирихле, гипотеза Римана, бесконечное произведение и характер Дирихле. Будет дан набросок доказательства общей теоремы, а также краткое введение в комплексный анализ.
Андрей Сандлер (ФИВТ МФТИ, Яндекс) «(Не очень) глубокое машинное обучение в играх»
В течение последнего года машинное обучение преодолело один важный барьер – человек, и не просто человек, а второй лучший в мире игрок в Го, Ли Седоль, побеждён в матче со счётом 4-1 в пользу программы. Сделано это было, разумеется, усилиями большой команды людей и огромного кластера машин.
На данном курсе мы не будем этого повторять, но попробуем понять, за счёт чего был совершён такой качественный скачок в возможностях глубокого обучения нейронных сетей. Если у нас останется время, я расскажу и о классических подходах к написанию игровых программ (alpha-beta pruning, Monte-Carlo Tree Search), хотя, возможно, части слушателей это покажется уже знакомым.
Традиционно, в течение школы будет проведён турнир программ по некоторой игре. В этом году это модифицированный морской бой. Главное отличие от обычного морского боя будет в том, что живые корабли можно перемещать, а выстрелы можно производить только с палубы своего корабля, сообщая сопернику, где она находится. Такое простое правило делает эту игру куда более зрелищной и захватывающей! Подробнее читайте тут. Участвовать приглашаются все желающие, даже те, кто на курс ходить не собирается. Писать программы можно на C/C++, Ruby, Pascal, Python2/3. Технические правила игры будут доступны на проверяющем сервере. Логин и пароль от проверяющей системы можно будет получить у Андрея Сандлера сразу после открытия школы, http-адрес сервера будет висеть на всех досках объявлений.
Если кто-нибудь пожелает программировать на языке, отличном от предложенных, просьба сообщить об этом по адресу andrei.sandler@phystech.edu, чтобы я добавил компилятор или интерпретатор этого языка в систему.
Данила Черкашин (ФИВТ МФТИ) «Введение в топологическую динамику»
Нас интересуют метрическое компактное пространство X и непрерывное отображение T из X в X (такая пара называется динамической системой с дискретным временем). Мы обсудим топологические свойства динамических систем, такие как плотность периодических точек (и почти периодических точек) и топологическую энтропию. Еще мы поговорим об их связи с комбинаторикой и, если останется время, с диофантовыми приближениями.
Крайне желательно знать базовые определения топологии (открытые/замкнутые множества, ком- пактность); других специальных знаний не требуется.
Михаил Ягудин (мехмат МГУ) «Случайные остовные деревья»
У каждого связного графа есть остовные деревья, подграфы без циклов, включающие все вершины; выбрав случайное из них, получим случайное основное дерево.
Первые работы по случайным остовным деревьям принадлежат ещё Кирхгофу. В 1847 он обнаружил потрясающую связь с электрическими цепями. А многие важные и красивые результаты были получены в девяностые годы прошлого века и в начале двухтысячных.
Сперва мы разберёмся с конечными графами: выведем формулу Кирхгофа и научимся генерировать случайные поддеревья удивительно красивым алгоритмом. В завершении курса я пролью свет на бесконечные графы, проиллюстрировав основные идеи на квадратной решётке.