Алексей Яковлевич Белов (ФИВТ МФТИ) «Проблема Варинга»
Известно, что любое натуральное число есть сумма четырёх квадратов, девяти кубов, 16 четвёртых степеней натуральных чисел.
Проблема Варинга означает, что для любого k существует такое n(k), что любое натуральное есть сумма n(k) степеней натуральных (ноль считаем натуральным числом)
Решение этой проблемы приводит к интересному взгляду на вероятностные соображения и на тригонометрию.
Илья Игоревич Богданов (МФТИ) «Как нарисовать клубок?»
Клубком называется граф, изображённый на плоскости, если любые два его ребра имеют ровно одну общую точку (при некоторых дополнительных естественных ограничениях). Конвей предположил, что в клубке всегда число рёбер не больше числа вершин. Несмотря на простоту вопроса, эта гипотеза остаётся открытой (при том, что в предположении гипотезы все графы, которые можно нарисовать в виде клубка, известны). Мы обсудим эту гипотезу и близкие вопросы.
Александр Игоревич Буфетов (МИАН, ИППИ РАН), Константин Тогой (СПбГУ) «Энтропия»
Хорошо известно число способов разместить k шаров по N коробочкам, а также то, что при фиксированном N больше всего способов – при k = N/2.
А сколько будет способов, если k меняется, и, например, k > 2/3 N?
Иными словами, какова вероятность при игре в орлянку, что 1-й игрок выиграет в 2/3 игр? А если монета не симметричная?
Начав с этих простых комбинаторных вопросов, мы обсудим потом понятие энтропии – понятие, которое в теорию информации ввел Клод Шэннон, а в теорию динамических систем – Андрей Николаевич Колмогоров.
Олег Герман (мехмат МГУ) «Геометрия чисел и диофантовы приближения»
Многие задачи, связанные с целыми числами, допускают геометрические формулировки, использующие понятие решетки. Такой подход позволяет по-новому взглянуть на эти задачи и порой дать неожиданно красивое решение. Изучению этого подхода и будет посвящен наш курс.
Виталий Гольдштейн (Google, ФИВТ МФТИ) «Обходы графов»
На лекциях будут рассмотрены два обхода графа: в ширину и глубину.
Несмотря на всю кажущуюся простоту этих алгоритмов? они имеют множество интересных применений. Даже если вы уже слышали подобные лекции, вы почти наверняка услышите что-то новое.
Однако начинающим тоже будет многое понятно, так как тема достаточно простая.
Мы рассмотрим различные свойства конструируемых алгоритмом деревьев, порядка обхода вершин и ребер и многое другое.
Также немного изучим, как данные алгоритмы используются в некоторых алгоритмах нахождения потоков в сетях.
Антон Гусев (мехмат МГУ) «Произведения последовательных натуральных чисел»
Вопрос, на который нам с вами хотелось бы получить ответ, на первый взгляд звучит очень просто: «Может ли произведение нескольких последовательных чисел быть степенью простого числа?»
Но, как часто бывает в математике, даже на самые простые вопросы не всегда легко получить ответ.
Данная проблема была поставлена известным венгерским математиком Полом Эрдешем.
Примечательна это задача тем, что она находится на стыке сразу нескольких дисциплин, полезных любому олимпиаднику.
Так, мы успеем применить знания из теории чисел, многочленов и неравенств.
Дмитрий Ильинский (ФИВТ МФТИ, 179 школа) «Некоторое задачи теории графов»
В этом курсе мы рассмотрим различные задачи из теории графов и их приложения. Темы занятий:
1. Обходы графов по ребрам и вершинам.
Мы обсудим, когда граф можно обойти, пройдя по всем ребрам, или пройдя по всем вершинам, а также различные приложения этой задачи: когда граф можно разбить на несколько непересекающихся путей, можно ли выписать последовательность из 0 и 1 так чтобы все подпоследовательности длины k встречались ровно по одному разу.
2. Планарные графы.
Графы, которые можно нарисовать на плоскости так, чтобы вершины были точками, а ребра – непересекающимися кривыми называются планарными. Мы найдем необходимое условие планарности, докажем непланарность некоторых графов, изучим вопрос раскраски вершин графа, если останется время, поговорим о рисовании графа на сфере и правильных многогранниках.
3. Различные варианты теоремы о паросочетаниях.
Паросочетание в графе – это набор ребер, никакие два из которых не имеют общей вершины. Мы обсудим следующую задачу:
Есть n юношей и n девушек, юношам нравятся некоторые девушки. В каком случае их можно разбить на пары так, чтобы каждый юноша был с девушкой, которая ему нравится?
и различные варианты и модификации её.
Виктор Кантор (ФИВТ МФТИ, ABBYY) «Знакомство с машинным обучением»
Как научить компьютер узнавать лица людей, распознавать речь, понимать, что изображено на картинке или определять тему текста? Ответы на подобные вопросы дает машинное обучение.
Мини-курс будет состоять из двух лекций. На первой будет увлекательное введение в практические задачи, основные понятия и несколько простых, но вполне используемых на практике алгоритмов. Вторая лекция порадует любителей теории, – сначала будет небольшое введение в теорию вероятностей, а затем рассказ о вероятностных методах машинного обучения.
Для сдачи зачета по курсу будет предложено семь задач (три теоретические и четыре практические), из которых достаточно решить любые три.
Яна Кашинская (ФИВТ МФТИ) «Я знаю, что он не знает, что она не знает, что…»
Курс будет состоять из двух частей.
1. Казино
Правила просты. У игрока в каждый момент игры есть некоторый капитал. В начале хода разрешается поставить некоторую сумму на черный цвет или на красный. Затем крутится барабан, на котором выпадает один из этих двух цветов. Если игрок угадал цвет, то ему возвращается ставка в удвоенном размере.
Допустим, крупье — ваш друг. Он вам рассказал, некоторую инсайдерскую информацию. Мы строго опишем понятие стратегии в этой игре, увидим, как нужно играть, чтобы использовать информацию.
2. Владение информацией
Безопасно говорить вслух «Я не знаю, какая у тебя карта»? Нет, теперь ваш соперник владеет информацией, что вы не владеете информацией. Мы разберём несколько игр, когда обмен информацией о незнании приводит ко всеобщему знанию.
Никаких специальных знаний для понимания курса не требуется, он будет понятен всем участникам школы.
Курс можно будет сдавать двумя способами: «программистский» – написать программу, «математический» – решить задачки.
Яна Кашинская (ФИВТ МФТИ) «Хеши»
Какие у вас возникают ассоциации, когда вы слышите слово «хеш»? Скорее всего, таблицы, списки, многочлены…
Я хочу пополнить ваш список словом «случайный граф».
Моя лекция будет посвящена обсуждению алгоритма быстрой проверки принадлежности элемента множеству.
Мы научимся за линейное время по множеству строить случайный граф, после чего отвечать на вопросы о принадлежности множеству за константное число операций.
Чтобы реализовать алгоритм с лекции, нужно быть знакомым с понятием поиск в глубину (dfs), уметь хранить граф в памяти компьютера более оптимально, чем матрицей смежности. Но для того, чтобы понять алгоритм, такой опыт не нужен.
Если останется время, то в конце лекции будут рассказаны пара алгоритмов, не связанных с хешами, красивых, но почему-то мало известных.
Виталий Анатольевич Кошелев (ФИВТ МФТИ, Яндекс) «Задача Эрдеша-Секереша о выпуклых многоугольниках на плоскости»
Сколько точек на плоскости будет достаточно, чтобы среди них всегда можно было найти выпуклый многоугольник на заданном числе вершин?
Этот вопрос был впервые поставлен 75 лет назад группой знаменитых венгерских математиков (и с этим связана отдельная красивая история).
Простота постановки задачи привлекала очень большое количество исследователей, но тем не менее, до конца задача не решена до сих пор.
Но за прошедшее время появилось очень много обобщений и близких задач.
Я расскажу о текущих достижениях и, в том числе, о совсем новых результатах.
Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Вероятностно проверяемые доказательства»
Обычное математическое доказательство требуется прочесть целиком, чтобы убедиться, что в нём нет ошибки.
Даже один неверный переход может всё разрушить. Оказывается, можно перевести любое доказательство на другой язык, при котором для проверки нужно прочесть совсем немного символов, выбранных случайно. При этом верное доказательство точно будет одобрено, а неверное — с высокой вероятностью забраковано.
Удивительно, что эта область тесно связана с приближённым решением сложных вычислительных задач.
Примером такой задачи может служить задача коммивояжёра: нахождение кратчайшего цикла, проходящего через все вершины во взвешенном графе.
Для приближённого решения нужно найти цикл, который не длиннее 110% от кратчайшего.
В мини-курсе мы изучим, как формально мерить трудоёмкость вычислительных задач, определим один из классов сложных задач — NP-полные, и свяжем их приближённое решение с вероятностно проверяемыми доказательствами.
Александр Полянский (ФИВТ МФТИ) «Графы диаметров»
Этот курс посвящен одной удивительно интересной теме — графам диаметров.
Представьте себе, что на плоскости (или в пространстве) дан такой конечный набор точек, что максимальное расстояние между ними равно 1.
Если расстояние между двумя точками равно 1, соединим их ребром. В результате получится граф, который принято называть графом диаметров.
Мы начнем наши исследования с очень простых и элементарных вопросов. А именно с задачи: доказать,
что в графе диаметров на плоскости не более n ребер (если граф построен на n вершинах).
Кстати, обязательно попробуйте сделать эту задачу. Она решабельная!
После этого мы обсудим то, как утроены графы диаметров в (нашем трёхмерном) пространстве.
Здесь речь коснется изящной теоремы Дольникова (о том, что два цикла нечетной длины имеют общую вершину).
При возможности будет предложено несколько доказательств.
В конце курса мы поговорим о совсем новых результатах в этой области!
Для тех, кто заинтересуется, будут предложены несколько открытых задач, часть из которых, вероятно, имеют элементарное решение.
Андрей Михайлович Райгородский (ФИВТ МФТИ, МГУ) «Теория Рамсея»
Теория Рамсея — это наука о том, что в большой структуре не может быть полного хаоса. Я расскажу о тех аспектах этой теории, которые связаны с графами.
Иван Решетников (ФИВТ МФТИ) «Задачи по геометрии»
В рамках данного курса будут предложены задачи олимпиадного толка по геометрии. Планируется два занятия.
На первом занятии мы познакомимся с таким геометрическим объектом, как поляра точки относительно окружности.
Используя некоторые знания про поляры, можно решить задачу о построении касательной из точки к окружности с помощью одной линейки.
На втором занятии будут предложены олимпиадные задачи по комбинаторной геометрии.
Алексей Владимирович Савватеев (МФТИ, РЭШ) «Доказательная геометрия»
На рубеже XVIII-XIX веков произошла «первая математическая революция» (вторая происходит на рубеже XX-XXI веков на наших с вами глазах). А именно, был решен целый ряд задач, стоявших с античных времён. Среди них: как найти общую формулу для корней уравнения пятой (и более высокой) степени; как построить с помощью циркуля и линейки куб, вдвое бОльший данного; как разделить данный угол на три равные части; и некоторые другие проблемы.
Общей характерной чертой полученных решений было то, что они содержали доказательства невозможности требуемого в задачах. На этом пути произошло становление науки, которую я бы назвал «доказательной геометрией». Речь идёт о сведении геометрических формулировок к задачам из области чистой алгебры, и затем, после наращивания «военной техники», прихода к противоречию с логикой изучаемых алгебраических конструкций.
Я докажу наиболее простые теоремы доказательной геометрии, относящиеся к построениям циркулем и линейкой. С этой целью я познакомлю слушателей с базовыми понятиями теории расширений полей и теории алгебраических чисел. Никаких предварительных знаний ни в какой области математики не требуется!
Илья Шкредов (ИППИ РАН, Математический институт им. Стеклова) «Введение в теорию динамических систем»
Неформально динамическую систему можно представлять себе как пару, состоящую их множества и некоторого закона, который каждой точке множества X сопоставляет другую точку – ее образ. Теория динамических систем – это наука, изучающая поведение точек при воздействии тех или иных законов. Например, пусть X – это отрезок [0,1], а закон состоит в том, что точке x из отрезка X сопоставляется точка 2x, если x<1/2, и 2x-1, если x>1/2. Что тогда можно сказать о поведении точек при таком отображении? К примеру, правда ли, что при таком отображении образы любой точки попадают в произвольный подотрезок отрезка [0,1]?
В курсе мы ответим на этот и другие подобные вопросы и разберем примеры простейших динамических систем на отрезке, на окружности и на плоскости: сдвиг Бернулли, поворот окружности, биллиарды в областях и т.д.