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

Критерий допустимости ИГ

Пусть нам дана ЗИП I = (X, V,p).

Скажем, что ИГ U разрешает ЗИП I = у V, р), если для любого запроса хX ответ на этот запрос содержит все те и только те записи из V, которые удовлетворяют запросу х, т. е.

ИГ U, разрешающий ЗИП /, будем также называть допустимым для задачи /.

Пусть U — некоторый ИГ, у — запись из У. Через Ьи (у) обозначим множество листьев ИГ U, которым соответствует запись у.

Справедлива следующая теорема [22, 23].

Теорема 1. ИГ U разрешает ЗИП I = {X, Vyp) тогда и только тогда, когда для любой записи уV, такой что 0(у,р) Ф 0, справедливо Ьц(у) ф 0 и V <Ра = Ху,р> а дл* любой записи уV, такой <*eLu(y)

что 0(у,р) = 0, справедливо либо Ьц(у) = 0 либо V <ра = 0.

a€Lu (у)

Доказательство. Достаточность.

Возьмем произвольный запрос хX.

Возьмем произвольную запись у Е V.

Если 0(у,р) = 0 и, следовательно, х ф 0(у,р), то по предположению либо Ьц(у) = 0, либо V а = 0. Откуда следует, что у ф ? Л(х). освЬи(у)

Теперь рассмотрим случай, когда 0(у, р) Ф 0.

Если х ру, то Ху,р{х) = 1, и согласно предположению

Откуда следует, что существует лист аC(U) такой, что y?Q(x) = = 1. Следовательно, уJu(x).

Если х ф 0(у,р), то Ху,р(х) = 0, и согласно предположению V <Ра(х) = о. Откуда следует, что у ф Ju(x).

a€bi/(y)

Таким образом, мы показали, что

и тем самым доказали достаточность.

Необходимость.

Возьмем произвольную запись у € К

Если 0(у,р) = 0 и, следовательно, для любого запроса х 6 X имеем х ф 0(у,р), значит, для любого хX получим у ф Ju(x). Откуда следует, что либо Ьи(у) = 0, либо V «Ра = 0.

Теперь рассмотрим случай, когда 0(у,р) ф 0.

Предположим, что для данной записи у не выполняются предположения теоремы, т. е. существует такой запрос х, что

Но это означает, что у принадлежит в точности одному из множеств Ju(x) или V: х р у).

Следовательно, при этом х

и, значит, ИГ U не разрешает ЗИП I.

Тем самым теорема доказана.

По сути теорема 1 говорит, что если нам дана ЗИП I = (X, V, р), и мы хотим построить ИГ, разрешающий эту ЗИП, мы должны построить многополюсник, который между корнем и остальными полюсами реализует как функции проводимости все функции Ху,р> где у € К

Рис. 1.3.

1.6. Пусть 5 = (X, X, =) — тип поиска идентичных объектов, множество предикатов F задается соотношением (1.7), базовое множество имеет вид Т = (F,0), V = {2/i,2/2, •• • , 2/fc} Я X. Приведите пример информационного графа над базовым множеством Т, разрешающего ЗИП / = (X, V, =).

1.7. Пусть S = (X, X, =) — тип поиска идентичных объектов, множество переключателей имеет вид

базовое множество имеет вид Т = (0,G), V = {yi,2/2,• • • ,2/fc} Q X. Приведите пример информационного графа над базовым множеством Т, разрешающего ЗИП / = (X, И, =).

1.8. Пусть X = {1,2,..., iV}, S = (X, X, =) — тип поиска идентичных объектов, множество переключателей имеет вид

базовое множество имеет вид Т = (0, С?), V = {3,5,7,11,13,17,19}. Постройте информационный граф над базовым множеством разрешающий

ЗИП / = (X, V, =).

1.9. Пусть X = {1,2,... tN}j S = (X, X, =) — тип поиска идентичных объектов, V = {t/i,2/2,••-,2/fc} Я X. Предположим, что у < у2 < • •• < < у к. Метод блочного поиска с размером блока т, решающий задачу / = = (X, К, =), состоит в следующем. Если на вход алгоритма поиска подается запрос х 6 X, то, начиная с t = 1 до i = к/m, просматриваем записи у,.тЕсли х > yi m, то увеличиваем г на 1, иначе по очереди просматриваем записи t/(t-i)m+b2/(i—i)m+2>• • • ,у*т и сравниваем их с запросом х. При равенстве мы нашли нужную запись, если же ни для какой записи равенства не наблюдается, то ответ на запрос х пуст. Опишите базовое множество и постройте информационный граф над этим базовым множеством, который бы решал ЗИП I = (X, V, =) методом блочного поиска.

1.10. Пусть X = {1,2,... , TV}, V С X, рс отношение поиска, задаваемое на X х V и определяемое соотношением

т. е. хрсу, если у (Е V, ближайшее справа к х. При выполнении этих условий ЗИП / = {X, Vtpc) называется задачей о близости. Пусть базовое множество имеет вид Т = (0, G), где множество переключателей G задается соотношением (1.8). Постройте информационный граф над базовым множеством Т, разрешающий ЗИП / = (X, V,pc), если V = {3,5,7,11,13,17,19}.

1.11. Одномерная задача о доминировании задается типом Sdomi = = ([0,1], [0,1],^). Пусть V = {уьуг, •• • ,Ук} С [0,1]. Опишите некоторое базовое множество и постройте какой-либо информационный граф над этим базовым множеством, который бы решал ЗИП I = ([0,1], V, ^).

1.12. Пусть Sint = (Xint,Yint,pint) — тип одномерного интервального поиска, где отношение рш определяется соотношением (1.1), V = = {У1,У2, •• • ,Уб}, где yi = 1/6, У2 = 1/4, уз = 3/8, у4 = 2/5, у5 = = 3/4, ус = 7/8. Разрешает ли информационный граф, изображенный на рис. 1.3, где функции определяются соотношениями (1.2)—(1.6), задачу информационного поиска I = (Xj„t, V,pint)? Обоснуйте ответ.

Рис. 1.4.

1.13. Докажите, что информационный граф, изображенный на рис. 1.1, разрешает одномерную задачу интервального поиска I = (Xint, V, pint), где V = {У1,У2,УЗ,У4,У5,У6} — библиотека, изображенная на рис. 1.4.

1.14. Пусть Sint = (Xmi, YxntyРш) — тип одномерного интервального поиска, где отношение pint определяется соотношением (1.1), V = = {1/8, 1/7, 1/5, 3/7, 3/5, 4/5, 7/8}. Опишите некоторое базовое множество и постройте какой-либо информационный граф над этим базовым множеством, который бы решал ЗИП I = (Xint, V, Pint)•

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