Мощностная нижняя оценка

В работе [52, стр. 92] бездоказательно, просто как очевидный факт утверждается, что время поиска по крайней мере не меньше чем время необходимое на перечисление ответа. В нашей модели этот факт находит свое доказательство и носит название мощностной нижней оценки. В связи повсеместностью применимости мощностной нижней оценки часто при оценке времени алгоритма поиска оценивают только разность между временем поиска и временем перечисления ответа (см., например, [52]).

Пусть нам даны произвольные множества запросов X, записей Y и отношение поиска р на X х Y. Причем на множестве запросов задано вероятностное пространство (X, а, Р).

Скажем, что базовое множество Т допустимо для ЗИП /, если существует ИГ над базовым множеством J^r₁ который решает ЗИП /.

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

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

Теорема 12 (мощностная нижняя оценка). Пусть I = (X, V, р) — произвольная ЗИП, такая, что существует такая запись у G V, что 0(у, р) ф 0, Т — измеримое базовое множество, допустимое для I, тогда

Доказательство. Возьмем произвольный ИГ U, решающий задачу I. Такой граф существует, так как 1Л (1, Т) Ф 9.

Возьмем произвольный запрос х 6 X. Так как ИГ U решает ЗИП /, то ответ на запрос х

aside class="viderzhka__img" itemscope itemtype="http://schema.org/ImageObject">

Возьмем произвольную запись у 6 Зи (х). Поскольку запись у попала в ответ, то, значит, в ИГ U существует некий лист а, которому приписана запись у и такой, что у?_а(:г) = 1. А так как ip_Q(т) = 1 и никакой лист не совпадает с корнем, то существует цепь, ведущая из корня в лист а, проводимость которой равна 1, и в этой цепи есть ребро, ведущее в а, с проводимостью 1. Это ребро назовем проводящим ребром записи у. Понятно, что разным записям из Зи (х) соответствуют разные проводящие ребра, так как эти ребра ведут в разные листья. Если проводящее ребро записи предикатное, предикат, приписанный проводящему ребру, обязательно был вычислен перед тем, как мы попали в лист. Если проводящее ребро записи переключательное, то обязательно был вычислен переключатель, приписанный вершине, из которой исходит проводящее ребро. Причем такие переключатели для разных записей из Зц (х) будут разными, так как только одно из переключательных ребер, исходящих из одной вершины, может иметь проводимость, равную 1. Таким образом, каждой записи из Ju (x) можно сопоставить переключатель или предикат, вычисляемый непосредственно перед попаданием в соответствующий записи лист. Причем разным записям будут сопоставлены разные переключатели или предикаты. Отсюда следует, что Следовательно,.

А так как это неравенство выполняется для любого графа и то

Так как в библиотеке V существует такая запись у, что 0(г/, р) ф 0, то в любом ИГ, решающем ЗИП /, существует хотя бы одна цепь, и соответственно хотя бы одно ребро исходит из корня. Следовательно, Т (1_УТ) > 1.

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

У пражнения.

• 2.31. Пусть X = {1,2,…, ЛГ}, 5 = (Х_у X, =, Р,<�т) — тип поиска идентичных объектов, где а = 2*, Р — равномерная вероятностная мера, то есть для любого х 6 X выполняется Р (х) = 1/7V, V = {3,5,7,11,13,17,19}. Приведите мощностную нижнюю оценку для ЗИП I = (X, V,=).
• 2.32. Пусть Sdom 1 = ([0,1], [0,1], >, Р, <�т) — тип одномерной задачи о доминировании, где Р — равномерная вероятностная мера на [0,1], V = {yi, y2,…|Ук} Я [ОЛЬ Приведите мощностную нижнюю оценку для ЗИП / = ([0,1], V, >).
• 2.33. Пусть Sint = (X_int, Yint> Pint) — тип одномерного интервального поиска и на множестве запросов Xi_nt = {(u, v): 0 < и < v < 1} задана равномерная вероятностная мера. V = {уъУг, • • •, 2/fc} Q [0,1]. Приведите мощностную нижнюю оценку для ЗИП / = (Xi_nt, V, p%nt) — Оцепите сверху полученную величину.