«Системы представителей»
(Андрей Михайлович Райгородский)
«Теорема Руфини-Абеля»
(Алексей Яковлевич Канель)
«Диск + точка = сфера, или интегрирование в топологии»
(Глеб Геннадьевич Гусев)
«Предписанные раскраски графов и связанные с ними комбинаторные задачи»
(Александр Борисович Дайняк)
На лекциях мы обсудим несколько различных постановок задач раскраски графов.
Увидим, как к задаче раскраски свести одну из долго не поддававшихся доказательству гипотезы Диница
о латинских квадратах, и как для решения полученной задачи применить известный алгоритм Гейла-Шепли из теории игр.
Также будет рассказано про применение алгебраических методов для получения теорем о существовании раскрасок.
В конце будет представлен ряд нерешённых связанных с раскрасками задач современной теории графов.
Направление изложения будет определяться слушателями.
«Про диаграммы Юнга»
(Дмитрий Геннадиевич Ильинский)
«Нестандартный анализ»
(Алексей Яковлевич Канель)
«Диаграммы Ван-Кампена»
(Алексей Яковлевич Канель)
«Три эксперимента, которые потрясли мир»
(Константин Викторович Северинов)
«Задача Эрдеша-Секереша о выпуклых многоугольниках»
(Виталий Анатольевич Кошелев)
«Как работает Яндекс?»
(Виталий Анатольевич Кошелев)
«Рсшифровка генетического кода»
(Михаил Сергеевич Гельфанд)
«Сети Петри»
(Егор Самосват, Артем Бабенко, Александр Рябченко)
«О некоторых алгоритмах машинного обучения»
(Андрей Александрович Кустарёв)
Будет рассказано об одном из наиболее эффективных и часто используемых алгоритмов машинного обучения – алгоритме C4.5, строящего дерево решений в задаче классификации. Также планируется обсудить некоторые технические приемы, используемые для улучшения результатов классификации – бэггинг и бустинг. Если останется время, обсудим более современный, нежели C4.5, алгоритм Gradient Boosting Machine – известный также как TreeNet.
«Две теоремы о Бегущем городе»
(Даниил Владимирович Мусатов)
В соревнованиях по ориентированию участники должны посетить некоторые заданные точки за наименьшее время.
Для этого им нужно составить кратчайший маршрут.
Задача о составлении такого маршрута изучается с конца XIX века и известна под названием «задача коммивояжера»
(Travelling salesman problem, TSP). Эта задача трудна: при произвольных расстояниях между точками
неизвестно полиномиального алгоритма даже для приближенного решения
(которое хуже оптимального не более, чем в 10 раз). Однако, если точки расположены в метрическом пространстве
(т.е. выполнено неравенство треугольника), то за полиномиальное время можно найти приближение в 1,5 раза,
а если на плоскости – то сколь угодно близкое приближение.
На сдвоенной лекции будет дан обзор важнейших результатов и рассказан алгоритм Ароры
нахождения приближённого решения на плоскости. Каких-либо специальных предварительных знаний не требуется.
«Некоторые алгоритмы на основе линейного и полуопределённого программирования»
(Юрий Притыкин)
На 2–3 занятиях будет рассказано о том, что такое линейное и полуопределённое программирование, и рассмотрены некоторые примеры задач, которые можно решить с помощью такого подхода. Мы разберём приближённый алгоритм Гёманса и Вильямсона 1995 года для задачи о максимальном разрезе в неориентированном графе, а если успеем, и другие примеры. Мы постараемся свести к минимуму используемые понятия из линейной алгебры, а то, что останется необходимо (умножение матриц, скалярное произведение), разберём в начале.
«Вероятность и раскраски»
(Андрей Михайлович Райгородский)
«Числа Рамсея»
(Андрей Михайлович Райгородский)
«Что такое соотношения и соотношения между соотношениями»
(Алексей Яковлевич Канель)
«Непериодические мозаики»
(Алексей Яковлевич Канель)
«Архитектура поиска Яндекса»
(Денис Расковалов)
Я кратко расскажу, из каких компонентов состоит поиск Яндекса. Про то,
как построен самый крупный в Европе кластер, как удалось добиться масштабируемости
и надежности.
«Алгоритмы, используемые при поиске»
(Денис Расковалов)
Как устроен поисковый индекс? Как построить индексатор, обрабатывающий миллиарды документов?
Как устроено текстовое ранжирование? Будет рассказано о характерных для олимпиадного программирования
задачах, которые встречаются при реализации поисковой машины.
«Теория динамических игр»
(Алексей Владимирович Савватеев)
Динамическая теория игр — это попытка математически точно просчитать результат многопериодного
и растянутого во времени взаимодействия нескольких игроков с (частично) конфликтующими целями.
В рамках динамического подхода можно предсказать исход войны, возможность долговременной кооперации,
итог выборов и результат футбольного состязания, монополизацию тех или иных рынков и многое, многое другое.
В курсе будут изложены математические основы теории динамических игр, объяснено понятие динамического равновесия
и разобран ряд примеров.
«Что такое производящие функции»
(Алексей Андреевич Чернов)
«Совершенные графы»
(Алексей Андреевич Чернов)
«Алгоритмы сжатия данных»
(Алексей Андреевич Чернов)
«Сжатие с потерей данных»
(Алексей Андреевич Чернов)
Со сжатием каких-либо данных мы сталкиваемся постоянно – например, когда смотрим видеоролик в интернете
или показываем друзьям фотографии из путешествий. Мы поговорим о методах сжатия данных без потерь и с потерей
информации; о самых первых методах – и о новых идеях в этой бурно развивающейся области на стыке математики
и программирования.
«Теория формальных языков»
(Александр Юрьевич Чуклин)
Теория формальных языков — математическая дисциплина, которая находит применение в таких, казалось бы,
разных областях, как теоретическая информатика и лингвистика. В данном курсе нас будут
прежде всего интересовать красивые математические теоремы и задачи теории языков, грамматик и автоматов.
Курс рассчитан на слушателей с хорошей математической культурой,
но какие-то предварительные знания по теории алгоритмов не требуются.
«ДНК. История открытия и значение»
(Алексей Александрович Шпильман)
«Сравнение последовательностей и филогенетические деревья»
(Алексей Александрович Шпильман)
После открытия ДНК и первичной структуры белков (последовательностей
аминокислотных остатков), и установления связи – последовательность –
функция, стало ясно, что главным определяющим в биологии фактором
являются биологические последовательности. Встала задача о сравнении
последовательностей, соответствующим разным генам и белкам, как метод
сравнения самих функциональных единиц. Также сами последовательности
стали фактором, позволяющим выстраивать филогенетические эволюционные
деревья. Будет рассказано как об основных алгоритмах сравнения
последовательностей так и о методах построения таких деревьев.
