Мы используем файлы cookies для улучшения работы сайта НИУ ВШЭ и большего удобства его использования. Более подробную информацию об использовании файлов cookies можно найти здесь, наши правила обработки персональных данных – здесь. Продолжая пользоваться сайтом, вы подтверждаете, что были проинформированы об использовании файлов cookies сайтом НИУ ВШЭ и согласны с нашими правилами обработки персональных данных. Вы можете отключить файлы cookies в настройках Вашего браузера.

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

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

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

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

 

Организатор семинара: Мамай Игорь Борисович, доцент департамента больших данных и информационного поиска ФКН

 

 

18 марта 2025 в 18:10

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

Тема: Статическая оптимальность и другие свойства Splay-дерева

Аннотация: На семинаре речь пойдет про Splay-дерево. Эта структура данных широко известна и многие знакомы не только с ее определением, но и с тем, как выбираются потенциалы для оценки амортизированного времени работы Splay-дерева. Поэтому мы только вспомним саму функцию потенциала и сформулируем лемму об амортизированном времени работы операции Splay для произвольной вершины дерева.
Далее мы подробно обсудим, как выбор весов элементов позволяет вывести теорему о статической оптимальности Splay-дерева, а также теорему о балансе, теорему о рабочем множестве и теорему о статических указателях.
В дополнение мы обсудим, как можно получить нижнюю оценку на время работы статически оптимального двоичного дерева поиска. А также обсудим алгоритм, который за 𝓞(n2) строит самое быстрое статичное двоичное дерево поиска для заданного набора запросов.
В конце мы затронем теорему о последовательном доступе к элементам Splay-дерева. Эта теорема говорит о том, что для произвольного Splay-дерева последовательный доступ к его элементам в порядке возрастания требует 𝓞(n) действий. Этот результат показывает преимущество Splay-дерева над любым статичным деревом и дает почву для веры в справедливость гипотезы о динамической оптимальности Splay-дерева.

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

 

Регистрация

2025

Развернуть все

6) 17 декабря, Игорь Мамай: Вероятностная структура данных Zip-дерево

2024

5) 19 ноября, Филипп Грибов: Алгоритм Торупа для поиска кратчайшего расстояния во взвешенном графе за линейное время

4) 3 октября, Никита Звонков: Поиск минимального объединения остовных деревьев в графе со случайными весами рёбер

3) 14 мая, Филипп Рухович: Внешние биллиарды вне правильных многоугольников

2) 23 апреля, Филипп Грибов: Понижение оценки 𝛀(log n) на время выполнения основных операций с упорядоченным множеством при работе с целыми числами

1) 5 марта, Иван Смрнов: Точные оценки сортировок и распределённый перебор алгоритмов


 

Нашли опечатку?
Выделите её, нажмите Ctrl+Enter и отправьте нам уведомление. Спасибо за участие!

109028, г. Москва, Покровский бульвар, д. 11

По всем вопросам обращайтесь по телефону

+7 (495) 531-00-00 *27254

или пишите на почту

computerscience@hse.ru