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

Пример оценки константы специальной ограниченности.

Введенное в данном разделе свойство специальной ограниченности формулируется несколько громоздко и использовалось лишь с целью облегчения доказательства теоремы. Но практически все неэкзотические распределения обладают этим свойством с той или иной константой, и вопрос только в том, чтобы эту константу подсчитать.

В качестве примера подсчитаем константу специальной ограниченности для равномерного распределения вероятности.

Лемма 50. Если функция плотности вероятности р(х) задает равномерную вероятностную меру на Xjntn> ™-о р(я) обладает свойством специальной ограниченности с константой 2 для любой конечной библиотеки, содержащейся в Vlntn-

Доказательство. Так как р(х) задаст равномерную вероятностную меру на Xintni то

Так как р(х) задает вероятностную меру на Xintn, то

Откуда

Легко видеть, что если p,(ui,vi,... г/*) — функция, определяемая соотношением (4.31), где i 6 {l,n — 1}, то для любого (t*i, vi,..., тУ V,-) € Х x-xXi справедливо

4-v-'

*

Возьмем произвольную конечную библиотеку V Э Yintn.

Пусть У* — множества, определяемые соотношением (4.20) для этой библиотеки, у*-1 = (у}, у],- •. yj"1) € У*'1 и p~<-i(ui,Vi) —

функции, определяемые соотношениями (4.33) и (4.34), где i G {1,п}. Тогда легко видеть, что для любого i G {2,п} и любого (ui,Vi) G Xi справедливо

(4.49)

Р1 («1, Vi) = Pi (иь Vi) = 2 (4.50)

в силу (4.48).

Следовательно, для функции р~*_, (г/*), определяемой соотношением (4.35), для любого i G {1,п — 1} и любого щ G [0,1] справедливо

Если обозначить через Ь{ начало, а через е* конец отрезка ^(мЧгГ1)), то для функции Vi(vi)y определяемой соотношением (4.36), для любого i G {l,n — 1}, любого G [6^, 1] и любого

УхМ'(у' *) справедливо

Осталось заметить, что соотношения (4.49)-(4.52) полностью доказывают утверждение леммы.

Следствие 19. Пусть ЗИП I = (ХхПт,У,Ршп) — п-мерная задача интервального поиска, т.е. задача типа Sintn, где V = к, Т — базовое множество, определяемое соотношениями (4.37)-(4.43), n ^ 1, Р является равномерной вероятностной мерой на Xintn , и R(I) = Е Р(0(у,ршп))- Тогда

yev

Данное утверждение является следствием леммы 50 и теоремы 50.

Отметим, что утверждения для многомерного случая задачи интервального поиска, приведенные в [27, 30, 157], отличаются от утверждения теоремы 50 в общем случае, но совпадают в случае равномерного распределения. Отметим также, что доказательства теорем для многомерного случая задачи интервального поиска, приведенные в [27, 30, 157], с целью сокращения объема отражают только идею доказательства. Полное доказательство этих теорем можно вести по методу, описанному в разделе для многомерной задачи о доминировании. Но в связи с более сложной геометрией множества запросов в задаче интервального поиска доказательство будет очень громоздким. Поэтому мы не приводим здесь это доказательство, тем более, что по порядку в обоих случаях оценки объемов совпадают.

Оценки В-сложпости задачи интервального поиска.

Вопрос о В-сложности для задачи интервального поиска полностью аналогичен ситуации с включающим поиском и задачей о доминировании, так как для любой ЗИП существует запрос, в ответ на который надо выдать всю библиотеку задачи, и, значит, при наличии в базовом множестве характеристических функций записей переборный алгоритм будем В-оптимальным. Сформулируем этот факт в виде теоремы.

Теорема 51. Если I = (Xintn, V,Pintn) ~ п-мерная задача интервального поиска, т.е. задача типа Sintn, F — базовое множество, содержащее характеристические функции всех записей из V, то ?(!,?) = V.

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