Алексей Яковлевич Белов (ФИВТ МФТИ, МИОО) «Неразрешимости»
Почему уравнение 5-й степени неразрешимо в радикалах? Почему правильный 17-угольник строится, а 19-угольник – нет? Почему трансцендентное уравнение tg(x)-x = c неразрешимо в элементарных функциях? Почему функция, переводящая некоторую область в круг, не выражается в квадратурах? За всеми этими задачами стоит одна и та же идея, с которой началась современная алгебра.
Виталий Волк (Яндекс) «Введение в поисковые системы»
Мы поговорим об архитектуре интернет-поисковиков, о том, как придать точный смысл выражению “одна система ищет лучше другой” и о том, какие нетривиальные задачи возникают при их разработке. Курс будет довольно простой, но с элементами интерактивного веселья; желающие смогут что-нибудь написать (код) или, наоборот, прочитать (какую-нибудь серьезную статью).
Всеволод Воронов (ИДСТУ СО РАН) «Сферические калейдоскопы и однородные многогранники»
Нестрогая формулировка той задачи, которая будет нас интересовать, выглядит так: cколько различных многогранников можно склеить из правильных многоугольников с единичной стороной при условии, что все вершины получившегося тела должны быть симметричны друг другу? Конечно, в списке присутствуют 5 платоновых тел, у которых все грани одинаковы, и 4 звездчатых правильных многогранника, а также 13 архимедовых тел, грани которых могут быть 2-3 типов. Из последних лучше всего нам знаком усеченный икосаэдр (футбольный мяч, «сшитый» из 12 пятиугольников и 20 шестиугольников, или структура молекулы фуллерена С60). Поиск звёздчатых полуправильных многогранников продолжался около столетия, и вопрос об их общем числе был окончательно закрыт лишь в 70-х годах XX века.
Часть времени будет уделена понятию группы преобразований и перечислению всех возможных типов симметрии, которыми может обладать трехмерное тело. Затем мы установим связь между покрытиями сферы треугольниками Шварца и однородными многогранниками. Основная задача для рассказчика и слушателей – убедиться в том, что доказательство полноты списка трехмерных однородных многогранников элементарно и доступно для понимания. В заключение мы совершим небольшое путешествие в пространства высших размерностей и коснемся некоторых открытых проблем перечисления многогранников более общих классов.
Олег Николаевич Герман (мехмат МГУ) «Двойственность, принцип переноса и диофантовы приближения»
Двойственность – одно из фундаментальных понятий математики. Мы рассмотрим ряд задач, связанных с этим явлением, принадлежащих теории диофантовых приближений – одной из важнейших областей современной теории чисел. Мы докажем принцип переноса Хинчина, поговорим о диофантовых экспонентах, последовательных минимумах, многомерных цепных дробях, двойственных многогранниках и двойственных решётках. Если останется время, затронем также гипотезы Литтлвуда, Оппенгейма и Вирзинга.
Антон Гусев (мехмат МГУ) «Теорема Зигмонди»
Теорема Зигмонди утверждает, что у a^n-b^n есть простой делитель, которого нет ни у одного из чисел вида a^k-b^k при k
Эта непримечательная на первый взгляд теорема имеет обширное применение для решения уравнений в целых числах. В первой части курса мы научимся её доказывать. Для этого нам предстоит познакомиться с таким замечательным объектом, как многочлены деления круга. Во второй части мы рассмотрим некоторые примеры её практического применения. Для понимания курса достаточно базовых знаний о комплексных числах.
Глеб Геннадьевич Гусев (Яндекс, ФИВТ МФТИ)«Алгебраические уравнения и эйлерова характеристика»
Этот курс – простое введение в теорию топологических инвариантов алгебраических множеств. Из нашего курса Вы узнаете:
- о том, какую роль в науке играют комплексные числа,
- о том, как изучать систему уравнений, если множество ее решений бесконечно,
- о том, что такое топологическое пространство,
- о том, какие замкнутые двумерные поверхности можно найти в Книге,
- о том, как научиться мыслить о многомерных пространствах и множествах.
Дмитрий Ильинский (ФИВТ МФТИ) «Теория Рамсея»
Многим знакома следующая задача: «Среди любых шести людей найдутся либо трое попарно знакомых, либо трое попарно незнакомых». Из этой задачи возникла очень красивая и интересная наука, называющаяся теорией Рамсея. Мы введём основные понятия, докажем конечность чисел Рамсея, обсудим возникающие сложности в их поиске. Если останется время, поговорим о геометрических и алгебраических приложениях теории.
Курс не требует никаких знаний, выходящих за рамки школьной программы.
Никита Киреев (ФИВТ МФТИ) «Алгоритмы: задача о поиске наименьшего общего предка; продвинутые применения обхода в глубину»
Виталий Анатольевич Кошелев (Яндекс, ФИВТ МФТИ) «Геометрия Лобачевского»
Источником возникновения геометрии Лобачевского послужил вопрос об аксиоме о параллельных, которая известна также, как пятый постулат Евклида. Этот постулат, ввиду его сложности в сравнении с другими, вызвал попытки дать его доказательство на основании остальных постулатов. Вопрос о пятом постулате Евклида, занимавший геометров более двух тысячелетий, был решен Лобачевским. Это решение сводится к тому, что постулат не может быть доказан на основе других посылок евклидовой геометрии и что допущение постулата, противоположного постулату Евклида, позволяет построить геометрию столь же содержательную, как и евклидова, и свободную от противоречий.
Иван Митрофанов (мехмат МГУ) «Синхронизирующие раскраски и конечные автоматы»
Представьте ориентированный граф, рёбра которого покрашены в синий, красный и зелёный цвета.
Пусть из каждой вершины выходит ровно по одному ребру каждого цвета и в какой-то вершине сидит умный червячок, различающий цвета, умеющий ползать по рёбрам и понимающий простые команды.
Тогда, получив последовательность команд “зелёный, зелёный, красный, синий”, он проползёт четыре ребра и попадёт в новую вершину.
Можно ли составить такую последовательность указаний (может быть, длинную), что, выполнив её, червячок оказывается в одной и той же вершине графа _вне_зависимости_ от того, из какой вершины начинал?
Такой граф с цветными рёбрами называется графом состояний конечного автомата, эта задача — задачей синхронизации автомата, а последовательность команд, сгоняющая всевозможных червячков в одну вершину — синхронизирующим словом.
Никаких предварительных знаний не требуется, но простым курс не будет, так как во второй его половине мы разберём доказательство гипотезы (а с 2007 года – теоремы) о раскраске дорог (road coloring problem).
Если нам дан орграф (не раскрашенный), при каком условии его рёбра можно раскрасить так, чтобы для полученного автомата существовало синхронизирующее слово?
Были найдены два очевидных необходимых условия: сильная связность и непериодичность (что это такое, я расскажу на занятии). Спустя 37 лет А. Трахтман доказал, что эти же условия являются и достаточными.
Даниил Мусатов (Яндекс, ФИВТ МФТИ)«Константа Чейтина – ключ к тайнам математики»
Широко известна гипотеза Гольдбаха: любое чётное число, начиная с четырёх, можно представить в виде суммы двух простых чисел. Неизвестно, истинна эта гипотеза или ложна, но если она ложна, то контрпример можно найти алгоритмически. Достаточно просто перебирать все чётные числа по возрастанию и пытаться представить каждое из них в виде суммы двух простых. Иначе говоря, истинность гипотезы эквивалентна тому, что программа, ищущая контрпример, никогда не остановится. Это не единственная гипотеза с таким свойством: многие математические вопросы сводятся к проблеме остановки некоторой программы.
Оказывается, такие задачи можно решить, если знать значение константы Чейтина – вероятности остановки произвольной программы. Разумеется, вычислить эту константу на практике с достаточной точностью невозможно. Курс будет построен вокруг изучения этой константы: мы узнаем, как она определяется, каковы её свойства и какие проблемы поможет решить её знание. Попутно мы затронем теорию вычислимых функций и теорию колмогоровской сложности.
Хайдар Нурлигареев (57 школа), Борис Бычков (ВШЭ, 179 школа) «Введение в комбинаторику»
В предлагаемом курсе мы планируем осветить некоторые базовые вопросы комбинаторики, которые традиционно не входят в школьную программу. Его первая половина будет посвящена перестановкам и производящим функциям. Эти объекты, интересные и сами по себе, несут большую практическую пользу, поскольку являются удобными инструментами при решении различных задач комбинаторного характера. Во второй части будут обсуждаться классические результаты из теории графов, такие, как теоремы Эйлера и Понтрягина-Куратовского для планарных графов и теорема Кэли о числе остовов полного графа (и ещё кое-что, если успеем).
Наличие специальных предварительных знаний у слушателей не предполагается.
Андрей Михайлович Райгородский (ФИВТ МФТИ, Яндекс, МГУ) «Вероятностный метод»
Мы расскажем о том, как с помощью методов теории вероятностей решать сложные задачи комбинаторики и теории графов. В частности, речь пойдет об обычных и дистанционных графах, которые трудно красить и в которых, тем не менее, отсутствуют, казалось бы, препятствия к раскраске. Разумеется, все страшные слова, которые есть в этом тексте, мы подробно поясним в курсе. Начав с очень простых идей, мы, однако, довольно быстро перейдем к весьма нетривиальным технологиям.
Алексей Владимирович Савватеев(РЭШ, ФИВТ МФТИ) «Цепные дроби и алгебраические числа»
Курс посвящён очень красивой, но практически не затрагиваемой
в школьной программе теме: разложению вещественных чисел в
цепные дроби. В первой части курса речь пойдёт о разложении
квадратичных иррациональностей, и в качестве приложения мы
получим полное решение любых диофантовых уравнений второй
степени от двух переменных (и уравнения Пелля в частности),
а также докажем знаменитую теорему Лагранжа о периодичности.
Во второй части курса мы попробуем разложить в цепную дробь
кубические иррациональности (на примере $\sqrt[3]{2}$), после
чего естественным образом выйдем на поле $Q[\sqrt[3]{2}]$ и
арифметику в нём. В третьей части курса, если останется время,
мы докажем некоторые теоремы о приближении вещественных
чисел рациональными. Курс не требует никаких пререквизитов
и без проблем доступен для понимания ученикам 9-11 классов.
Андрей Сандлер (Яндекс, ФИВТ МФТИ) «Анализ и программирование игровых алгоритмов»
В течение курса слушателям предлагается придумать и реализовать на любом удобном языке программирования алгоритм для игры под названием «Битва питонов» (имеется в виду не python2 vs. python3 :). Технические правила игры будут изложены ниже, в общих чертах игра такая: две змейки передвигаются по полю и едят еду, сталкиваться им нельзя, ходить через стены можно. Если еда закончилась, то выигрывает тот, кто больше съел, иначе – тот, кто не нарушил правила (не врезался в соперника).
По итогам занятий планируется провести турнир, в котором сразятся все алгоритмы, прошедшие проверку (надеюсь, что будут и призы 🙂 ). Так как турнир подразумевает соревнование, то на занятиях планируется не разбирать какую-либо конкретную стратегию, а освещать общие вопросы теории алгоритмов, например, поиск в ширину или перебор с отсечением, которые могут пригодиться при написании кода игры. Заготовки на Pascal, C, C++, Ruby и Python лежат здесь (скоро будет), технические правила изложены тут. Если кто-нибудь пожелает программировать на языке, отличном от предложенных, просьба сообщить об этом по адресу andrei.sandler@phystech.edu, чтобы я добавил компилятор или интерпретатор этого языка в систему. Будет хорошо, если в школу вы приедете уже с некоторой работающей версией игры (можно посылать их мне на почту для проверки).
Михаил Тихомиров (Яндекс) «Вычислительная комбинаторика в задачах»
Тома Ферник (CNRS, University Paris 13) «Проблема домино»
Проблема домино заключается в следующем: по данному набору квадратов (плиток) с раскрашенными рёбрами понять, можно ли замостить ими плоскость так, что любые два примыкающие ребра были покрашены в один цвет. Мы увидим, что эта проблема неразрешима. Для этого мы покажем, что плитки умеют вычислять не хуже, чем машина Тьюринга, и что существует набор плиток, которыми можно замостить плоскость, но только непериодическим способом.
Данила Черкашин (СПбГУ) «Расходящиеся ряды»
Суммой ряда а_1 + .. + а_n + … называется предел последовательности частичных сумм S_k = a_1 + … + a_k.
Но что делать, если предела нету, то есть ряд расходящийся? Оказывается, можно рассмотреть другие определения «суммы» ряда,
при этом станет возможным суммирование некоторых расходящихся рядов (например, 1-1+1-1+1… или 1-2+3-4…), а «сумма», хотя и будет слабее обычной, все равно будет обладать многими разумными свойствами.
Курс не требует никаких знаний, выходящих за рамки школьной программы, и доступен широкой публике.
Илья Шкредов (ИППИ РАН, Математический институт им. Стеклова) «Введение в аддитивную комбинаторику»
Аддитивная комбинаторика – это молодая и активно развивающаяся область, находящаяся на стыке теории чисел и комбинаторики, а также интенсивно использующая инструменты из гармонического анализа, теории графов, эргодической теории, теории вероятностей,
алгебраической геометрии, топологии и геометрии чисел.
Основной предмет данной науки – это всевозможные комбинаторные утверждения, в формулировке которых присутствуют операции сложения или умножения. Например, что можно сказать о свойствах множества A+A (множества всевозможных попарных сумм), зная свойства множества A, и наоборот? Правда ли, что как бы мы не раскрашивали натуральные числа в конечное число цветов, у уравнения x+y=z найдётся решение такое, что x,y и z будут одноцветными? Как можно легко доказать, что любое число представимо в виде суммы некоторого фиксированного числа простых и единицы?
В мини-курсе мы коснёмся как можно более широкого круга задач аддитивной комбинаторики и сформулируем большое число нерешённых проблем.