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