Home » Летние и зимние школы » Летняя школа 2015 » Анонсы курсов и задачи

Анонсы курсов и задачи

Архив задач

 

Алексей Яковлевич Белов (ФИВТ МФТИ, Bar-Ilan University) «Проблема Варинга»

Известно, что любое натуральное число есть сумма четырёх квадратов, девяти кубов, 16 четвёртых степеней натуральных чисел.

Проблема Варинга означает, что для любого k существует такое n(k), что
любое натуральное есть сумма n(k) степеней натуральных (ноль считаем
натуральным числом).

Решение этой проблемы приводит к интересному взгляду на вероятностные
соображения и на тригонометрию.


Вера Буланкина (мехмат МГУ) «О вложениях графов»

Почти каждому школьнику, знакомому с понятием графа, известно определение планарности.
Многие также знают теорему Понтрягина-Куратовского, и некоторые умеют доказывать, например,
что полный граф на пяти вершинах (К5) нельзя нарисовать на листе бумаги без самопересечений.

Достаточно очевидным выглядит в таком случае определение вложимости.
Граф является вложимым (в плоскость), если существует такое его отображение (в плоскость),
что ребра графа не пересекаются нигде, кроме как в общих вершинах, а также не самопересекаются.
Иными словами, для плоскости это та самая планарность.

В данном курсе мы затронем основы топологии и рассмотрим некоторые случаи вложения графов в плоскость и пространство,
а именно: Х-планарность, аппроксимируемость путей на плоскости, вложимость иероглифов в разные поверхности и утолщения графов.
Докажем критерии вокруг этих свойств и объектов, подумаем над алгоритмами их распознавания
(конечно, частично они будут предложены в качестве задач) и увидим, что эти задачи между собой тесно связаны.
Нас ждут собачьи тропинки, бублики с дырками и прочие топологические радости.


Борис Бычков (ВШЭ, 179 школа) «Алгебраические кривые»

Мы начнём с двух хорошо известных фактов школьной геометрии:

1. Любые две окружности на плоскости имеют не более двух точек пересечения;

2. Через любые три точки на плоскости проходит единственная окружность.

Увидим, что на самом деле (на комплексной проективной плоскости) любые две окружности проходят через некоторую фиксированную точку,
а всего имеют 4 точки пересечения (с учётом кратностей).
И вообще, любые две плоские алгебраические кривые степеней m и n пересекаются в mn точках.

Это утверждение называется теоремой Безу, мы обсудим разные интересные следствия из неё, например,
совершенно бесплатно получим доказательство знаменитой теоремы Паскаля.

Затем, обобщая второй факт, докажем, что через любые 5 точек общего положения проходит единственная коника,
а через любые n(n+1)/2 точек общего положения проходит единственная плоская алгебраическая кривая степени n.
От слушателей предполагается знание о том, что такое многочлены и комплексные числа.


Всеволод Воронов (ИДСТУ СО РАН) «Сферические калейдоскопы и однородные многогранники»

Со времен античности и до начала XIX века построения циркулем и линейкой занимали особое место в геометрии.
Верно ли, что они заслуживали столь пристального внимания? Представим себе планету X, на заре цивилизации которой математики,
как и у нас, интересовались построением геометрических фигур и отрезков заданной длины, но считали каноническим другой набор инструментов:
плоские конструкции из стержней единичной длины. Концы стержней соединяются в вершинах;
толщина пренебрежимо мала, так что пересекающиеся стержни свободно перемещаются в плоскости, если конструкция это позволяет.

Будем считать, что отрезок заданной длины можно построить, если нашлась такая жесткая конструкция из стержней,
что искомая длина является расстоянием между некоторыми ее вершинами.
Например, квадратный корень из 3 – это расстояние между вершинами ромба, составленного из двух равносторонних треугольников с единичной стороной.

Какие длины отрезков умели строить древние математики планеты X? Удалось ли им решить все те же задачи,
какие разрешимы в рамках построений циркулем и линейкой?
Быть может, и трисекция угла равностороннего треугольника не являлась для них непреодолимым препятствием?
Объединив усилия, мы попробуем найти ответ.


Александр Воронцов (Яндекс) «Теория узлов»

Теория узлов — одна из «молодых» областей математики, выгодно выделяется среди других низким порогом вхождения:
для того, чтобы понять основные определения и многие классические теоремы достаточно знаний на уровне 7-8 класса школы.
С другой стороны, многие идеи, возникающие естественно в теории узлов находят неожиданно глубокое отражение
в самых разных областях математики и физики. На курсе мы обсудим классические теоремы из теории узлов
и поговорим немного о более экзотических идеях: инвариантах Васильева, виртуальных узлах и других конструкциях.


Константин Вячеславович Воронцов (Яндекс, ФУПМ МФТИ) «Теория и практика машинного обучения»

Человечество научилось собирать данные о процессах в природе, производстве и обществе.
Кто, как и зачем обрабатывает эти данные? Машинное обучение – это наука о том, как по данным отыскивать полезные закономерности,
восстанавливать зависимости, строить прогнозы, принимать решения. В те доли секунды, когда Яндекс обрабатывает ваш запрос,
на вас работают десятки алгоритмов машинного обучения, созданные сотнями математиков и инженеров, запускаемые на тысячях серверов.
Интеллектуальный анализ данных – это профессия будущего, а машинное обучение – одна из основополагающих его дисциплин.
Курс знакомит с некоторыми задачами и простейшими методами машинного обучения.


Алексей Глебов (Институт математики им. С.Л. Соболева СО РАН, НГУ) «Труднорешаемые задачи и приближённые алгоритмы»

Задумывались ли вы когда-нибудь над тем, почему для одних комбинаторных
задач, таких как задача о поиске минимального остовного дерева в графе или
задача о максимальном потоке в сети, разработаны алгоритмы их точного решения,
работающие довольно быстро, в то время как для множества других задач (задача
коммивояжера, задача о рюкзаке и др.) ни одного такого алгоритма не известно?
Нередко встречаются ситуации, когда даже на графе из 20 вершин все
существующие алгоритмы работают недопустимо долго (месяцы или даже годы).

Возникает вопрос: вызвано ли отсутствие быстрых алгоритмов недостаточной
изобретательностью их разработчиков, или существуют какие-то более серьёзные,
фундаментальные причины, по которым построение таких алгоритмов оказывается
невозможным? В нашем курсе мы познакомимся с современным ответом на этот
вопрос, который предлагает теория алгоритмической сложности комбинаторных
задач. Мы определим и проанализируем понятия временной сложности алгоритма,
сложностного статуса задачи, полиномиальной сводимости и полиномиальной
эквивалентности задач, рассмотрим важнейшие классы полиномиально разрешимых,
NP-трудных и NP-полных задач, рассмотрим примеры конкретных задач и алгоритмов
их решения, увидим, каким образом задачи полиномиально сводятся друг к другу,
установим NP-полноту некоторых известных задач.

В завершающей части курса мы поговорим о практических подходах к решению
NP-полных и других труднорешаемых задач. К числу таких подходов относятся
выделение специальных подслучаев задачи, в которых она становится полиномиально
разрешимой, и разработка приближенных, быстро работающих алгоритмов для
решения задач. Особое внимание будет уделено методам построения приближенных
алгоритмов с гарантированными оценками точности для полученного решения. За
основу мы возьмём различные приближённые алгоритмы для задачи коммивояжёра
и её модификации — задачи об m коммивояжёрах, которая состоит в поиске в графе
m непересекающихся гамильтоновых циклов с минимальным или максимальным
суммарным весом рёбер.


Антон Гусев (мехмат МГУ) «Случайные блуждания»

Пусть по бесконечно прямой скачет кузнечик, начиная из начала координат. При этом каждую секунду он с вероятностью 1/2 прыгает на единичку вправо
и с вероятностью 1/2 прыгает на единичку влево. Оказывается, что рано или поздно он вновь окажется в начале координат.
А если говорить корректнее, то вероятность того, что он вернется в начало координат, равна 1.

Теперь пусть кузнечик скачет не по прямой, а по плоскости, также случайным образом выбирая одно из четырех направлений.
Оказывается, что он вновь рано или поздно вернется в точку, из которой начинал.
Парадокс заключается в том, что если мы уйдем в трехмерное пространство,
то там уже кузнечик вернется «домой» (в точку, из которой начал) с вероятностью, строго меньшей 1.

С чем связан такой забавный эффект? На этот вопрос нам и предстоит ответить в ходе данного курса.
Помимо этого, мы разберем и много смежных вопросов.


Николай Зинов (ФИВТ МФТИ) «Cамоналаживающиеся структуры данных»

Обычно структуры данных устроены так, чтобы любая операция на них выполнялась за малое время.
Чтобы гарантировать это, приходится накладывать на структуру дополнительные ограничения,
что усложняет код и требует накладных расходов времени и памяти.

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

Многие структуры данных имеют аналоги, работающие быстро в среднем, которые проще в написании и на практике работают быстрее.
В данном курсе мы познакомимся с методами оценки времени работы операций на таких структурах данных
и опробуем их на простых примерах.
Затем мы рассмотрим более сложный и интересный пример: Левостороннюю кучу и её самоналаживающийся вариант — Косую кучу.

Приветствуется (но не требуется!) понимание устройства обычной Кучи (приоритетной очереди).


Дмитрий Ильинский (ФИВТ МФТИ, 179 школа) «Формула обращения Мёбиуса»

Курс будет посвящен одному из «трюков» в базовой теории чисел — формуле обращения Мёбиуса.
При помощи неё мы посчитаем количество циклических последовательностей, докажем формулу Эйлера.
Кроме того, обсудим мультипликативные функции, передоказательство формулы Эйлера, совершенные числа.
Если останется время, поговорим о доказательстве существования первообразного корня и формулы
включений и исключений при помощи формулы обращения Мёбиуса.


Айнур Максутов (МФТИ, тренер сборных на международной олимпиаде школьников по биологии) «Алгоритмы в биоинформатике»

Биоинформатика — динамически развивающаяся область знаний, благодаря которой биология и медицина выходят на новый уровень.
Исследование структуры ДНК и других биополимеров и открытие генетического кода открыли новые инструменты к исследованию в Life Sciences, что потребовало разработки алгоритмов по обработке больших данных. Благодаря биоинформатике был прочитан и постепенно расшифровывается геном человека, лечатся серьезные заболевания, такие как рак; были обнаружены способы борьбы со многими инфекциями, созданы вакцины, антибиотики, лекарства.

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

Краткий план:

1) введение в молекулярную биологию, генетику и биотехнологии;

2) расстояние между последовательностями, выравнивание;

3) алгоритмы поиска подстроки;

4) алгоритмы поиска с ошибками;

5) чтение и сборка геномов;


Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Неисчерпаемый мир комбинаторных игр»

Многие из вас сталкивались с математическими играми, где двое играют по некоторым хитрым правилам,
а проигрывает тот, кто не может сделать ход. Одной из самых известных подобных игр является игра «Ним».
Джон Конвей, автор игры «Жизнь», вместе со своими учениками и коллегами развил глубокую теорию, описывающую все такие игры.
Оказывается, на играх можно определить арифметические операции, при этом в полученную теорию погрузятся не только обычные (действительные) числа,
но и такие числовые системы, как ординалы, бесконечно малые или нечётко заданные величины.
В мини-курсе мы изучим основы теории, в основном на примере игры «Хакенбуш» («Кусторезка»).


Роман Просанов (ФИВТ МФТИ) «Новые методы в комбинаторной геометрии»

Около 60 лет назад известный математик Пол Эрдёш поставил следующую задачу.
Дано множество из n точек на плоскости. Измерим всевозможные попарные расстояния между ними и посмотрим,
сколько различных чисел у нас получилось. Как мы можем оценить результат?

Практически очевидно, что все расстояния легко могут оказаться различными друг с другом.
Но если мы спросим о том, насколько мало может быть число различных расстояний,
то получим весьма сложную задачу, которая была решена лишь пять лет назад Ларри Гутом и Нецем Кацем.

(На самом деле, они дали не точное решение, а асимптотическое: они доказали, что существует такая константа c,
что любое множество из n точек определяет не меньше c*n / log(n) различных расстояний,
но по сути всех математиков именно существование такой константы и интересовало.)

Для этого им пришлось придумать весьма оригинальный метод, основанный на некотором обобщении известной теоремы о бутерброде:
если у вас есть бутерброд из батона, сыра и колбасы, то можно сделать один плоский разрез ножом так,
чтобы разделить наш бутерброд на половинки, массы батона, сыра и колбасы в которых будут равны.
Метод Гута и Каца оказался удивительно плодотворным, он был моментально подхвачен различными математиками
и успешно применён к множеству других задач комбинаторной геометрии. Обо всём этом мы и поговорим на наших занятиях.


Михаил Пядёркин (мехмат МГУ) «Алгоритмы для анализа комбинаторных игр»

Значительная часть игр, где два игрока ходят по очереди, может быть сформулирована в виде игры на графе с очень простыми правилами.
Изучению таких игр посвящен целый раздел математики; он содержит множество интересных сюжетов, а нас будет интересовать очень простой вопрос:
как по данной игре (или набору игр) эффективно понять, кто является в ней победителем?

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


Андрей Михайлович Райгородский (МФТИ, Яндекс) «Системы общих представителей с геометрическими приложениями»

Многие могут знать (от меня же) задачу про то, как «накалывать сосиски на шампуры, чтобы эти сосиски побыстрее сожрать».
Но это задача на одну лекцию. Оказывается, что у нее есть масса различных приложений в совершенно неожиданных априори областях.
Например, к ней имеет отношение так называемая размерность Вапника–Червоненкиса,
а также с ее помощью решаются задачи в геометрической теории чисел.
О чем-то из этого (если не обо всем) мы точно успеем поговорить.


Алексей Владимирович Савватеев (РЭШ, Яндекс, МФТИ) «Биссекторально-пифагоровы треугольники»

В журнале «Квант» номер 8 за 1983 год в статье «Вокруг биссектрисы» на
странице 36 И. Ф. Шарыгин формулирует такую задачу (входящую также
под номером 500 в его известный задачник):

«Про данный треугольник известно, что треугольник, образованный
основаниями его биссектрис — равнобедренный. Можно ли утверждать,
что и данный треугольник равнобедренный?»

Ответ отрицательный, но в статье далее сказано:

«К сожалению, автор не сумел построить конкретный пример треугольника
(то есть точно указать величины всех его углов или длины сторон) со столь
экзотическим свойством. Может быть, это удастся сделать читателям журнала?»

С тех пор построены три примера (я их перечислю). Последний пример
выводит нас на теорию эллиптических кривых и операцию сложения точек.

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


Андрей Сандлер (ФИВТ МФТИ, Яндекс) «Программирование и анализ игровых алгоритмов»

Три года подряд на этой летней школе проводились курсы «Программирование и анализ игровых алгоритмов»,
в течение которых слушателям предлагалось придумать и реализовать алгоритм для некоторой игры.

В конце школы проводились турниры и выявлялись сильнейшие алгоритмы.

В итоге этой деятельности накопилось внушительное количество логов сыгранных турниров,
которые в этом году предлагается взять в качестве отправной точки для построения более сильных алгоритмов для тех же игр / разумеется, с помощью машинного
обучения 🙂 /

В этом году я планирую несколько расширить лекции и затронуть тему обучения с подкреплением (Reinforcement Learning),
не обойдя вниманием, конечно, и классический материал — Minimax, Alpha-Beta Pruning, Monte-Carlo Tree Search.

Слушателям курса, как всегда, предстоит написать программу, которая будет играть в одну из игр на выбор (Реверси, Война вирусов, Битва питонов),
разрешается использовать любой удобный язык программирования (будьте аккуратны с Java, были случаи,
когда java-код отказывался запускаться в оболочке для проведения турнира).
В этом году задача будет стоять немножко нестандартная — нужно будет выиграть все алгоритмы предыдущих лет (ну, или почти все),
используя большую базу логов сыгранных турниров. Также будет проведён турнир только среди новых алгоритмов / чтобы выяснить, кто же тут всех круче 🙂 /


Евгений Юрьевич Смирнов (НИУ ВШЭ, НМУ) «Паросочетания на графах, непересекающиеся пути и ацтекский бриллиант»

Сколькими способами можно замостить «ацтекский бриллиант», т. е. ромб на клетчатой бумаге, доминошками размера 2х1?
Оказывается, что для ромба со стороной n существует 2^{n(n-1)/2} способов это сделать.

Эту задачу можно решать разными способами; мы обсудим два из них.
Первый основан на подсчете так называемых статистических сумм для паросочетаний на графах (или, как говорят физики, димерных конфигураций).
Второй способ использует такой фундаментальный прием современной алгебраической комбинаторики,
как подсчет числа наборов непересекающихся путей на решетках.
Для этого мы познакомимся с таким важным алгебраическим понятием, как определитель матрицы.

Если останется время, мы посмотрим, какие еще комбинаторные задачи можно решать этими же двумя методами.


Михаил Тихомиров (Яндекс, ФИВТ МФТИ) «Вероятностные алгоритмы»

Рандомизированный, или вероятностный алгоритм — это алгоритм, который помимо входных данных использует генератор случайных чисел.
Опираясь на свойства случайных чисел (независимость, равномерность распределения и т.д.),
для рандомизированных алгоритмов можно получать вероятностные оценки
(т.е. доказывать утверждения вида «алгоритм работает за линейное время в среднем»,
«вероятность ошибки алгоритма не превосходит ε», и т.д.).
Помимо этого, вероятностные алгоритмы зачастую оказываются проще и эффективнее детерминированных
(т.е. не использующих случайность) аналогов. Мы рассмотрим несколько несложных, но красивых примеров таких алгоритмов.
Знание базовых понятий теории вероятностей рекомендуется, но не является обязательным.