О сложности интервального поиска на булевом кубе Блайвас Татьяна Дмитриевна

Введение к работе

1. Общая характеристика работы

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

Все возрастающий поток информационно-вычислительных работ требует дальнейшего совершенствования методов проектирования и разработки баз данных и поисковых систем. Решение этих задач невозможно без тщательного анализа накопленного опыта, построения математической модели баз данных и информационных систем. Исследование математической модели помогает решать задачи, позволяющие повысить эффективность поиска в базах данных. В работах [5, 22, 29, 30, 39, 53, 13] вводились различные формализации информационно-поисковых систем. В данной работе используется информационно-графовая модель, предложенная в [13]. Такая модель данных может найти применение при проектировании физической организации баз данных, а также при разработке интеграл ьньгх схем, обеспечивающих аппаратную реализацию быстрых алгоритмов поиска.

В данной работе используется такое понимание задачи поиска, при котором предполагается многократное обращение к одним и тем же данным, но, возможно, каждый раз с новыми требованиями к искомым объектам, то есть с разными запросами на поиск. Такие задачи обычно возникают в системах, использующих базы данных. Многократное использование порождает особую проблему — проблему специальной организации данных, направленной на последующее ускорение поиска. Процесс такой специальной организации данных может занимать много времени, что потом окупается в результате многократности поиска. Ценность алгоритма поиска в таком случае определяется варьированием запроса на поиск, например, показателем может служить среднее время поиска на запросе. Классификацию задач поиска на однократные и многократные можно найти в работах [51, 27, 13].

Пусть задано некоторое упорядоченное множество X. На множестве Х^п определим отношение частичного порядка следующим образом: если 0,6 X, о = (eii...,fln)j Ь = {bi,...,b_n), то будем писать о X J ("а предшествует Ь"), если flj < bi для любого і = 1,...,п. Если V С Д"^п,

Общая характеристика работы

и,w Х^п, и ^ w, то задача интервального поиска в X заключается в перечислении всех тех элементов у из V, для которых верно и < у < VJ.

Интервальный поиск имеет очевидное приложение к системам баз данных. В базе данных, содержащей записи о служащих некоторой компании, каждая запись имеет несколько атрибутов, таких, как возраст, жалование и т. д., и может рассматриваться как точка в n-мерном пространстве, в котором каждый атрибут соответствует измерению, а число измерений пространства п равно числу атрибутов. Типичная задача интервального поиска для двух измерений заключается в выявлении всех служащих, чьи возраст и жалованье находятся в заданных интервалах. Это пример взят из [22J. Другой пример можно найти у Д. Кнута [21]. Он рассматривал базу данных городов США с координатами в виде широты и долготы. К такой базе естественен вопрос о перечислении всех городов, попадающих в некоторой прямоугольник-запрос. Это типичная двумерная задача интервального поиска. Подобные задачи возникают также в статистике [48] и автоматизации проектирования [45].

Исследованию задачи интервального поиска в R" (в другом переводе с английского — регионального поиска) посвящено большое количество работ [22, 27, 33, 35, 36, 37, 38, 41, 42, 43, 44, 46, 47, 49, 50, 52, 55]. Приведем результаты некоторых из них. Алгоритм решения двумерной задачи интервального поиска путем сведения к решению четырех двумерных задач о доминировании можно найти в [22, 27]. Бентли в [33] предложил метод многомерного двоичного дерева (k-D-дерева), исходя из того, что бинарное дерево для одномерной задачи дает хороший результат. Этот метод имеет линейные затраты по памяти, но Ли и Вонг [46] показали, что в худшем случае этот алгоритм дает плохие результаты, так двумерная задача решается за время 0(Vk). Здесь и далее, к равно мощности библиотеки, а оценки приводятся без времени перечисления ответа. В работе [34] Бентли предложил метод прямого доступа, который решает задачу за время 0(log₂ к), но требует затрат по памяти порядка А³ для двумерной задачи. Гасанов в работе [18] для n-мерной задачи предложил алгоритм, который при затратах памяти порядка к^2п~¹ требует в среднем константное время, а в худшем случае решает задачу за время 0(log₃ к). Чтобы уменьшить требуемую память в работе [36] Бентли и Маурером был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени. Б работе Гасанова и Кузнецовой [20] предлагается модификация алгоритма Бентли-May pep а, решающего двумерную задачу интервального поиска. Эта модификация позволяет снизить исходное логарифмическое среднее время поиска до константного при сохранении логарифмического времени поиска в худшем случае. При этом этот алгоритм зависит от параметра, при вариации которого объем памяти, необходимый алгоритму, изменяется от 0(к³) до O(klogk), при этом среднее время поиска (без учета времени на перечисление ответа) изменяется от 0(1) до O(logJt). В частности, для любого е > 0 при объеме памяти 0(к^1+е) достигается среднее время поиска 0(1). С помощью метода дерева интервалов (или дерева регионов) Бентли и Шеймос [37] получили оценку времени поиска

Общая характеристика работы

Q.(\og2 к) при затратах памяти 0{к log^- к), где п — размерность задачи интервального поиска. Уиллард [55] и Люкер [49] независимо предложили модификацию дерева интервалов, которая позволила снизить время поиска до 2(log"^-1 к) при тех же затратах памяти. Чазелле в [42] для двумерной задачи смог снизить затраты памяти до О (к log₂ к/ Iog₂ log₂ к), но при этом возросла константа при логарифме в оценке времени. Во всех этих работах оценивается время поиска в худшем случае, И только Болоур описал метод хеширования [41], который он использовал вместо поиска по древовидным структурам в задаче интервального поиска. Применение этого метода позволило получить довольно быстрые в среднем решения зада-чи интервального поиска при условии, что область запросов находится в заранее определенных границах.

Однако, результаты, полученные для интервального поиска в евклидо
вом пространстве, нельзя использовать для задачи интервального поиска
на булевом кубе В. Решение задачи интервального поиска на булевом кубе
в рамках информационно-графовой модели предполагает сведение ее к за
даче синтеза схемы (называемой информационным графом), реализующей
систему элементарных конъюнкций. Поэтому методы исследования задачи
интервального поиска на булевом кубе гораздо ближе к методам, применя
емым при реализации системы к конъюнкций ранга п. Задача реализации
произвольной системы к элементарных конъюнкций ранга п контактными
схемами была впервые рассмотрена К.Шенноном [54] в 1949 г. Для данной
задачи (к = 2") была построена схема в виде контактного дерева с числом
контактов 2^n+l — 2. В 1958 г. О.Б. Лупанов [23] предложил недревовидную
конструкцию с числом контактов, асимтотически равным 2" = к. Зада
ча построения схемы для системы из к конъюнкций, где к < 2, впервые
была рассмотрена Э.И. Нечипоруком [25, 26] в 1969 г., для к 3> 2"/п им
был получен асимптотически оптимальный метод. Дальнейшее продвиже
ние в решении этой задачи было получено в 1975 г. Н.П. Редькиным [28].
Им были получены следующие факты: 1) число контактов в схеме, реа
лизующей к конъюнкций не превосходит min_r=i n(2]n/r[-(2^r + к — 2)); 2)

если log₂ fc = о(п) и log; п = o(logj к), то существует схема с асимптотически оптимальным числом контактов, равным кп/ log₂ к. А.Е. Андреевым [1, 2, 3, 4] и И. А. Вихлякцевым [11, 12] в 1989 г. было предложено асимптотически оптимальное решение задачи реализации системы it элементарных конъюнкций при условии Iog₂ t^nc числом контактов, асимптотически равным к.

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

Таким образом, разработка новых способов хранения и поиска информации, а также способов оценки их средней временной сложности, пред-

Общая характеристика работы

ставляется теоретически и практически интересной.

Цель работы. Рассматривается задача интервального поиска, которая состоит в следующем. Есть некоторое подмножество n-мерного куба, называемое библиотекой. Запрос задаст некоторый интервал (подкуб) булева куба. Необходимо перечислить все наборы из библиотеки, попавшие в данный интервал. Целью работы является исследование средней временной сложности задачи интервального поиска при различных ограничениях на структуру данных и базовое меюжєство функций, то есть множество функций, разрешенных к использованию.

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

Научная новизна. Исследования, проведенные в данной работе, направлены на изучение средней временной сложности алгоритмов поиска. Они используют в качестве своей основы информационно-графовую модель данных, предложенную Э. Э. Гасановым в работе [13]. Работы [15, 16, 17, 18, 19, 20] содержат результаты исследований интервального поиска на прямой и на плоскости; также в работе [13] одна глава посвящена исследованию задачи интервального поиска в n-мерном евклидовом пространстве. Но методы и алгоритмы, предложенные в этих работах, ни коим образом не могут быть использованы для задачи интервального поиска на булевом кубе. В работе [14] введено понятие задачи интервального поиска на булевом кубе и исследовано поведение функции Шеннона в классе древовидных схем в случае, когда нет ограничений на базовое множество функций, то есть разрешается использовать любую булеву функцию, и каждая функция вычисляется со сложностью, равной 1. К сожалению, в этом случае задача вырождается, и оценки носят почти тривиальный характер.

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

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

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

Предложены индуктивные способы построения решающих деревьев. Даны средние оценки временной сложности полученных деревьев.

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

Основные результаты диссертации, выносимые на защиту.

Общая характеристика работы

В работе исследуется следующая задача информационного поиска. Имеется некоторое подмножество V n-мерного булева куба B%, называемое библиотекой. На булевом кубе берется произвольный интервал («,ш), где и — (ut,-.. ,u_n), и> = (ші,... ,w_n) и и Ч w, то есть Uj < Wj t = 1,...,п. Требуется определить все такие элементы у Є V_t у — (у і,.. .,Уп), называемые записями, для которых выполнено и Ч у < и>. Приведем интерпретацию данной задачи.

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

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

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

Задачу можно решать, если на каждом шаге алгоритма проверять условие Uj < yj < Wj, j Є {1,,..,n} для фиксированного набора компонент записи.

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

Если же номера проверяемых на одном шаге компонент одинаковы для всех записей, то мы приходим к классу сбалансированных древовидных схем.

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

В работе получены следующие результаты.

1. Получено асимптотическое поведение среднего времени поиска в классе сбалансированных древовидных схем на последовательностях натуральных чисел fcj в предположении, что ki мощность баз данных.

Содержание работы

Показано, что для разных последовательностей асимптотическое поведение может быть разным. Полностью описав класс возможных асимптотических поведений. Эти исследования проводились для базисов элементарных конъюнкций, переменных и взвешенных элементарных конъюнкций.

2. Получены оценки функции сложности Шеннона в классе древовидных схем, причем для некоторых значений параметров эти оценки описывают порядок функции Шеннона, а для других значений параметров дают асимптотику логарифма ее сложности.

3. Предложены три индуктивных алгоритма автоматического построения информационных деревьев над базисом переменных. Показана несравнимость этих алгоритмов. Показана неустойчивость алгоритмов к выбору параметра. Получена средняя сложность для двух алгоритмов.

Апробация работы. Результаты настоящей работы докладывались на XIII Международной конференции по проблемам теоретической кибернетики (Казань, 2002г.), на XIV Международной конференции по проблемам теоретической кибернетики (Пенза, 2005г.), а также на семинарах механико-математического факультета МГУ им. М.В.Ломоносова: на семинаре "Математические вопросы кибернетики "под руководством академика РАН, проф. д.ф-м.н. О.Б.Лупанова (2005г.), на семинаре "Теория а»томатов^ипод руководством академика, проф., д.ф-м.н. В.Б. Кудрявцева (2005г.), на семинаре "Вопросы сложности алгоритмов поиска "под руководством проф., д.ф*м.в. Э.Э.Гасанова (2002-2004гг.), на семинаре "Моделирование сложных систем я процессов'¹ под руководством к.ф-м.н. А.С.Строгалова (2002г.)

Публикации. По теме диссертации опубликованы 6 печатных работ.

Структура и объем работы. Диссертация состоит из введения и трех глав. Объем диссертации 102 стр. Список литературы содержит 57 наименований.

2. Содержание работы

Мы будем использовать терминологию и обозначения ш работы [15], но поскольку в данной работе рассматриваются только древовидные схемы, то здесь будет приведена несколько упрощенная версия понятия информационного графа.

Бели X — множество символов запросов с заданным ва нем вероятностным пространством (Х,о~, Р), где а — алгебра подмножеств множества X, Р — вероятностная мера ва <т; У — множество символов данных (записей); р — бинарное отношение на X х У, называемое отношением поиска; то пятерка S = (А", У, р, сг, Р) называется шипом. Тройка / = (X, V, р), где V — некоторое конечное подмножество множества У, называемое библиотекой, называется задачей информационного поиска (ЗИП) типа S. Содержательно ЗИП / = {X, V, р) состоит в перечислении для произвольно

Содержание работы

взятого запроса х X всех и точно тех записей у V, что хру. Если Т

— суть множества символов одноместных предикатов, определенных на X,
Т называется базовым множеством и описывает множество элементарных
операций, используемых при решении задачи информационного поиска.

Над базовым множеством Т определяется понятие информационного графа (ИГ). В конечной многополюсной ориентированной сети выбирается вершина — полюс, называемая корнем. Остальные полюса называются листьями и им приписываются записи из Y. Ребрам ИГ приписываются предикаты из множества Т. Таким образом нагруженную многополюсную ориентированную сеть называют информационным графом над базовым множеством Т. Затем определяется функционирование ИГ. Предикатное ребро проводит запрос х є X, если предикат ребра истинен на х; ориентированная цепочка ребер проводит х, если каисдое ребро цепочки проводит х; запрос х проходит в вершину fi ИГ, если существует ориентированная цепь, ведущая из корня в вершину /3, которая проводит х; запись у, приписанная листу а, попадает в ответ ИГ на х, если х проходит в лист а. Ответом ИГ U на запрос х называют множество записей, попавших в ответ U на а:, и обозначают его Ju{x}- Эту функцию Ju{x) считают результатом функционирования ИГ U.

ИГ U разрешает ЗИП I = (X, V,p), если Ju{x) = {у Є V : хру}.

Вводится сложность ИГ. Предикат tf/j [х) истинный на х, если х проходит в вершину р, и ложный в противном случае, называется функцией фильтра вершины 0. Слоокностью ИГ U на запросе х Є X называется число T{U,x) — YLpeR $8 ' V/jO^i где 11 — множество вершин ИГ U, ірр

— количество ребер, исходящих из вершины Д. Эта величина равна чис
лу функций, вычисленных алгоритмом поиска, определяемым ИГ U, на
запросе х.

Пусть а = (сц,..., а„) Є Rⁿ. Обозначим через Т$ базис элементарных конъюнкций, в котором конъюнкции длины і соответствует вес ctj. Базис Т будем называть взвешенным базисом с системой весов а. Слоокностью ИГ U над взвешенным базисом с множеством весов а на запросе х X называется число T^a(U,x) = ^^^(з:) 22_е&₉ «е> где И — множество вершин ИГ U, & — множество ребер ИГ U, исходящих из вершины &, а_е

— вес предиката, являющегося нагрузкой ребра е.

Если каждая функция из Т (Tq) измерима (относительно алгебры а), то для любого ИГ U над Т (Tjj¹) функция T(U,x) (T^a(U,x)} измерима.

Сложностью ИГ U называется математическое ожидание величины T(U, х), равное T[U) = М_г Т{1/, х). Она характеризует среднее время поиска,

Взвешенной сложностью с системой весов а ИГ U называется математическое ожидание величины Т(ї7,а:), равное T^a(U) = М._х T^a(U,x).

Легко показать, что

T(U)=^_ff-P(N_vp[x)), - (1)

/36t/

Содержание работы

Если / предикат на множестве X, то Nf{x) = {х Є X : f(x) = 1). Сложностью ребра, исходящего из вершины /3 назовем число P(N_Vfi(x)). Взвешенной сложностью ребра е, исходящего из вершины 0 назовем число Р(Мур(х)) а_е, где о_е — вес нагрузки ребра е. Согласно (1), сложность (взвешенная сложность) ИГ равна сумме сложностей ребер.

Рассмотрим следующую ЗИП. Имеется некоторое fc-элементное подмножество n-мерного булева куба V В^ (библиотека). На булевом кубе задан некоторый интервал (u,w), где и — («i,.. .,и_п), w = (uii,... ,w_n), wuто есть «j < щ, Vi = 1,..-,п. Требуется определить все элементы у Є V, удовлетворяющие условию и -< у < VJ.

Очевидно, что если tii = 1 для некоторого І, то и Ш( = 1, а, следовательно, и у і = 1. Аналогично, если гщ = 0, то и у і = 0. Таким образом, вышеописанная ЗИП сводится к следующей: есть библиотека V В%, |V| = к, берем запрос х = (xi,...,x_n)- трехзначный вектор, компоненты которого

МОГуТ быТЬ раВНЫ ЛИбо 1, ЛИбо 0, Либо 2: ЄСЛИ Щ = 1, ТО Ж; = 1, ЄСЛИ У){ = 0,

то хі = 0, иначе хі = 2. Для данного запросах = (xi,...,х_п) хотим найти все у = (уі,... ,/„) Є V, для которых Уі = x_t, если Хі — 1 ИЛИ Хі = 0, И Уі любое из {0,1}, если Х{ = 2.

Получаем тип задач S_n—_}<7,P>, где В$ и В% трехзначный и двузначный (булев) кубы, соответственно, р : хру О (Хі =уі)У(хі — 2), а - множество подмножеств В$, и Р - равномерная вероятностная мера на В, то есть для любого а; Є В Р(х) = 3~".

Вершину со степенью полуисхода, равной нулю назовем висячей верши-пой. Информационным деревом (ИД) назовем ИГ без циклов, множество листьев которого совпадает с множеством висячих вершин, и все ребра которого ориентированы от корня к листьям. Высотой ИД назовем длину максимального пути из корня в лист.

Пусть X - множество переменных {xi,..., х_п}. Упорядоченное множество R. = {Xj,...,X_m} будем называть разбиением множества X, если Х_; ЛХу = 0 для t / j, i,j = l,...,m, и и!=Г^Хі = ^X

Пусть x Є {0,1,2} и у Є {0,1,2}. Определим функцию x^v :

^{

x, если (у = 1)к(х ф 2) х, если (у = 0)&(ж ^ 2) , 1, если (у = 2) V {х = 2)

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

Определим понятие яруса вершин. Вершиной первого яруса будем называть корень. Для любого числа г, ие большего высоты дерева плюс 1, вершинами j-ro яруса назовем такие вершины, из которых длина пути в корень равна і — 1. В информационном дереве нагрузкой цепочки ребер будем называть конъюнкцию нагрузок входящих в цепочку ребер. Сбаланси-рованним деревом, соответствующим разбиению R = {Xi,... ,X_m} множества X будем называть любое ИД высоты т над базисом элементарных конъюнкций

7Ь={<'& —«и^:р=1,...,п,«Є{0,1}},

удовлетворяющее следующим условиям:

Содержание работы

1) из каждой вершины ї-го яруса вершин, і — 1 го — 2, выходит

точно2^|Х'1 ребер, несли Xj = {xi_u ...,^,), то этим ребрам взаимно однозначно сопоставлены конъюнкции вида х"* fa &сх±^г, где

{О, і},ї = і,....к

2) из каждой вершины пг-го яруса выходит не более 2І^Х*І ребер, и им
приписаны конъюнкции (различные для каждой пары ребер, исходя
щих из одной вершины).

1-Сбалансированным деревом с характеристикой т будем называть сбалансированное дерево, такое, что если R = {Xj,..., X_m} — разбиение, задающее дерево, то jXi| = 1 для любого і, то есть решающее дерево построено над базисом переменных

Т\ = {li,I₂,.. .I_nt*l 1^2.- -En}-

Из каждой вершины тп-го яруса выходит не более 2' ^т' цепочек ребер, и им приписаны конъюнкции (различные для каждой пары цепочек ребер, исходящих из одной вершины) объединение которых по всем ребрам цепочки выглядит как а;^ & 1сх^_ч, где а і {0,1}, І = 1,..., g, и где

Л-m ⁼⁼ \^mj і * . у^тп^ /.

Множество задач I =< В", V, о > типа 5„, где \V\ = fc, обозначим через 2(п,к). Множество сбалансированных деревьев с характеристикой h, с к висячими вершинами, над базисом F обозначим Vp{п,к,Л).

Для множества базисных функций F введем понятие сложности ЗИП / С 1(п,к) над множеством Т>р(n,k,h):

T{I,F,h)= inf T(D).

Сложностью задачи J С Х{п, к) в классе сбалансированных (1-сбалан-сированных) деревьев над базовым множеством F назовем

T(I,F) = minT(I,F,h).

Сбалансированное ИД D, решающее задачу / в базисе F, назовем оптимальным, если Т{/, F) = T(D). В силу конечности множества сбалансированных деревьев, решающих задачу типа < В,В2,р >, оптимальное дерево существует.

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

Обозначим а = log* 2 (і logj ^ и 1 ⁱ . Теорема 1. Для любой ЗИП I С 1(п,к) выполняется

_Clfc2-log₃3 _ « < Т(Т,Го) < с₂к²~^³- І~.

Содержание работы

Следствие 1. При п -» со, к -4 со, / є Х{п, к) верно

r(f,7o)"fc^,os^.

Теорема 2. Для любого числа а Є [сі,сг] существует подпоследовательность натурального ряда к{, для которой выполнено

I) ki — оо при і —і со,

S) для любой последовательности задач информационного поиска 7$ Є

1(п, Jfci) при і -* оо Т(іі, То) ~ ofc,²~'^{B3 3}.

і l0g| J И C4 = 9.

Теорема 3. Для любой ЗИП I С Х(п,к) выполняется

_C3fc2-log_a S _ ₆ _ з /|у < Г(/,^і) < C4fc²-¹⁰^ * - ⁶ - ³ (I) "

Следствие 2. При п — со, А -+ оо, / Є ї(п, к) верно

Г(Л^і)"ІЬ^І0в:і*.

Теорема 4. Для любого числа о Є [сз,С4І существует подпоследовательность натурального ряда fc;, длл которой выполнено

1) ki -* со при і -* со,

5J для любой последовательности задач информационного поиска І{ Є 1{п,Ь) при і -* оо T{I_uTi) ~ afc?~^]oga3.

Умение хорошо реализовывать произвольные системы элементарных конъюнкций позволяет легко получить верхнюю оценку сложности для произвольного отношения поиска.

Пусть q — произвольное отношение на Bg х В% и 5_в,_п =< В%, В%, в > — соответствующий ему тип задач информационного поиска.

Положим

t f, „ї _ / !. ^еслн *W /»1*.WJ — \ о иначе

Для ЗИП / =< B$,V,e > Sg,_n, V = {у¹,...,y^k} обозначим F_S{I) = {/«> ./}> где /'(я) = /_е(х,у¹) для і = l,...,fc. Обозначим через Т(1) сложность минимального ИГ, решающего ЗИП J Є 5_e>n над базисом переменных.

Утверждение 1. Пусть ЗИП І Є S_titl, и пусть каждая функция из множества F_e(I) принимает значение "1"не более чем нар наборах. Тогда прип> Iog₂ {kp) выполнено

T(I)^ios*t.

Систему весов a = (ori,... ,a„) будем называть допустимой, если существует / U*=i,.„ г- ^(^п»*)і такая что

T{I,J^)

Содержание работы

Теорема 5. Система весов а = («і, , а„) является допустимой тогда и только тогда, когда существует номер і Є {1,..., га} такой, что

сц <3

_О-¹₎

Теорема 6. Длл любой ЗЯ77 7 С Х{п,к), любой системы весов а — (at,..., а_п), при п - со, к -4 со выполняется

Следствие 3. При п —^ со, А: —* со, 7 Є Z(n, к), а Є R верио

T(I,J$) -хк¹⁰***.

Теорема 7. Для любого числа о Є [сі, С4], существует подпоследовательность натурального ряда ki, существует система весов a = (ai,..., а_п), для которых выполнено

1) ki -> 00 при і — оо,

,) для любой последов а тельиостм задач информационного поиска 7; Г(п, fcj) при і -J. 00 T(/i,jy) ~ о *^2_І0Вз3.

Через Х>/(п,) обозначим всевозможные деревья, решающие задачу I из 1{п, к) над базисом переменных Ту. Функцией Шеннона сложности в классе древовидных схем над базисом переменных назовем число

L(n. к) = max min T(D).

В главе 2 исследуется поведение функции Шеннона и получены следующие оценки.

Теорема 8. При п -> оо, к —) оо выполнено:

1. Если к > 2"-¹, mo Цп, к) = 6 (±)"~^l + it (f)""¹ - 6;

Я. Ясли it >: 2", то Цп, к) х fc^loei1;

5. Ясли log₂ log₂ n = o(log₂ A), mo Iog₂ L(n, k) — log₂ і Iog₂ fc.

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

Обозначим через C(v,p,m) следующую операцию: из вершины v строим ориентированную от v цепочку ребер длины п — ти, а всем ребрам

цепочки последовательно (по ориентации) приписываем функции х^^т+г, I = 1,..., п — т. Листу (конечной вершине последнего ребра) приписываем запись у^р.

Содержание работы

Пусть V — {у¹,...,у^к} является подмножеством булева куба В". По упорядоченному множеству (у*¹,- --іУ'*)) ^{то есть по} множеству V и перестановке со = (ti,...,j(t) Є St, по заданной перестановке чисел а = О'ь ! Jn) Є 5п, задающей порядок координат, будем строить информационное дерево D, решающее задачу 7 =< BJ, V, р >.

Алгоритм с жестким порядком проверок (Al(V,aQ,a)y.

В множество вершин дерева D кладем корень с кодом v = * (пустой

символ).

С(*,п,0)

V = *

Для каждого »'р, р — 2,..., к выполняем Шаг 1. N = 1

Sf'"

Шаг 2, Если есть ребро, исходящее из и, с нагрузкой х-¹^¹,

то переходим в вершину с кодом V = [^,у/_я)-N = N + 1 Переходим к шагу 2, Шаг 3. Иначе C(v,i_p,N).

Таким образом, по библиотеке, заданной перестановке координат и при заданном порядке элементов библиотеки получаем дерево D = A1(V, pq,(t).

Пусть ребра информационного дерева занумерованы некоторым образом. Номером цепи ребер будем называть номером первого ребра цепи. Нагрузкой цепи ребер будем называть конъюнкцию нагрузок всех ребер цепи. Полной цепью из вершины v будем называть цепь ребер, конечная вершина которой имеет полустепень исхода, не равную 1, а все остальные вершины цепи имеют полустепень исхода, в точности равную 1.

Будем рассматривать следующие функции, и пользоваться следующими обозначениями и операциями.

E(v,N) — выдает полную цепь с номером JV, исходящую из вершины v.

V(v,N) — выдает конечную вершину полной цепи E(v,N).

N(v) — число ребер, исходящих из V.

f(c) Ті — нагрузка цепи с.

Х(с) — {х'*\ *' — множитель в /(с)}.

г(0 = {*?*,...,*}.

X'{c,i) = X(c)f\Y(i).

с^іі^г) ^— цепь с начальной вершиной vi и конечной вершиной 1. Операция С(с,г) удаляет полную цепь с = («і,«з), добавляет новые вершины v' и «", добавляет цепи ci = (ui,w')_t Сг = (v\v₂), d = {и\у").

Цепи Cl Соответствует Нагрузка АхХ'{с,і) ^х> ^^{єпи с}2 ^— АгЄХ(с)\Х'{с,і) ^Х'

цепи d — ЛяУ{»)\х'(<:.0 ^х- Первое ребро цепи с% получает номер, равный номеру цепи с, остальные ребра цепи с получают номер 1; все ребра цепи С2 получают номер, равный 1; первое ребро цепи с* получает номер 2, все остальные ребра — номер 1.

Операция NE(v,i,X) добавляет в вершину v цепь с номером первого ребра JV(u) + 1, номерами остальных ребер, равными 1, и суммарной нагрузкой цепи Да^х ^х- Листу V{v,N{v) + 1) приписываем запись у*.

Содержание работы

Для задачи / =< B",V,p > 1(п, к) и перестановки элементов библиотеки a = (t],...,ijt) Sic, решающее дерево будем строить при помощи алгоритма первого пересечения A2{V,a).

Алгоритм первого пересечения (j42(V, <т)) Добавляем в множество

вершин дерева корень Vq.

NEivoJuYin)).

р = 2.

Шаг 0. I? = vq, N = 1, У = Y(i_p). Перейти к шагу 1.

Шаг 1. Если X'(E{v,N),i_p) = 0, то

Перейти к шагу 2. Иначе

Перейти к шагу 3. Шаг 2. Если N

N = N + Ї, Перейти к шагу 1. Иначе

NE(v,i_p,Y). Перейти к шагу 5. Шаг 3. Если X'(E{v,N),i_p) = X{E(v,N))

v = V(v,N),N=l,Y = Y\X{E{v, N)).

Перейти к шагу 1. Иначе C(E(v,N),i_p). Перейти к шагу 5. Шаг 5. Если р< к

р = р + 1. Перейти к шагу 0.

Пусть V = {у¹,...,у^к} является подмножеством булева куба В%, По
упорядоченному множеству (у'¹ J/"), то есть по множеству V и пере
становке а = (ii,...,»*) Є Sk, будем строить информационное дерево D,
решающее задачу J =< В", V, р >. при помощи жадного алгоритма.

Жадный алгоритм (A3(V,a))

Добавляем в множество вершин дерева корень «о-

іге(«мі,У(*і))-

р=2.

Шаг 0. ь — v₀, Y = Y{i_p). Перейти к шагу 1.

Шаг 1.1 = maxjve{i,jv(v)} 1-^4^(^^0,^)1- Перейти к шагу 2.

Шаг 2. Если I = 0, то

Перейти к шагу 3. Иначе если і > 0

Перейти к шагу 4. Шаг 3. NE(v,i_p,Y). Перейти к шагу 6. Шаг 4. JV = min{« : \X'(E(v,n),i_p)\ = (}, Перейти к шагу 5. Шаг 5. Если Х'(Е{у^),і_р) = X(E(v,N)}

v = V(v, N),Y = Y\X{E(v, JV)). Перейти к шагу 1. Иначе

C{E(v,N),i_p). Перейти к шагу 6. Шаг 6. Если р < к

р = р + 1. Перейти к шагу 0.

Содержание работы

Фиксируем число п. Пусть V С BJ,

Если А некоторый алгоритм построения ИД, то через A(V,...) обозначим построенное по этом алгоритму ИД для входной библиотеки V. Здесь вместо многоточия стоят параметры, от которых зависит алгоритм.

Обозначим через Sa множество параметров алгоритма А. Скажем, что алгоритмы An В построения ИД несравнимы, если существуют библиотеки V"i и V2, такие что

T{A(V_U.,.)) > rain Т[В(Ух,о)) и min T(A(V_2lT(B(V_a,...)).

Теорема 9. Алгоритмы At и A2 попарно несравнимы.

Скажем, что алгоритм А лучше алгоритма В, если для любой библиотеки V

min Т(А<У>а))<Т(В(У,...)).

<г t-Ьл

Теорема 10. Алгоритм AS лучше алгоритмов А\ и А1.

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

Теорема 11. Алгоритм А\ устойчив по отношению к перестановке элементов библиотеки, и неустойчив по отношению к перестановке переменных. Алгоритмы А2 ы A3 неустойчивы по отношению к перестановке элементов библиотеки.

Положим Т 1(7) = ЛСГ(Л1{У»), где <т є S_n. Положим Tl(n,k) = М_УТ1(У), где V Є В$ : \V\ = к. Положим Г2(У) = M„T{A2(V,o-)), где и Є S_k. Положим Г 2(п, к) = M_VT2(V), где V Є В : \V\ = к. Получены следующие результаты.

Теорема 12. При п -юо, к -+ оо, к = 6(2"), n = 6(2*)

/ и \ іві і

"<**>* (і*ї)

Теорема 13. При п -) оо, fc -> 00, к = й(2"), п = б(2*)

Uog₂(fcn) /

Публикации по теме диссертации

3. Публикации по теме диссертации

1. Блайвас Т.Д. Решение задачи интервального поиска на булевом кубе. Проблемы теоретической кибернетики. Тезисы докладов XIII Международной конференции, Часть I, стр. 22

2. Блайвас Т.Д. Оптимальное решение задачи интервального поиска на булевом кубе в классе сбалансированных древовидных схем. Интеллектуальные системы, том 7, вып. 1-4, стр. 223-245

3. Блайвас Т.Д. Асимптотика интервального поиска на булевом кубе в классе сбалансированных древовидных схем. Дискретная математика, том 16, выпуск 4, 2004 г, стр. 65-78

4. Blaivas Т. D. The asymptotic behaviour of the complexity of the interval search on the Boolean cube in the class of balanced trees. Discrete Mathematics and Applications. Volume 14, No. 6, pp. 579-592

5. Блайвас Т.Д. Один алгоритм решения задачи интервального поиска на булевом кубе. Интеллектуальные системы, том 8, вып. 1-4, стр. 319-331

6. Блайвас Т.Д. Алгоритм с жестким порядком проверок построения решающих деревьев для задачи интервального поиска на булевом кубе. Проблемы теоретической кибернетики. Тезисы докладов XIV Международной конференции, стр.17.

7. Блайвас Т.Д. Сложность поиска по маске для алгоритма с жестким порядком проверок. Интеллектуальные системы, в печати

8. Блайвас Т.Д. Функция Шеннона сложности интервального поиска на булевом кубе в классе деревьев. Дискретная математика, в печати.