• A
  • A
  • A
  • АБB
  • АБB
  • АБB
  • А
  • А
  • А
  • А
  • А
Обычная версия сайта

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

Семинар по алгоритмам и структурам данных ФКН создан для всех, кто интересуется последними достижениями данной дисциплины или ищет актуальные задачи для своей научной деятельности. Доклады доступны широкому кругу слушателей, включая аспирантов и заинтересованных студентов.

Заседания проходят по вторникам с 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 марта, Иван Смрнов: Точные оценки сортировок и распределённый перебор алгоритмов