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

Леммы о сведении.

В данном разделе мы приведем два случая, когда нижние оценки сложности для одних задач могут быть использованы для оценки сложности других задач.

Лемма 10 (первая лемма о сведении). Если I = (X, V,р) —

ЗИП7 F = (F, 0) — измеримое базовое множество, допустимое для I, то для любой такой ЗИП Г = (X,V',p), что ЩГ,Т) ф 0 u V С V', выполняется T(IF) ^ Т(1,Т) и Т(//, Т) ^ Т(/, Т).

Доказательство. Возьмем произвольный ИГ U 6 Ы{Г,Т). Уберем нагрузку с листьев, которым соответствуют записи из V' V, и объявим эти листья обычными вершинами. Если после этого образовались несущественные ребра и вершины, то уберем их. Получившийся ИГ обозначим через U'. Понятно, что U' разрешает ЗИП I и T(U') ^ T(U) и T(U') ^ T(U). Таким образом, мы показали, что для любого ИГ U 6 и(Г,Т) существует такой ИГ U' 6 U(I, Т), что T(U') ^ T(U) и Г(?/') ^ T(U). Откуда следует, что Т(Г,Т) > Т(1,Т) и Т{Г,Т)>Т{1,Т).

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

Лемма 11 (вторая лемма о сведении). Пусть I = (X,V,p) 6 6 5 = (Х,У,р, Р,<т) и Г = (X,V',p') 6 5' = (Х,У,р',Р,<т) - такие ЗИП, что |V| = У и существует взаимно однозначное соответствие ф: V —> V, такое, что для любой записи у 6 V7 выполухяется 0{ф{у),р') С 0(у,р); F = {F, 0) — измеримое базовое множество, допустимое для I и V, такое, что для любой записи у 6 У имеем ХУ,РF, тогда Т(Г,Т) > T(I,T) ti T(/',F) ^ f(/,F).

Доказательство. Возьмем произвольный ИГ U 6 U(JT). Для произвольного листа а ИГ U заменим его нагрузку у на ф(у), а нагрузку всех ребер, входящих в лист а, заменим на Хф(у),р? В результате мы получим ИГ U который разрешает ЗИП I и T(U') ^ T(U) и T(U') ^ ^ T(U). Откуда легко получается утверждение леммы.

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

Как следствие первой леммы о сведении мы легко можем получить нижнюю оценку сложности для класса задач, у которых в ответе всегда не более чем п записей.

Теорема 10. Если пнатуральное число, I = (X,V,p) — ЗИП, обладающая Вп -свойством, Т = (F, G)измеримое базовое множество, допустимое для I, то Т(1,Т) ^ W([|V|/n]), и если кроме того ЗИП I, такая, что для любой записи у ? V выполняется Р(0(у,р)) = = r, mo T(lF)*r-R([V/n]).

Доказательство. Выделим в библиотеке V подмножество V', которое обладает В-свойством. Это можно сделать следующим образом. Возьмем произвольную такую запись у, что ее тень пересекается с тенью хотя бы одной другой записи из V. Выбросим из V все записи, отличные от у, чьи тени пересекаются с тенью записи у. При этом число выброшенных записей будет не более чем n —1. С получившейся библиотекой данную операцию будем повторять до тех пор пока это возможно. В результате получим библиотеку V', обладающую В- свойством, причем V' ^ [|V|/n].

Теперь, применив к ЗИП Г = (X, Vр) теоремы 7 и 8 и первую лемму о сведении, получим требуемое.

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

Второй леммой о сведении удобно пользоваться, когда пересечения между тенями записей есть, но они малы по сравнению с самими тенями. Тогда можно перейти к такому отношению поиска, которое “подрезает” тени так, чтобы они взаимно не пересекались.

Другой случай использования второй леммы о сведении — это когда тени записей имеют примерно одинаковые, но все же разные вероятности, что можно сформулировать в виде теоремы.

Теорема 11. Если I = (X,V,p) ? S = (Х,У,р, Р,<т) — ЗИП, обладающая В -свойством, такая, что для любой записи у G V выполняется Р(0(у,р)) ^ г и существует такое множество Ау € G а, что Ау С 0(у,р) и Р(ЛУ) = г; Т = (F,G) — измеримое базовое множество, допустимое для I, такое, что для любой записи у 6 V имеем /av G F, где NfAv = Ау, то Т(1,Т) ^ г • R(V).

Доказательство. Рассмотрим отношение поиска р такое, что 0(у,р') = Ау для любой записи уV, и ЗИП V — (X,V,p'). Теперь воспользовавшись теоремой 7 и второй леммой о сведении, получаем

ЩГ) (!,?)>*• mV).

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

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