Анонсы курсов

Архив задач

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

Число называется трансцендентным, если оно не является корнем многочлена с целыми коэффициентами.
Курс посвящен построению трансцендентных чисел. Предполагается доказать трансцендентность чисел e и π.


Борис Бычков (матфак ВШЭ, 179 школа) «Коники и элементарная геометрия»

Ни для кого не секрет, что параболой называют график функции x2y = 0,
а гиперболой – график функции xy – 1 = 0.
На занятиях я расскажу, почему их, вместе с эллипсом, называют кониками, и о некоторых их замечательных свойствах;
в каком смысле коники эквивалентны друг другу и какими ещё свойствами обладают проективные преобразования.
Будут доказаны теоремы Паскаля, Брианшона и других известных ученых древности.
В конце обсудим несколько задач о кониках, описанных около треугольника,
а если останется время, изучим ещё одно интересное преобразование плоскости – изогональное сопряжение.
От слушателей предполагается знание о том, что такое высота треугольника
и почему биссектрисы треугольника пересекаются в одной точке.


Александр Воронцов (ИПМ им. М.В. Келдыша РАН, школа «Интеллектуал», Яндекс) «Комбинаторная теория игр»

Задачи

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


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

Лекция 1: Современные задачи анализа данных и машинного обучения. Математическая постановка задачи.
Обучение и тестирование. Обучение и переобучение. Метод ближайших соседей. Отбор признаков. Примеры и упражнения.
Лекция 2: Нейрон и линейный классификатор. Соревнования по анализу данных. Задача медицинской диагностики. Конкурсное задание.


Виталий Гольдштейн (Google, ФИВТ МФТИ) «Как протестировать свою программу»

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


Антон Гусев (мехмат МГУ) «Уравнения Пелля»

Уравнения Пелля – это уравнения вида x2my2 = 1,
где m – натуральное число, не являющееся точным квадратом.
Они представляют собой класс диофантовых уравнений второй степени и связаны со многими важными задачами теории чисел.
Решение уравнений Пелля – задача непростая, хотя и выполнимая методами элементарной математики.
Полное описание решений этих уравнений и является нашей конечной целью.
Попутно нам встретятся некоторые математические понятия и теоремы, которые на первый взгляд
могут показаться не связанными с основной темой. Большинство из них представляет интерес
не только как инструмент для исследований уравнений Пелля, но и сами по себе.


Глеб Геннадьевич Гусев (Яндекс, ФИВТ МФТИ) «Вырожденные системы уравнений, дискриминант и эйлерова характеристика»

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


Дмитрий Ильинский (ФИВТ МФТИ, 179 школа) «Системы вычетов и первообразные корни»

Курс будет посвящен базовому понятию из теории чисел – системам вычетов и различным его применениям.
Мы изучим первообразные корни и индексы, введем дискретный логарифм на системах вычетов
и обсудим его применение в теории кодирования. Если останется время, то поговорим немного
о конечных полях и кодах БЧХ для них. Таким образом, курс в основном посвящен теории чисел
с добавками из алгебры и теории кодирования.

Предварительных знаний не требуется.


Виктор Кантор (ФИВТ МФТИ, ABBYY) «Машинное обучение в действии»

Задачи

На нашем курсе мы будем заниматься спасением мира и настоящей магией. Да да, я не шучу.
Машинное обучение – это наука, которая лежит в основе решения широкого спектра задач прогнозирования, распознавания, интеллектуального анализа текстов, изображений, видео и других сложных (часто неструктурированных) данных самой разнообразной природы.
С помощью машинного обучения сегодня:
• Поисковики показывают сайты, наиболее релевантные поисковому запросу
• Сети магазинов прогнозируют спрос на товары
• Мобильные операторы оценивают готовность клиентов перейти к другому оператору (чтобы вовремя предложить интересные акции или услуги и оставить клиента у себя)
• Банки предсказывают, вернет человек кредит в срок или нет
• Рекламщики выясняют, какую рекламу показать человеку, чтобы она его на самом деле заинтересовала, а не вызывала только раздражение.
• Интернет-магазины рекомендуют товары, которые могут быть нужны пользователю
• Задачи диагностики заболеваний решаются намного точнее, чем раньше
• Создаются системы компьютерного зрения, распознавания и синтеза речи, понимания смысла текста
Что-то из этого выглядит как возможность «заглянуть в будущее» и заранее понять, как будет развиваться некий процесс. Что-то – как возможность наделить компьютер пониманием того, что доступно сейчас только человеку, вдохнуть в компьютер жизнь. Это ли не настоящая магия?
На курсе вас сначала ждет небольшое введение в язык Python, а затем мы с вами поучимся решать практические задачи, в частности, задачу медицинской диагностики (я же обещал вам спасение мира?).
Примечание: крайне рекомендуется посещать курс вместе с курсом К. В. Воронцова «Введение в теорию и практику обучения машин».


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


Ярослав Кищенко (Яндекс, ФИВТ МФТИ) «Параллельное программирование с помощью openMP»

В данном курсе вы узнаете, как быстро распараллелить свою программу,
указав, например, перед циклом директиву типа “#pragma omp parallel for”.
Так же в курсе будет рассмотрена архитектура компьютера, и особенно – способы,
позволяющие параллельно исполняться коду на уровне “железа”;
такие элементы операционной системы, как процесс и поток; и базовые конструкции openMP.
Для сдачи курса, помимо задач по openMP, будет предложено разработать собственный алгоритм для некоторой задачи и распараллелить его.
Требования: не бояться прогать на C.


Виталий Кошелев (Яндекс) «Теория Рамсея и вычисления»

Теория Рамсея – это, говоря не совсем формально, наука о том, что в очень больших и сложных структурах
непременно есть достаточно регулярные подструктуры. В течение XX века выделилась целая совокупность дисциплин,
каждую из которых естественно отнести к теории Рамсея. Так, в теории чисел наиболее глубоко изученной рамсеевской проблемой
является задача об отыскании длинных арифметических прогрессий в плотных подмножествах натурального ряда.
В теории графов и гиперграфов речь идет о так называемых числах Рамсея.
Наконец, в геометрии рамсеевская проблематика сконцентрирована около задач Нельсона–Эрдеша–Хадвигера
о раскрасках метрических пространств и задач типа Эрдеша–Секереша.
Мы поговорим об этих задачах, а также затронем вопросы вычисления их точных значений.


Даниил Мусатов (ФИВТ МФТИ, Яндекс) «Парадоксы самореференции и их разрешение»

В некотором полку был брадобрей. Командир приказал ему брить всех, кто не бреется сам.
Должен ли брадобрей брить сам себя? Если задуматься, то в любом случае брадобрей нарушит приказ.
Почему так получилось? Из-за самореференции: утверждение «брадобрей должен брить сам себя»
зависит от собственной истинности. На первой лекции мы изучим различные парадоксы, связанные с самореференцией,
а на второй поговорим о том, как их разрешать и какое влияние они оказали на современную математику.
Никаких предварительных специальных знаний не требуется.


Хайдар Нурлигареев (57 школа) «Паркеты и замощения»

Искусство замощения плоскости различными фигурами известно с незапамятных времён;
начавшись, должно быть, когда человек научился использовать камни для строительства домов и прочих сооружений,
оно не угасало ни на мгновение. Со времён средневековья до нашего времени дошли великолепные арабские и римские мозаики,
украшающие культовые сооружения, мостовые городов всего мира покрыты брусчаткой различных форм и цветов,
о кафельной плитке можно и не говорить. Замощения встречаются и в природе – стоит вспомнить, скажем, о пчелиных сотах или кристаллах соли, –
и в искусстве, – например, в работах датского художника М. К. Эшера.

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

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


Александр Полянский (ФИВТ МФТИ) «Немного о том, что знали о многогранниках ещё в 19 веке»

На занятиях мы докажем три теоремы о многогранниках (третья будет рассказана, если останется время).

1. Теорема Коши. Эта теорема почти что стала олимпиадным фольклором. Она гласит:
Два выпуклых многогранника с соответственно равными и одинаково расположенными гранями обладают равными углами между соответствующими гранями.

2. Теорема Штейница. Это теорема об условиях на планарный граф,
при которых будет существовать многогранник, комбинаторно эквивалентный ему
(это понятие мы определим на занятии; например, куб и произвольный параллелепипед комбинаторно эквивалентны).

3. Теорема Минковского. Эту теорему мы будем разбирать, только если нам будет хватать времени. Она гласит:
Если каждой грани одного выпуклого многогранника, соответствует равновеликая ей грань другого выпуклого многогранника
с параллельной внешней нормалью и обратно (т.е. справедливо тоже самое условие для второго многогранника), то два таких многогранника равны.

Требуется: знание формулы Эйлера для планарных графов; интуитивное понимание того,
что есть многогранник (формально мы определим это на занятии);
воображение для работы с трехмерными объектами;
простые знания по комбинаторике и хорошее настроение.
До встречи!


Роман Просанов (мехмат МГУ) «Избранные задачи комбинаторной геометрии»

Курс будет посвящён обзору отдельных известных и важных проблем комбинаторной геометрии. Моей целью будет дать слушателю некоторое общее представление о специфике вопросов, относящихся к этой безусловно красивой области математики. Будут затронуты:
– задача освещения выпуклого тела;
– некоторые вопросы, связанные с плотными упаковками конечного числа тел и числом Хадвигера;
– задача Тарского о планках (покрытие тела полосами);
– задача Эрдёша-Кли о максимальном размере множества точек без тупых углов.
Предполагается в основном работать с объектами в n-мерном пространстве, но этого не следует бояться. Собственно говоря, курс можно рассматривать, как ознакомительный экскурс в многомерную геометрию. Разумеется, всё будет иллюстрироваться примерами на плоскости и в пространстве. Особенных предварительных знаний не требуется.


Андрей Михайлович Райгородский (Яндекс, МФТИ, МГУ) «Дистанционные графы и их случайные подграфы»

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


Михаил Абрамович Ройтберг (ИМПБ РАН, ФИВТ МФТИ) «Разностные уравнения и траектории»

Разностные уравнения (иначе – линейные рекуррентные уравнения) k-го порядка – это уравнения вида
Xn = a1 × Xn-1 + …
+ ak × Xn-k + g(n).
Если g(n) = 0 для всех n, то уравнение называется однородным.
Пример разностного уравнения 2-го порядка – уравнение Фибоначчи
Xn = Xn-1 + Xn-2.
Решение разностного уравнения – бесконечная последовательность {Xn}.
Разностные уравнения (наряду с дифференциальными уравнениями) используются для описания различных процессов;
на их примере можно понять многие свойства дифференциальных уравнений.

Примеры вопросов, которые будут разобраны;
• Какова общая формула решений разностного уравнения?
• Какая есть связь между разностными уравнениями и векторными пространствами?
• Какие траектории могут задавать системы разностных уравнений?

Примеры задач:
1) Вычислить с точностью до 5-го знака после запятой X100,
где {Xn} – решение уравнения Xn = Xn = 0,5 Xn-1 + 0,5 Xn-2.
2) Описать общий вид решений уравнений вида
Xn = a Xn-1 + b Xn-2 + c.


Алексей Владимирович Савватеев (РЭШ) «Арифметика и геометрия кубических кривых»

В этом году на моих лекциях настанет кульминация всего того, что мы изучали последние три года на Школах.
А именно, мы займёмся кривыми третьего порядка – групповым законом на них, топологическим устройством кривых,
арифметикой рациональных и целых решений.
Разберём красивейшее геометрическое решение уравнения Ферма x3+y3=z3,
решим ещё одно знаменитое уравнение y2=x3 ± 1.
Фактически миникурс откроет слушателям дверь к пониманию центра современной математики –
доказательства Великой теоремы Ферма. Разумеется, путь к ней будет ещё далёк (я и сам пока не разобрался в доказательстве!),
но это будет первый шаг. Предварительных знаний для понимания курса не потребуется, приходите все!


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

В течение курса слушателям предлагается придумать и реализовать на любом удобном языке программирования алгоритм для игры «Реверси»
(http://ru.wikipedia.org/wiki/Реверси).
Технические правила игры и формат обмена ходами будут изложены ниже, но по сути от классического Реверси 8×8 игра отличаться не будет.
По итогам занятий планируется провести турнир, в котором сразятся все алгоритмы, прошедшие проверку (надеюсь, что будут и призы 🙂 ).
Так как турнир подразумевает соревнование, то на занятиях планируется не разбирать какую-либо конкретную стратегию,
а освещать общие вопросы теории алгоритмов, например, поиск в ширину или Alpha-Beta pruning, которые могут пригодиться при написании кода игры.
Также, если останется время и желание, я расскажу про применение метода Монте-Карло в обходе дерева игры.
Писать код можно на C/C++, Ruby, Pascal, Python2/3. Заготовка на Ruby лежит здесь,
технические правила изложены тут.
Если кто-нибудь пожелает программировать на языке, отличном от предложенных,
просьба сообщить об этом по адресу andrei.sandler@phystech.edu,
чтобы я добавил компилятор или интерпретатор этого языка в систему.
Будет хорошо, если в школу вы приедете уже с некоторой работающей версией игры (можно посылать их мне на почту для проверки).


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


Игорь Шнурников (НИУ ВШЭ) «Триангуляции Делоне»

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


Тимофей Ющенко «Компьютерная безопасность»

Компьютерная безопасность – это весьма обширная тема, которая
затрагивает множество областей, начиная с безопасности веб-сайтов и
заканчивая шифрованием информации и стеганографией. Практически
невозможно изучить все направления за одну смену лагеря, поэтому все
лекции планируются быть обзорными и, все, кого эта тема заинтересует,
смогут в частном порядке задавать любые вопросы. В планах на лекции –
разобрать основные методы атак на web-сервисы, поговорить о
криптографии и стеганографии, обсудить
основные принципы работы Unix-системы и просто повысить уровень
компьютерной грамотности.