Семинар по алгоритмам и структурам данных

17 декабря 2024 в 18:10

Докладчик: Игорь Мамай, ФКН НИУ ВШЭ 

Тема: Вероятностная структура данных Zip-дерево

Аннотация: Самобалансирующиеся двоичные деревья поиска занимают важное место среди структур данных, так как позволяют эффективно реализовать различные алгоритмы сортировки и поиска. Также с их помощью можно эффективно реализовать такие абстрактные типы данных, как множество и ассоциативный массив.

Начиная с 1960-х годов, были предложены различные способы балансировки двоичного дерева поиска, и сегодня нам известны такие структуры данных, как АВЛ-дерево (1962), B-дерево (1970), Красно-чёрное дерево (1978), Splay-дерево (1985) и так далее. Также были предложены рандомизированные способы балансировки двоичного дерева поиска, и самым известным из них является Декартово дерево (1989).

При этом в 1989 году появилась вероятностная структура данных Skip List, в основе которой лежит определенная иерархия односвязных списков с дополнительными связями. Эта структура данных не является двоичным деревом поиска, но позволяет выполнять те же задачи. Преимуществами Skip List являются простота реализации и возможность параллельной работы с ключами.

Естественно, возникает вопрос, дает ли Skip List принципиально новые возможности в сравнении с самобалансирующимися деревьями поиска. Ответ на этот вопрос позже был получен. В 2007 году было построено отображение, преобразующее Skip List в двоичное дерево поиска. А затем в 2021 году было предложено новое вероятностное двоичное дерево поиска Zip-дерево, которое обладает естественным изоморфизмом со структурой данных Skip List.

На семинаре мы пройдем весь путь от Skip List до Zip-дерева, посмотрим на изоморфизм между ними, а также проведем сравнение Zip-дерева с Декартовым деревом.

Место проведения: Покровский бульвар 11, аудитория D108

19 ноября 2024 в 18:10

Докладчик: Филипп Грибов, ФКН НИУ ВШЭ

Тема: Алгоритм Торупа для поиска кратчайшего расстояния во взвешенном графе за линейное время

Аннотация: Для задачи поиска кратчайшего пути в графе давно известен алгоритм Дейкстры, который при использовании Фибоначчиевой кучи работает за асимптотику 𝓞(|E| + |V| log |V|). К сожалению, алгоритм Дейкстры нельзя ускорить до линейного времени работы, так как это потребовало бы существования кучи с линейным временем работы. На семинаре мы разберем алгоритм Торупа, который позволяет искать кратчайшее расстояние в графе за время 𝓞(|V| + |E|) с дополнительным ограничением, что веса ребер являются целыми числами.

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

В самом алгоритме Торупа используется множество других достаточно сложных алгоритмов, таких как линейный алгоритм построения остовного дерева, линейный СНМ при особых условиях запросов, atomic heap. Мы не будем подробно разбирать эти части алгоритма и скорее обзорно пройдемся по основным шагам алгоритма Торупа, тем самым сведя поиск кратчайшего пути к набору задач, которые в науке хорошо изучены и для которых существуют оптимальные решения.

Место проведения: Покровский бульвар 11, аудитория R601

3 октября 2024 в 18:10

Докладчик: Никита Звонков, ФКН НИУ ВШЭ

Тема: Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер

Аннотация: Многие алгоритмы на графах имеют большую сложность. Для некоторых задач (например, проверка на существование гамильтонова цикла) даже не придумано полиномиального по времени алгоритма. Однако большинство алгоритмов работают довольно быстро в большинстве случаев. В частности, для многих алгоритмов показано, что они работают быстро на случайных графах.
Будем называть случайным графом и обозначать через G(n,p) случайный элемент множества графов на n вершинах, каждое ребро которого появляется независимо от других с вероятностью p (вообще говоря, зависящей от n). В таких графах мы можем быстро решать сложные задачи с вероятностью, стремящейся к единице. В частности, проверка на существование гамильтонова цикла устроена очень просто: нам достаточно проверить, что степени всех вершин не менее двух.
Задача нахождения веса минимального остовного дерева, в отличие от многих других, решается довольно быстро, но случайная постановка заслуживает отдельного рассмотрения. Так, А. Фриз показал, что в полном взвешенном графе на n вершинах с независимыми одинаково распределенными весами U[0,1] по мере роста n вес минимального остовного дерева стремится к числу 𝝵(3) = 1/1³ + 1/2³ + 1/3³ + …. Натурально возникает вопрос: в чём причина настолько красивого ответа? Обладают ли красивыми ответами другие подобные задачи?
На докладе мы разберём задачу поиска веса минимального объединения k остовных деревьев, не пересекающихся по ребрам, обсудим алгоритм для решения этой задачи в общем случае и получим результат (пусть, и не такой красивый), обобщающий изначальную находку Фриза.

Место проведения: Покровский бульвар 11, аудитория N506 

14 мая 2024 в 18:10

Докладчик: Филипп Рухович, ФПМИ МФТИ

Тема: Внешние биллиарды вне правильных многоугольников

Аннотация: Рассмотрим многоугольник 𝚪. Из точки 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 этаж).

23 апреля 2024 в 18:10

Докладчик: Филипп Грибов, ФКН НИУ ВШЭ

Тема: Понижение оценки 𝛀(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. 

5 марта 2024 в 18:10

Докладчик: Иван Смирнов, ФКН НИУ ВШЭ

Тема: Точные оценки сортировок и распределённый перебор алгоритмов

Аннотация: Задача сортировки сравнениями изучена давно и хорошо. Известна как нижняя оценка в 𝛀(n log n) сравнений, так и алгоритмы, достигающие времени работы 𝓞(n log n). На семинаре мы выберемся за пределы 𝓞-большого. Точное необходимое число сравнений для произвольного n неизвестно до сих пор, однако к уточнению оценки было сделано немало подходов: как со стороны разработок алгоритма с минимальным зазором относительно нижней оценки, так и к уточнению нижних оценок.

В 50-х годах прошлого века был опубликован алгоритм Форда-Джонсона со временем работы n log n + 𝓞(n), то есть с линейным отличием от оптимума. Мы разберём основные идеи этого алгоритма и его дальнейшие модификации — алгоритм Манакера и другие.

В области точных нижних оценок для небольших значений n существенная работа была проделана Печарски за прошедшие 20 лет. Он предложил двухфазный способ перебора алгоритмов сортировки, позволивший уточнить нижнюю оценку для n = 15 и ряда других значений. Мы обсудим метод Печарски, недавнее (2022 г.) продвижение, с помощью которого получилось улучшить оценки для n = 16-18, а также рассмотрим подходы к параллелизации алгоритмов перебора и их реализацию в модели распределенных вычислений.

Место проведения: Покровский бульвар 11, аудитория R506.