Алексей Яковлевич Белов «Дискретное преобразование Фурье, ряды Фурье и проблема Варинга»
Рассказ посвящен ряду задач теории чисел и теории приближений.
Игорь Беляев «Классические комбинаторные алгоритмы»
В первой, более простой части курса будет освещен спектр тем, ориентированных на участников, желающих улучшить свои навыки на не очень сложных задачах. Мы рассмотрим генерацию перестановок с повторениями и без повторений рекурсивным и нерекурсивным способами. Решим ряд задач, в которых можно эффективно использовать битовую арифметику, а также задачи на антагонистические игры.
В второй части курса рассмотрим подсчёт количества инверсий в перестановке 3-мя различными способами (с использованием сортировки слиянием, карманной сортировки, а также дерева Фенвика). Оценим эффективность каждого из подходов. В завершении мы разберем подсчет арифметического выражения методом рекурсивного спуска, а также затронем топологическую сортировку графа.
Александр Игоревич Буфетов «Детерминанты»
Борис Василевский «Теоретико-числовые алгоритмы в олимпиадном программировании»
Курс будет прочитан в одну длинную лекцию с небольшим перерывом. Мы начнём с быстрой реализации решета Эратосфена и его применения для подсчёта количества делителей для чисел 1, 2, …, N за линейное время. После этого мы обсудим расширенный алгоритм Евклида и обобщим его для решения линейных диофантовых уравнений с любым числом неизвестных. Далее, вспомнив необходимую теорию, мы научимся вычислять k-этажную степень двойки по модулю данного натурального T, а потом применим это знание для вычисления значения функции Аккермана по тому же модулю. Закончу я примером ещё одной задачи, идея решения которой довольно часто встречается в олимпиадном программировании.
В каждой из перечисленных тем сложность материала варьируется от начального уровня до довольно продвинутого понимания. К примеру, расширенный алгоритм Евклида должны знать все, а задача про функцию Аккермана когда-то давно была дана на международной олимпиаде. Я собираюсь подробно излагать сложные места, чтобы было понятно всем. После лекции для закрепления полученных знаний вам будет предложено решить последние две из разобранных задач. Тесты и чёткие условия к ним я выложу на ближайший ко входу в комповник компьютер.
Зачёт будет проходить на следующий день после лекции. Для получения зачёта автоматом нужно решить обе задачи, показать мне код программ и как они лихо проходят все тесты. Если у меня возникнет подозрение на то, что программа списана, вы получаете незачёт автоматом. Для получения обычного зачёта необходимо подойти ко мне в течение дня, следующего после лекции, и побеседовать со мной на освещённые в лекции темы.
Виталий Гольдштейн «Технология MapReduce и её применения»
Глеб Гусев «Смешанные объемы: топологический взгляд на алгебру и геометрию»
Будут новые куплеты той песни, которая началась на февральской школе, но они будут рассчитаны также и на нового слушателя.
Если два треугольника равны, то их площади совпадают. Значит, площадь – это мерка, с помощью которой можно различать геометрические фигуры. В топологии интервалы разной длины считаются равными, а отрезок и интервал считаются различными. Я собираюсь рассказать о замечательном подходе, который позволяет мерить так называемые топологические пространства.
Мы будем разрезать фигуры, складывать и умножать числа, и при этом говорить такие выражения как «интеграл по эйлеровой характеристике».
Александр Дайняк «Марковские модели»
В курсе мы рассмотрим, как можно описывать системы, меняющие своё
состояние во времени с той или иной вероятностью. Мы увидим, что в
рамках одной и той же схемы можно промоделировать структуру слов
некоторого языка, отказы в технических системах, азартные игры и др. В
частности, будет рассказано, как можно по тексту на латинице
определить, на каком языке этот текст написан, – эта задача довольно
часто встречается в информационном поиске.
Виталий Кошелев «Задача Эрдеша-Секереша о выпуклых многоугольниках на плоскости»
Сколько точек на плоскости будет достаточно, чтобы среди них всегда
можно было найти выпуклый многоугольник на заданном числе вершин?
Этот вопрос был впервые поставлен 75 лет назад группой знаменитых
венгерских математиков (и с этим связана отдельная красивая история).
Простота постановки задачи
привлекала очень большое количество исследователей, но тем не менее,
до конца задача не решена до сих пор. Но за прошедшее время
появилось очень много обобщений и близких задач. Я расскажу о текущих
достижениях и, в том числе, о совсем новых результатах.
Даниил Мусатов «Неформально о формальных языках»
Современный человек обитает в богатой языковой среде, состоящей из естественных языков человеческого общения, специальных отраслевых языков (например, язык радиообмена в авиации), языков программирования, языков знаков (например, дорожных) и так далее. В самом общем виде язык можно понимать как совокупность последовательностей символов из некоторого алфавита: слов, фраз, текстов, которые «написаны на этом языке».
В теории формальных языков смысл текстов неважен: изучается синтаксис, т.е. правила построения слов, фраз и текстов. Оказывается, все языки можно разделить на несколько классов в зависимости от сложности описания. В мини-курсе мы опишем эти классы и познакомимся с наиболее простыми из них: автоматными (регулярными) и контекстно-свободными. Теоретические концепции будут проиллюстрированы на примерах из жизни.
Юрий Притыкин «Что такое проблема равенства P и NP»
Проблема «P vs. NP» (равны ли P и NP) является одной из фундаментальных проблем теоретической информатики (theoretical computer science) и математики вообще, что подтверждается и разными внематематическими формальностями (например, это одна из семи «проблем тысячелетия», за решение каждой из которых объявлен приз в 1 миллион долларов). Я расскажу, в чём заключается формулировка проблемы (это уже потребует обсуждения многих интересных понятий), а также – по возможности – о разных результатах вокруг неё.
Андрей Михайлович Райгородский «Случайные графы и вероятность в комбинаторике»
В комбинаторике есть огромное количество задач, которые крайне просто
формулируются и, тем не менее, с трудом поддаются решению. Зачастую
вероятность оказывается единственным средством для штурма таких задач.
В рамках курса слушатели познакомятся с базовыми объектами и
инструментами теории вероятностей, а также с рядом красивых примеров
применения вероятностных методов при решении комбинаторных задач.
Отдельное внимание мы уделим понятию <<случайного графа>>. А именно, мы
с <<вероятностной точки зрения>> посмотрим на хорошо всем известные
свойства графов, и такой взгляд даст нам принципиально новое понимание
теоретико-графовых задач.
Алексей Владимирович Савватееев «Великая теорема Ферма при n=3»
Теорема Ферма вдохновляла и направляла исследователей на протяжении
долгих 3.5 веков. Её полное решение получено Эндрю Уайлзом в 1994-1995
годах, занимает сотни страниц и завершает плодотворные размышления
сотен других математиков. В процессе раздумий над ней разработан мощный
аппарат современной математической науки, и доказательство пока далеко от
“популярности”. Однако простейшие случаи $n=3,4$ вполне доступны
старшеклассникам. В лекциях будет изложено геометрическое (насколько
это возможно) доказательство теоремы Ферма для $n=3$, а также дано
общее представление о том, как человечество шло к решению одной из
самых великих и знаменитых в его истории загадок.
Егор Самосват «Об эффективных методах обнаружения дубликатов»
В настоящее время в интернете актуально стоит вопрос о плагиате, дублировании материалов и просто воровстве. Фраза «перепечатка или использование материалов нашего сайта возможна только с разрешения автора» уже никого не останавливает, дубликаты плодятся как грибы.
Сама по себе задача быстрой проверки, является ли какая-то новая страница дубликатом уже существующей, нетривиальна и интересна; об эффективных алгоритмах осуществления этой проверки и пойдет речь.
Андрей Сандлер «Алгоритмы поиска в графах»
На занятиях планируется подробное освещение алгоритмов поиска пути между вершинами в графах. Кроме стандартных BFS, DFS и алгоритма Дейкстры, в курсе заявлен алгоритм А*, который является лучшим на сегодняшний день алгоритмом поиска, и применяется в компьютерных играх (Age Of Empires, World Of WarCraft, Lines:)) По итогам занятий будет зачет, который можно будет сдать в компьютерном варианте.
Григорий Ривенович Челноков «Зачем нужен функциональный анализ в комбинаторике?»
Владимир Шарич «Инварианты узлов»
Теория узлов – сравнительно молодая математическая дисциплина на стыке
топологии, алгебры и комбинаторики. Основная задача формулируется так:
научиться алгоритмически различать узлы. В последнее время бурное
развитие связано с рассмотрением инвариантов конечного порядка и
хордовых диаграмм.
В курсе предполагается отправиться от начальных понятий и, опуская
техничные доказательства, добраться до некоторых вопросов, актуальных
на сегодняшний день. Таким образом, обязательно будут рассмотрены
движения Рейдемейстера, многочлен Конвея, особые узлы, инварианты
конечного порядка, четырехчленное соотношение на хордовых диаграммах.
Все явления будут иллюстрироваться на примерах и подробно обсуждаться.