Семинар по алгоритмам и структурам данных ФКН создан для всех, кто интересуется последними достижениями данной дисциплины или ищет актуальные задачи для своей научной деятельности. Доклады доступны широкому кругу слушателей, включая аспирантов и заинтересованных студентов.
Заседания проходят по четвергам с 18:10 до 19:30, ориентировочно раз в месяц (следите за объявлениями).
Организатор семинара: Мамай Игорь Борисович, доцент департамента больших данных и информационного поиска ФКН
3) 14 мая, Филипп Рухович: Внешние биллиарды вне правильных многоугольников
Тема: Внешние биллиарды вне правильных многоугольников
Аннотация: Рассмотрим многоугольник 𝚪. Из точки p на плоскости проведем касательную (т.е. опорную прямую) к 𝚪 и отразим p относительно точки касания. Такое преобразование называется преобразованием внешнего биллиарда. При последовательном применении такой операции, точка может оказаться периодической (т.е. вернуться в какой-то момент в себя), апериодической (никогда не вернуться в себя), а также вырожденной (внешний биллиард можно применить конечное число раз).
Особое место занимает случай, когда 𝚪 есть правильный n-угольник. В случаях n=3,4,6 ситуация проста (апериодических траекторий нет); также ситуация была исследована для случая n=5 и, частично, n=10 (апериодическая точка есть, но периодические точки образуют множество полной меры). Автором были получены результаты для случаев n=8,12,10. Р.Шварц, основываясь на компьютерных экспериментах, высказал предположение, что только для случаев n=5,10,8,12, по-видимому, есть точное самоподобие, которое позволяет полностью описать периодические структуры и найти апериодические точки. Шварц проводил эксперименты для случая n=7, и самоподобие найти не удалось.
Тем не менее, более глубокий компьютерный анализ дал возможность установить, что в случаях n=7 самоподобие все-таки существует. С его помощью, легко показать существование апериодической точки. Более того, оказывается, что существует континуально большое множество различных замыканий апериодических орбит – явление, не имеющее места в ранее исследованных случаях.
В докладе пойдет речь о компьютерном доказательстве существования самоподобия и, как следствие, апериодической точки, а также о том, каковы могут быть дальнейшие шаги в изучении как случая n=7, так и других случаев. Также мы поговорим о том, какие алгоритмы могут быть использованы для доказательства фактов, связанных с внешними биллиардами.
Место проведения:Центральный университет (Москва, ул. Гашека, д. 7), аудитория Вега (4 этаж).
2) 23 апреля, Филипп Грибов: Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами
Тема: Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами
Аннотация: В модели сравнений давно показано, что существует оценка 𝛀(log n) на время выполнения основных операций с упорядоченным множеством (insert, delete, lower_bound). Однако при работе с целыми числами, кроме операций сравнения, доступны арифметические и битовые операции с целыми числами. В RAM-модели все эти операции выполняются за 𝓞(1), что позволяет при работе с целыми числами не ограничиваться сравнениями и снизить время выполнения основных операций с упорядоченным множеством.
На семинаре мы рассмотрим результат двух статей Fredman и Willard. В начале мы разберемся со структурой данных Fusion Tree, которая позволяет получить оценку 𝓞(log n / log log n) на операцию lower_bound в упорядоченном массиве целых чисел.
После этого мы разберем структуру данных Q-tree, которая позволяет при проведенном предподсчете за 𝓞(n) хранить любые упорядоченные множества целых чисел размера не более 𝓞(log n / 5) и делать основные операции с множеством (insert, delete, lower_bound) за асимптотику 𝓞(1). На основе этой структуры данных строится большинство алгоритмов для целых чисел, которые понижают известные нижние оценки в модели сравнения. Мы рассмотрим некоторые из этих алгоритмов, в частности объединив Q-tree и B-дерево, научимся строить упорядоченное множество целых чисел произвольного размера, в котором все основные операции будут выполняться за 𝓞(log n / log log n).
Место проведения: Покровский бульвар 11, аудитория R406.
1) 5 марта, Иван Смрнов: Точные оценки сортировок и распределённый перебор алгоритмов
Тема: Точные оценки сортировок и распределённый перебор алгоритмов
Аннотация: Задача сортировки сравнениями изучена давно и хорошо. Известна как нижняя оценка в 𝛀(n log n) сравнений, так и алгоритмы, достигающие времени работы 𝓞(n log n). На семинаре мы выберемся за пределы 𝓞-большого. Точное необходимое число сравнений для произвольного n неизвестно до сих пор, однако к уточнению оценки было сделано немало подходов: как со стороны разработок алгоритма с минимальным зазором относительно нижней оценки, так и к уточнению нижних оценок.
В 50-х годах прошлого века был опубликован алгоритм Форда-Джонсона со временем работы n log n + 𝓞(n), то есть с линейным отличием от оптимума. Мы разберём основные идеи этого алгоритма и его дальнейшие модификации — алгоритм Манакера и другие.
В области точных нижних оценок для небольших значений n существенная работа была проделана Печарски за прошедшие 20 лет. Он предложил двухфазный способ перебора алгоритмов сортировки, позволивший уточнить нижнюю оценку для n = 15 и ряда других значений. Мы обсудим метод Печарски, недавнее (2022 г.) продвижение, с помощью которого получилось улучшить оценки для n = 16-18, а также рассмотрим подходы к параллелизации алгоритмов перебора и их реализацию в модели распределенных вычислений.
Место проведения: Покровский бульвар 11, аудитория R506.
