|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
О СЛОЖНОСТИ ЗАДАЧ О МЕТРИЧЕСКОЙ БЛИЗОСТИдипломная работа (Специалист)
- Научный руководитель: Гасанов Э.Э.
- Автор: Остроухова Елена Николаевна
- Тип: Специалист
- Организация, в которой проходила защита: МГУ имени М.В. Ломоносова
- Год защиты: 2006
- Аннотация: Данная работа посвящена двум типам задач регионального поиска. В первой из этих задач отношением поиска является многогранник в пространстве $\mathbb{R}^s$. Для этой задачи получена серия алгоритмов, задаваемых некоторым натуральным параметром. В зависимости от значения этого параметра получаются различные оценки памяти и времени, которые дают верхнюю оценку функциональной сложности в последовательности точек. Вторая задача --- двумерная задача о близости в евклидовой метрике. Запросом в этом случае служит круг заданного радиуса $R$. Для того, чтобы снизить оценку среднего времени в задаче о близости в евклидовой метрике было предложено ввести новую характеристику сложности --- ошибку. Согласившись на некоторую погрешность в вычислениях, получаем константное среднее время. Для приведенных в данной работе алгоритмов приближенного поиска средняя ошибка составляет примерно $0.04$, т.е. на каждые $100$ точек ответа будем получать не более $4$ ошибочных.
- Добавил в систему: Гасанов Эльяр Эльдарович