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

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

Заседания проходят по вторникам с 18:10 до 19:30, ориентировочно раз в месяц (следите за объявлениями).

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.