Аннотация:В работе Артема Пропажина исследуется динамическая задача о прокалывании для потоков запросов, возникающих в задачах предотвращения столкновений. В задача о прокалывании элементы базы данных – это отрезки прямой, а запросы – точки прямой, и надо находить в базе данных все отрезки, содержащие запрос. Рассматривается поток данных, в котором добавляемые отрезки имеют тенденцию сдвигаться вправо на прямой, а запросы тоже сдвигаются вправо. Показано, что в этом случае длина ответа в среднем небольшая и с учетом этого предложена структура данных, обеспечивающая время вставки и удаления порядка log2 n, и время поиска порядка log n, где n размер базы данных. Написана компьютерная программа, реализующая предлагаемые алгоритмы