Полная версия

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

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

Оценки В-сложности включающего поиска.

Теорема 33. Если I = п, V, У)ЗИП типа Sbool, F ~ базовое множество у допустимое для I, то Т(1,Т) ^ |У|.

Доказательство. Обозначим через 1 набор, состоящий из всех единиц, т. е. 1 = (1,..., 1).

Так как J/(l) = V, то согласно теореме 4

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

Следствие 13. Если Т — полное базовое множество для типа Sbool) то

ь

Теорема 34. Если I = (Вп, V, >^) — ЗИП типа Sbool > 7* = (F, G)базовое множество, такое, что Кп С F, то T(I,T) = |V|.

Доказательство. Нижняя оценка следует из теоремы 33, а верхняя оценка достигается на переборном алгоритме, задаваемом ИГ, изображенном на рис. 1.5.

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

Следствие 14. Если Т = (F, G) — базовое множество, такое что /Сп С F, то

ь

Лемма 31. Если I = п,У,У) — ЗИП типа Sbool• -F = (F, 0) — базовое множество, допустимое для I, где F — одно из трех множеств Мп, /Сп или Хп, и ИГ U € Ы(1,Т), то T(U) = Q{U).

Доказательство. Так как для любого предиката / 6 F /(1) = = 1, то запрос 1 доходит до всех вершин ИГ U. Напомним, что мы считаем, что ИГ не содержит несущественных ребер. Следовательно, все предикаты соответствующие ребрам ИГ U будут вычислены, т. е. Т(С/, 1) = Q(U). Но так как всегда Т(?/, х) ^ Q(U) для любых (/их, то

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

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

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>