Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом

Пусть Vq — множество связных ориентированных деревьев с корнем, в которых каждое ребро принадлежит хотя бы одной цепи, ведущей из корня к какой-либо концевой вершине. Пусть D G Vq. Обозначим через Со — множество всех цепей в D, ведущих из корня к какой-либо концевой вершине.

Если С = (а1,а2),(а2,аз),…,(а_г-1,а_г) — ориентированная цепь, г—1.

то обозначим через Пс мощность следа цепи С, т. е. пс = Фон •.

«=1.

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

Дерево D, такое, что Z (D) = Z (D), назовем деревом с минимальным следом.

Лемма 8. Для любого натурального к существует дерево с минимальным следом с к концевыми вершинами, полустепень исхода любой внутренней вершины которого равна либо 2, либо 3.

Доказательство. Предположим, что дерево D содержит ветвь D вида изображенного на рис. 2.1, где / ^ 4. Рассмотрим дерево Ог вида, указанного на рис. 2.2, где г = [//2]. Имеем.

Таким образом, мы показали, что если в дереве есть ветвь вида D, то ее всегда можно заменить на ветвь вида 1?2> и дерево от этого не усложнится.

Осталось заметить, что ветвь вида D3, изображенного на рис. 2.3, всегда можно заменить на ветвь D₄, не усложняя при этом дерева. Тем самым лемма доказана.

Обозначим.

где к принимает натуральные значения.

Лемма 9. Для любого натурального к выполняется Z (k) = W (k).

Доказательство. Доказывать будем индукцией по числу к. Базис индукции, k = 1; Z ( 1) = 0 = W (l). к = 2; Z (2) = 2 = W{2). к = 3; Z{3) = 3 = W{3).

Шаг индукции. Пусть для любого t < к выполнено Z (t) = W (t). Согласно лемме 8, существует дерево с минимальным следом с к концевыми вершинами, которое имеет либо вид D, изображенный на рис. 2.4, либо вид D₂, изображенный на рис. 2.5.

Рассмотрим 3 случая:

• 1) 3¹ < к ^ 3^,Ч-3^,«^[1]. Тогда 3^/_1 < к/3[ ^ З^З^[1]„^[1]. Откуда согласно предположению индукции Z (]k/3[) = 3(/ — 1) 4- 1 =31 — 2, и, значит, Z (D_l) >3 + 31−2 = 31 + 1 = W (k).
• 2) 3^[1] 4- З*-^[1] < к ^ 2 • 3*. Тогда З'“^[1] 4- З'» {{ 3l 4- З*-1 (31 4- 3,'^[1])/2 = 2 • З'" 1,]к/2[ ^ 3*. Отсюда согласно предположению индукции Z (]k/2[) = 3/, и, значит, Z (D2) >2 + 31 = W (к).}} < ]к/3[ ^ 2 • З*"^[1]. Отсюда согласно предположению индукции Z (]k/3[) = 3(/ — 1) 4- 2 = 3/ — 1, и, значит, Z (D) >3 + 31 — 1 = 3/ 4−2 = W (k).
• 3) 2 • 3* < А: ^ 3^,+1. Тогда 2 • З*"¹ < ]к/3[ > 3*. По предположению индукции Z (]k/3[) = 3/, и, значит, Z (Di) > 3/ 4- 3 = И^(А:).

Рассмотрим 3 случая:

3) 2 • 3* < к ^ 3^I+1. Тогда.

Согласно предположению индукции 3/ + 1 ^ Z (]k/2) ^ 3/ + 2, и, значит, ?(Дг) ^ 3/ + 1 + 2 =.

С другой стороны, если D^D^, D'₃ — деревья с минимальным следом и их мощности (т. е. количество концевых вершин) различаются не более чем на 1, то Z (D) — W (k) и D — дерево с минимальным следом, а если 3^^log3^fc) ^ к ^ 8 • и D" и D₃ — деревья с минимальным следом, такие, что ||D|| — |Щ ^ 1₅ то Z (D2) = W (k) и D2 — дерево с минимальным следом.

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

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

Теорема 8. Если I = (X, V, p) — ЗИП, обладающая В-свойст- 00м, Т — (F, 0) — измеримое базовое множество, допустимое для I,

mo T (I, F)>W (V).

Доказательство. Возьмем произвольный ИГ U € U (I, Т). Согласно теореме 6 существует такое информационное дерево D € V¹, что T (U) ^ T (D). Оценим В-сложность ИД D.

В силу произвольности U теорема доказана.

Следствие 5. Если I = (X, V, p) — ЗИП, обладающая В-свойством, Т — (F, 0) — измеримое базовое множество, допустимое для I,

такое, что Fq С F, то T (I, F) = WAV'!).

Доказательство. Нижняя оценка следует из теоремы 8, а верхнюю дает ИД, изображенное на рис. 2.3, где D4 — дерево с минимальным следом с к концевыми вершинами, которые одновременно являются листьями графа, нагрузка листьев записями из V выбрана произвольно, а нагрузка ребер осуществляется по методу, описанному в доказательстве теоремы 6, так, чтобы выполнялось С-свойство.

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

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

Теорема 9. Если I = (X, V, p) — ЗИП, обладающая В-свойством, Т = (F, G) — измеримое базовое множество, допустимое для I, такое, что любой переключатель из G принимает не более т значений, где т > 1, то Т (1,Т) ^ ]log_m |V|[.

Доказательство. Возьмем произвольный ИГ U € Ы{1,Т). Так как ЗИП I обладает В-свойством, то легко видеть, что если мы удалим все ребра, исходящие из листьев, то функционирование ИГ не изменится. В самом деле, цепи, начинающиеся в некотором листе и ведущие в некоторый другой лист, которому приписана другая запись, неизбежно должны иметь такую проводимость, которая при умножении на функцию фильтра исходного листа равна тождественному нулю. Цепи, которые ведут из листа в лист, и обоим листьям приписана одна и та же запись, также можно разорвать без нарушения функционирования.

После удаления ребер, исходящих из листьев, удалим также образовавшиеся несущественные ребра и вершины. Полученный ИГ обозначим U'. Понятно, что U' € и (1,Т) и T (U) ^ T (U').

Таким образом в U' все листья концевые вершины. Для каждой вершины U из которой исходят предикатные ребра, занумеруем эти ребра подряд, начиная с 1.

Теперь каждой ориентированной цепи, начинающейся в корне, сопоставим последовательность целых чисел, которую назовем кодом цепи, следующим образом. В начальный момент код некоторой цепи не содержит ни одного числа. Начиная с первого, просматриваем по очереди ребра цепи и для каждого выполняем следующее: если данное ребро переключательное, то добавляем к концу кода число, приписанное данному ребру; если данное ребро предикатное и имеет номер <7, а из начала ребра исходит г ребер, то добавляем к концу кода сначала q чисел «-1», а затем т — q чисел «—2». Понятно, что для каждой цепи однозначно выписывается код и коды, соответствующие разным цепям, разные.

Предположим, что T (U') = п < ]log_m V[. Рассмотрим множество С всех цепей ИГ U ведущих их корня в некоторый лист, проводимость которых не равна тождественному нулю. Возьмем произвольную цепь С G С. Через пс обозначим длину кода цепи С. Пусть fc — проводимость цепи С. Возьмем произвольный запрос х 6 ЛГ/_С. Так как fc{%) = = 1, то запрос х доходит до каждой вершины цепи С, откуда следует, что число вычисленных переключателей и предикатов на запросе х будет равно по крайней мере п^, т. е. T (U>x) ^ пс• Следовательно, пс ^ п для любой цепи С € С. Так как все листья в U' концевые вершины, и так для каждой записи из V существует лист, которому приписана эта запись и в который ведет из корня некоторая цепь, то.

|С| > v.

Теперь, если для некоторой цепи С € С выполнено пс < п, то добавим п — пс нулей к коду цепи С. Полученные коды цепей из С обладают следующими свойствами:

• 1. коды, соответствующие разным цепям, разные;
• 2. никакой код не может быть префиксом другого кода;
• 3. для любых двух кодов, имеющих общий префикс длины / (Z < п), в обоих кодах / + 1-й элемент является одновременно
• • либо отрицательным числом,
• • либо нулем,
• • либо положительным числом.

Из свойств 2 и 3 сразу следует, что различных кодов может быть не более чем тп^п. Так как п < ]log_m |V|[ и п — целое число, то п < < log_m |V|. Отсюда следует, что число различных кодов не более чем mⁿ < 7П^1обт1Ч = |V|. То есть, кодов длины п не хватит, чтобы закодировать все цепи из С. Противоречие.

Таким образом, мы показали, что для любого ИГ U € U (I, T) выполняется T (U) ^)log_m |V|[. Следовательно, Т (/, Т) ^ ]log_m V[.

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

Результат теоремы 9 аналогичен теоретико-информационной нижней оценке [121], но все же является несколько более сильным, поскольку доказан для произвольных сетей, а не бинарных деревьев.

• [1] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [2] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [3] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [4] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [5] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [6] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [7] 3l 4- З*-1 < к ^ 2 • 3Z. Тогда ]к/2 > (31 4- 3,'{{ 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).
• [8] 3* < к ^ З1 4−31'1. Тогда По предположению индукции Z (]fc/2[) = 3(/ — 1) 4−2 = 3/ -1, и, значит, Z (D2) 5*24−3/ -1 = 3/ 4−1 = W (k).