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