– Страница мероприятия
– 4 августа, вторник, 19:00 – 20:30
– Мраморный зал, ПОМИ РАН, наб. реки Фонтанки, 27, Санкт-Петербург
– Пожалуйста, не забудьте зарегистрироваться — это необходимое условие посещения
⭐️ О лекторе
Николай Мальковский — кандидат физико-математических наук; Principal Engineer, Chebyshev Research Center
📢 Анонс
Range minimum query — это довольно известная академическая задача, она важна и на практике, но не сама по себе. Часто она используется как рутина в алгоритмах типа LZ, суффиксных деревьев или поисковых индексов. У задачи есть несколько вариаций. Основная суть в том, что дан массив чисел, и нужно на произвольном подотрезке индексов искать минимум. Самый простой пример того, где такая задача может возникнуть — запрос к базе данных вида «какая максимальная зарплата сотрудников в возрасте от 30 до 40 лет?».
На семинаре я расскажу про эффективное решение статической задачи, то есть, когда массив известен заранее и не изменяется, но запросы заранее неизвестны. Наиболее эффективное решение такой вариации — это разреженные таблицы, их проблема в том, что они требуют O(n log n) памяти и, соответственно, применимы для размеров максимум ~10^7. Существует много подходов, как за счёт чуть более медленных запросов добиться использования O(n) памяти, включая классический алгоритм Фараха-Колтона — Бендера. Существуют также и succinct подходы, которые требуют ~2.5n бит памяти, но скорость ответа на запросы на практике у них уже заметно хуже. На семинаре я расскажу, как взять лучшее из обоих миров: два варианта, каждый из которых сравним по скорости ответа на запросы с разреженной таблицей, но при этом
— Первый вариант требует 1.05n дополнительных бит, но при этом нужно иногда подглядывать в исходный массив;
— Второй вариант требует 2.1n дополнительных бит, но заглядывать в исходный массив не нужно.