Меню
Главная
Авторизация/Регистрация
 
Главная arrow Информатика arrow ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
Посмотреть оригинал

Одномерная задача интервального поиска

В данном разделе рассматривается следующая задача. Дано конечное множество точек из отрезка [0,1]. Запрос на поиск задает некий отрезок [а,Ь] С [0,1]. Надо перечислить все точки из множества, которые попадают в отрезок [а, 6]. Это известная геометрическая задача поиска, описанная, например, в [64] и называемая одномерной задачей интервального поиска. В данном разделе исследуется вопрос, какие алгоритмы возникают, если ограничивать набор доступных средств, или, более формально, при различных базовых множествах. Получены также некоторые нижние оценки, с помощью которых показывается, что соответствующие полученные алгоритмы не могут быть существенно улучшены при данных ограничениях на набор доступных средств. Результаты данного раздела были опубликованы в [28, 156].

Итак, в одномерной задаче интервального поиска множество записей Yint есть отрезок [0,1], множество запросов Xint есть множество отрезков [u, v] С [0,1], или множество пар точек (и, г>), таких, что 0 ^ и ^ v ^ 1, т. е. X{nt = = (u, v): 0 ^ tx ^ v ^ 1}.

На X^t задано вероятностное пространство (Xjnt,a, Р), где о — алгебра подмножеств множества Xint, содержащая все прямоугольники со сторонами параллельными осям координат и прямоугольные равнобедренные треугольники с катетами также параллельными осям координат, Р — вероятностная мера на <7. Будем считать, что мера Р определяется функцией плотности распределения вероятностей p(tx, v), т. е. для любого В ? а

Для удобства будем считать, что p(u, v) определена на всем квадрате [0,1] х [0,1], но p(u,v) = 0 при (u,v) & Xint.

Отношение поиска, которое будем обозначать через pjnt, определяется соотношением

где (u,v) € Xint, У € Ут^-

Тип Sint = {Xint , Y{nt) pint, P) будем называть типом одномерного интервального поиска.

В следующих пунктах мы исследуем задачи типа 5jnt при различных базовых множествах.

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Популярные страницы