– Страница мероприятия
– 28 марта, суббота, 14:00 – 15:30
– Мраморный зал, ПОМИ РАН, наб. реки Фонтанки, 27, Санкт-Петербург
– Пожалуйста, не забудьте зарегистрироваться — это необходимое условие посещения
⭐️ О лекторе
Николай Мальковский — кандидат физико-математических наук; Principal Engineer, Chebyshev Research Center
📢 Анонс
Формально, succinct-структуры — это такие, которые используют o(N) дополнительной памяти для обеспечения операций над множеством из N бит. Неформально — это несколько способов хранения дерева размера N за 2N + o(N) бит и использования этих o(N) бит для навигации по дереву, а иногда и для ответов на довольно сложные запросы.
Одно из подобных битовых представлений вы, с большой вероятностью, встречали: делаем обход в глубину, каждый раз, когда опускаемся, записываем «(», когда поднимаемся — «)». В результате мы должны получить правильную скобочную последовательность длины 2N-2. В целом, вот эти 2N бит, но что можно делать с таким представлением? Как оказывается, всё, что нам обычно нужно от дерева, можно получить с помощью небольших вспомогательных вычислений. А сами succinct-деревья очень даже практичны, особенно когда число узлов переваливает за миллион.