Семинар по алгоритмам и структурам данных
Семинар по алгоритмам и структурам данных ФКН создан для всех, кто интересуется последними достижениями данной дисциплины или ищет актуальные задачи для своей научной деятельности. Доклады доступны широкому кругу слушателей, включая аспирантов и заинтересованных студентов.
Заседания проходят по вторникам с 18:10 до 19:30, ориентировочно раз в месяц (следите за объявлениями).
Организатор семинара: Мамай Игорь Борисович, доцент департамента больших данных и информационного поиска ФКН
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
5) 19 ноября, Филипп Грибов: Алгоритм Торупа для поиска кратчайшего расстояния во взвешенном графе за линейное время
4) 3 октября, Никита Звонков: Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер
3) 14 мая, Филипп Рухович: Внешние биллиарды вне правильных многоугольников
2) 23 апреля, Филипп Грибов: Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами
1) 5 марта, Иван Смрнов: Точные оценки сортировок и распределённый перебор алгоритмов