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

Алексей Яковлевич Белов «Системы взаимодействующих конечных автоматов, или Роботы в лабиринтах»


Илья Игоревич Богданов «О комбинаторике слов»


Александр Игоревич Буфетов «Детерминанты и непересекающиеся пути»


Виталий Борисович Гольдштейн «Объединяемые структуры данных»


Виталий Анатольевич Кошелев «Задача Эрдеша–Секереша о выпуклых многоугольниках на плоскости»

Сколько точек на плоскости будет достаточно, чтобы среди них всегда можно было найти выпуклый многоугольник на заданном числе вершин?
Этот вопрос был впервые поставлен 75 лет назад группой знаменитых венгерских математиков (и с этим связана отдельная красивая история). Простота постановки задачи
привлекала очень большое количество исследователей, но тем не менее, до конца задача не решена до сих пор. Но за прошедшее время
появилось очень много обобщений и близких задач. Я расскажу о текущих достижениях и, в том числе, о совсем новых результатах.

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


Аким Сергеевич Кумок «Алгоритмы на строках»


Даниил Владимирович Мусатов «Что мы знаем о проблеме равенства P и NP»

Проверить решение олимпиадной задачи зачастую гораздо проще, чем найти
его. А что, если задача не олимпиадная, а алгоритмическая? Например,
требуется установить по графу, можно ли его вершины раскрасить в три
цвета, так чтобы одноцветные не были соединены ребром. Кажется, что
задач, решение которых легко проверить (они образуют класс NP), должно
быть больше, чем задач, которые легко решить (они образуют класс P).
Вопрос о том, так это или нет, т.е. равны ли классы P и NP, является
одной из главных нерешённых проблем современной математики.
Единственное существенное продвижение – обнаружение класса NP-полных
задач, к которым сводятся все остальные задачи из NP. В мини-курсе мы
определим, что значат слова “задача”, “решить”, “легко” и “сводятся”,
а также познакомимся с несколькими NP-полными задачами.


Виталий Алексеевич Павленко «Минимальное остовное дерево»

Задача поиска минимального остова в графе — одна из классических в computer science.
На первой лекции я расскажу и докажу алгоритмы Прима, Краскала и Борувки решения этой задачи, а также рандомизированный алгоритм, который позволяет находить минимальный остов за линейное время.
На второй лекции мы обсудим хорошие свойства минимальных остовов и решения некоторых необычных задач по этой теме.
Если останется время, поговорим о связи остовных деревьев с функционированием Интернета.
Конспект двух лекций будет изложен в виде
листочка с задачами.

«Наименьший общий предок»

За две лекции я расскажу несколько алгоритмов поиска наименьшего общего предка в корневом дереве.
Хотя эта задача не имеет большого значения в науке, технике и животноводстве, однако её решения весьма красивы,
а в их основе лежат очень любопытные идеи. Стоит сказать, что мы научимся искать минимум на произвольном отрезке
статического массива (для знатоков: решать задачу RMQ) за константное время с предподсчётом за O(N).
Кстати, задача поиска наименьшего общего предка — одна из немногих задач в информатике, решённых «до конца».


Андрей Михайлович Райгородский «О проблеме Борсука«

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


Михаил Абрамович Ройтберг «Конечные автоматы«


 

Алексей Владимирович Савватеев «Теория Галуа, или Почему не может существовать общей формулы
для корней многочленов 5-й степени (и выше)»