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

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

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

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

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

Справедлива следующая теорема.

Теорема 9. ИГ U решает ЗИП I = (X, V, p) тогда и только тогда, когда для любой записи у 6 V, такой, что 0(у_} р) ф 0, справедливо Ьи (у) Ф 0 и у </?_а = Ху.р> ^а любой записи

у 6 V, такой, что 0(у, р) = 0, справедливо либо Ьц{у) = 0, либо ^ = 0.

<*€Lu (у)

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

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

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

Если 0(у, р) = 0 и, следовательно, х ф 0(у, р), то по предположению либо Ьи (у) — 0, либо J <�р_а = 0. Откуда следует,.

e€?i/(y).

ЧТО уф Л (х).

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

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

Откуда следует, что существует лист, а € ?(?/) такой, что ра (х) = 1. Следовательно, у € *7с/(#).

Если х? 0(у, р), то Ху, р (^х) = 0, и согласно предположению V V? a (s) = 0. Откуда следует, что у ф Ju (^x) — <*€Lu (y)

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

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

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

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

Если 0(у, р) = 0 и, следовательно, для любого запроса х (Е X х ф 0(г/, р), значит, для любого х € X у & Ju (x). Откуда следует, что-либо Ьц (у) = 0, либо J <�р_а = 0.

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

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

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

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

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

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

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

Упражнения.

• 2.16. Пусть S = (Х_}Х_}=) — тип поиска идентичных объектов, множество предикатов F задается соотношением (2.7), базовое множество имеет вид Т — (F, 0), V = {yi, 3/2, •. •, У*} С X. Приведите пример информационного графа над базовым множеством F, решающего ЗИП I = (X, V, =).
• 2.17. Пусть S = (X, X, =) — тип поиска идентичных объектов, множество переключателей имеет вид

Рис. 2.3:

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

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

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

2.19. Пусть X = {1,2,…, N), S = (X, X, =) — тип поиска идентичных объектов, V = {yi, у2,…, Ук] Я X. Предположим, что У < У2 < • • * < Ук- Метод блочного поиска с размером блока т, решающий задачу / = (X, V_t =), состоит в следующем. Если на вход алгоритма поиска подается запрос х 6 X, то, начиная с i = 1 до: = fc/m, просматриваем записи у*._т— Если х > у*._т, то увеличиваем г на 1, иначе по очереди просматриваем записи y (i-i)_m+i, У (*-1)т+2> • > У" т и сравниваем их с запросом х. При равенстве мы нашли нужную запись, если же ни для какой записи равенства не наблюдается, то ответ на запрос х пуст. Опишите базовое множество и постройте информационный граф над этим базовым множеством, который бы решал ЗИП / = (X, V, =) методом блочного поиска.

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

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

2.21. Одномерная задача о доминировании задается типом.

Sdomi = ([0,1), [0,1],>). Пусть V = с [0,1]. Опишите некоторое базовое множество и постройте какой-либо информационный граф над этим базовым множеством, который бы решал ЗИП.

/ = ([ 0,1], К>).

2.22. Пусть Sint = (Xmt, Yi_ntу Pint) — тип одномерного интервального поиска, где отношение pint определяется соотношением (2.1),.

V = {У1,2/2,…, г/б}, где у = 1/6, уг = ¼, у₃ = 3/8, у₄ = 2/5, ys = ¾, ye = 7/8. Решает ли информационный граф, изображенный на рисунке 2.3, где функции определяются соотношениями (2.2) — (2.6), задачу информационного поиска I = (Xi_nt_y V_ypint)7 Обоснуйте ответ.

• 2.23. Докажите, что информационный граф, изображенный на рисунке 2.1, решает одномерную задачу интервального поиска / = (Xinty Vy Pint)у где V = {yi, У2, уз, У4, У5, Уб} — библиотека, изображенная на рисунке 2.4.
• 2.24. Пусть Sint = (Xinty Yint у Pint) — тип одномерного интервального поиска, где отношение pint определяется соотношением (2.1),

V = {1/8,1/7,1/5,3/7, 3/5,4/5,7/8}. Опишите некоторое базовое множество и постройте какой-либо информационный граф над этим базовым множеством, который бы решал ЗИП I = (Xinty V, pint).