|
ИСТИНА |
Войти в систему Регистрация |
ИПМех РАН |
||
Синтез динамических информационных графов для специальных потоков запросовдипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Горинова Юлия Юрьевна
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2019
- Аннотация: В работе Юлии Гориновой исследуется динамическая задача поиска идентичных объектов. Исследование ведется с помощью динамических информационных графов (ДИГ), которые представляют собой информационные графы, по которым блуждают конечные автоматы и выполняют операции поиска, вставки и удаления информации. У ДИГ имеется 2 особых параметра: размер обозреваемой окрестности R и степень инцидентности вершин графа N, и такие ДИГ называются (R,N)-ДИГ. А.А.Плетнев показал, что существуют (2,2)-ДИГ, которые могут обрабатывать произвольные потоки запросов, но при этом не существуют (1,2)-ДИГ, которые бы обрабатывали произвольные потоки запросов. Для (1,N)-ДИГ, где N>2, вопрос остался открытым. В работе Ю.Гориновой показано, что существуют (1,4)-ДИГ, которые могут обрабатывать потоки запросов, которые не содержат двух вставок подряд и приблизительное равное число поисков и удалений, и существуют (1,2)-ДИГ, которые могут обрабатывать потоки запросов, к которых число операций поиска не менее чем в 2 раза больше числа операций удаления.
- Добавил в систему: Гасанов Эльяр Эльдарович