|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
Решение динамической задачи о прокалывании для специальных потоков запросовкурсовая работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Пропажин Артем Алексеевич
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Кафедра: Кафедра математической теории интеллектуальных систем
- Год защиты: 2019
- Курс: 3
- Аннотация: В работе Артема Пропажина исследуется динамическая задача о прокалывании для потоков запросов, возникающих в задачах предотвращения столкновений. В задача о прокалывании элементы базы данных – это отрезки прямой, а запросы – точки прямой, и надо находить в базе данных все отрезки, содержащие запрос. Рассматривается поток данных, в котором добавляемые отрезки имеют тенденцию сдвигаться вправо на прямой, а запросы тоже сдвигаются вправо. Показано, что в этом случае длина ответа в среднем небольшая и с учетом этого предложена структура данных, обеспечивающая время вставки и удаления порядка log2 n, и время поиска порядка log n, где n размер базы данных. Написана компьютерная программа, реализующая предлагаемые алгоритмы
- Добавил в систему: Гасанов Эльяр Эльдарович