О сложности интервального поиска на булевом кубе тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский государственный университет им. М.В. Ломоносова

На правах рукописи

Блайвас Татьяна Дмитриевна

О СЛОЖНОСТИ ИНТЕРВАЛЬНОГО ПОИСКА НА БУЛЕВОМ КУБЕ

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва - 2005

Работа выполнена на кафедре математической теории интеллектуальных систем механико-математического факультета Московского государственного университета им. М.В. Ломоносова

Научный руководитель: доктор физико-математических наук,

профессор Гасанов Эльяр Эльдарович Официальные оппоненты- доктор физико-математических наук

Гашков Сергей Борисович, кандидат физико-математических наук Мадатян Хикар Асилбекович Ведущая организация- Московский энергетический институт

Защита диссертации состоится 28 октября 2005 г в 11 ч. 00 мин на заседании диссертационного совета Д 501 001.44 в Московском государственном университете им. M В. Ломоносова по адресу: 119992, ГСП-2. Москва. Ленинские горы, МГУ. 2-й учебный корпус, факультет ВМиК, аудитория 685 С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ Автореферат разослан 27 сентября 2005 г.

Ученый секретарь диссертационного совета

(технический университет) (МЭИ(ТУ))

профессор

Н.П. Трифонов

лсюб-у „,_,//■>,т

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

Актуальность темы. В связи с постоянным расширением области

компью-

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

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

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

ЧЦГасанов Э. Э , Кудрявцев В.Б. Теория хранения и гтоигка информации. — М , ФИЗ-МАТЛИТ, 2002

РОС НДЦИм >„,ь,!„я БИБЛИОТЕКА СПстербу 09 ЮОЗиги

Пусть задано некоторое упорядоченное множество X. На множестве Хп определим отношение частичного порядка следующим образом: если а,Ь Е Хп, а = (а\,..., ап), b = (Ьь ..., Ь„), то будем писать а ■< Ь (а предшествует Ь), если аг < Ьг для любого i = 1,... ,п Если V С Xя, u,w G X", и < w, то задача интервального поиска в Хп заключается в перечислении всех тех элементов у из V, для которых верно и < у < w.

Интервальный поиск имеет очевидное приложение к системам баз данных. В базе данных, содержащей записи о служащих некоторой компании, каждая запись имеет несколько атрибутов, таких, как возраст, жаяование и т. д., и может рассматриваться как точка в n-мерном пространстве, в котором каждый атрибут соответствует измерению, а число измерений пространства п равно числу атрибутов. Типичная задача интервального поиска для двух измерений заключается в выявлении всех служащих, чьи возраст и жалованье находятся в заданных интервалах Это пример взят из |2|2

Исследованию задачи интервального поиска в R™ (в другом переводе с английского - регионального поиска) посвящено большое количество работ Однако, результаты, полученные для интервального поиска в евклидовом пространстве, не переносятся на задачу интервального поиска на булевом кубе Решение задачи интервального поиска на булевом кубе в рамках информационно-графовой модели предполагает сведение ее к задаче синтеза схемы (называемой информационным графом), реализующей систему элементарных конъюнкций. Поэтому методы исследования задачи интервального поиска на булевом кубе гораздо ближе к методам, применяемым при реализации системы к конъюнкций ранга п Задача реализации произвольной системы к элементарных конъюнкций ранга п контактными схемами была впервые рассмотрена К.Шенноном [З]3 в 1949 г. Для данной задачи при к = 2" была построена схема в виде контактного дерева с числом контактов

2|2\JJu Д, Препарата Ф Вычислительная геометрия Обзор.// Кибернетический сборник - 1987, Т. 24 - С.5-96

3[3\Shannon С.Е The synthesis of two-terminal switching circuits // Bell Syst Techn J -

1949. - V 28 - N1 - P.59-98 i

2П+1 — 2. В 1958 г О Б. Лупанов [4]4 предложил недревовидную конструкцию с числом контактов, асимтотически равным 2™ — к. Задача построения схемы для системы из к конъюнкций, где к < 2", впервые была рассмотрена Э И Нечипоруком [5]5 в 1969 г., для к 2"/п им был получен асимптотически оптимальный метод. Дальнейшее продвижение в решении этой задачи было получено в 1975 г. Н.П. Редькиным [б]6. Им были получены следующие факты- 1) число контактов в схеме, реализующей к конъюнкций не превосходит гшпг—1, )П(2]п/г[-(2г + к - 2)); 2) если \0g2k = б{п) и тг — д{\щ2к), то существует схема с асимптотически оптимальным числом контактов, равным кп/ к А Е Андреевым и И.А Вихлянцевым в 1989 г. было предложено асимптотически оптимальное решение задачи реализации системы к элементарных конъюнкций при условии 1о§2 к ~ п г, числом контактов, асимптотически равным к [7]т, [8]8.

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

*[4]Лупанов ОБО синтезе контактных схем // Доклады АН СССР - 1958 - Т 119 - N1 - С.23-26

ъ\Ь\Нечипорук Э.И. О топологических принципах самокорректирования // Проблемы кибернетики. — 1969, вып.21. — С.5-102

6[6]Редькин НПО реализации систем конъюнкций контактными схемами // Проблемы кибернетики - 1975, вып.ЗО. - С.263-267

7\7]Андреев А Е О синтезе самокорректирующихся управляющих систем.// Доклады

АН СССР. - 1984. - Т 277, N3. - С.521-5

*\8]Витляпцев И А О реализации систем конъюнкций контактными схемами // Дис-

кретная математика — 1989 - Т 1, вын 4 С 3-11

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

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

Научная новизна. Исследования, проведенные в данной работе, направлены па изучение средней временной сложности алгоритмов поиска. Они используют в качестве своей основы информационно-графовую модель данных, предложенную Э Э. Гасановым в работе [1]. Работы [9]9, [Ю]10, [II]11, [12]12 содержат результаты исследований интервального поиска на прямой и на плоскости: также в работе [1] одна глава посвящена исследованию задачи интервального поиска в п-мерном евклидовом пространстве Но методы и алгоритмы, предложенные в этих работах, пи коим образом не могут быть использованы для задачи интервального поиска на булевом кубе В работе [13]13 введено понятие задачи интервального поиска на булевом кубе и ис следовапо поведение функции Шеннона в классе древовидных схем в случае, когда нет ограничений на базовое множество функций, то есть разрешает-

"ЩГасанив Э Э Некоторые задачи поиска, допускающие мгновенное в среднем решение // Фундаментальная и прикладная математика. 1995. Т. 1, Лг° 1. С.123-146

,0[10] Гасанов Э Э Об одномерной задаче интервального поиска //Дискретная математика - 1995 Т7, Л"« 2. С.40-60.

и[11) Гасанов Э Э. Мгновенно решаемые задачи поиска.// Дискретная математика. — 1996. Т 8, К" 3 - С 119-134.

12[12|Гасанов 9 Э., Кузнецова И В О функциональной сложности двумерной задачи интервального поиска // Дискретная математика 2002 Т 14, N° 1

13{И]Гасанов Э Э О сложности информационного поиска Диссертация на соискание степени к ф -м н — Москва, 1985

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

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

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

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

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

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

Основные результаты диссертации, выносимые на защиту. В работе исследуется следующая задача информационного поиска Имеется некоторое подмножество V п-мерного булева куба называемое библиотекой. На булевом кубе берется произвольный интервал (и,ги), где у = (их,..., ип), ги — (ги\,. ., то,,) и и < и). Требуется перечислить все такие элементы у Е V. у — (ух,..., уп), называемые записями, для которых выполнено

Приведем интерпретацию данной задачи

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

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

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

»Задачу можно решать, если на каждом шаге алгоритма проверять условие UJ < У] € {1. • • • для фиксированного набора компонент записи

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

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

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

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

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

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

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

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

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

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

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

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

Если X — множество символов запросов с заданным на нем вероятностным пространством {X, а, Р), где а — алгебра подмножеств множества X, Р - вероятностная мера на а\ У — множество символов данных (записей); р -бинарное отношение на X х У, называемое отношением поиска; то пятерка 5 = (X, У, р, гт, Р) называется типом Тройка I = (X, V, р), где V некоторое конечное подмножество множества У, называемое библиотекой, называется задачей информационного поиска (ЗИП) типа 5. Содержательно ЗИП I = (X, V, р) состоит в перечислении для произвольно взятого запроса х € X всех и точно тех записей у £ V, что хру. Если Т - суть множества символов одноместных предикатов, определенных на X, 3- называется базовым множеством и описывает множество элементарных операций, используемых при решении задачи информационного поиска

Над базовым множеством Т определяется понятие информационного графа (ИГ) В конечной многополюсной ориентированной сети выбирается вершина — полюс, называемая корнем. Остальные полюса называются листьями и им приписываются записи из У. Ребрам ИГ приписываются предикаты из множества Т Таким образом нагруженную многополюсную ориентированную сеть называют информационным графом над базовым множеством Т Затем определяется функционирование ИГ. Предикатное ребро проводит за-

прос х £ X если предикат ребра истинен на х\ ориентированная цепочка ребер проводит х, если каждое ребро цепочки проводит х; запрос х проходит в вершину /3 ИГ, если существует ориентированная цепь, ведущая из корпя в вершину ¡3, которая проводит х; запись у, приписанная листу а попадает в ответ ИГ на х, если х проходит в лист а Ответом ИГ II на запрос х называют множество записей, попавших в ответ II на х, и обозначают его Л(х) Эту функцию «7у(х) считают результатом функционирования ИГ [7

ИГ II разрешает ЗИП I — (X, V, р), если ¿/и(х) = {у € V : хру}.

Вводится сложность ИГ. Предикат <рр{х) истинный на х. если х проходит в вершину ¡3, и ложный в противном случае, называется функцией фильтра вершины /3 Пусть 7 : Т —> И — функция весов функций из базового множества Сложностью ИГ II па запросе х £ X для функции весов 7 называется число Ту{11, х) = ^детг^р(х)12ее£0 т(/с), где 7? — множество вершин ИГ и, — множество ребер ИГ Г/, исходящих из вершины /3, /е — предикат, являющий нагрузкой ребра е. В случае, когда 7(/) = 1, мы будем опускать значок 7, и в этом случае Т(Г/, г) — ^¡¡¿цф^ ' Фр количество

ребер, исходящих из вершины /9 Эта величина равна числу функций, вычисленных алгоритмом поиска, определяемым ИГ Г/, на запросе х Везде далее будем считать, что если значок функции весов опущен, то она равна тождественной единице

Если каждая функция из Т измерима (относительно алгебры сг), то для любого ИГ и над Т функция х) измерима.

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

Если / предикат на множестве X, то М]{х) = {х е X : /(х) = 1}.

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

= (1) Реи е€£а

Сложностью ребра, исходящего из вершины /3 назовем число Р{Ыч>0{х)) ■ 7(/Р), где /е - предикат, приписанный ребру е Согласно (1), сложность ИГ

равна сумме сложностей ребер

Рассмотрим следующую ЗИП. Имеется некоторое ^-элементное подмножество п-мерного булева куба V € В% (библиотека). На булевом кубе задан некоторый интервал (и, т), где и = (и\,..., ип), ю = {гю\,..., «;„), и и < ю, то есть иг < Уг = 1,... ,7г. Требуется определить все элементы у е V, удовлетворяющие условию и <у

Очевидно, что если и, = 1 для некоторого г, то и = 1, а, следовательно, и у, = 1. Аналогично, если ыг = 0, то и уг = 0. Таким образом, вышеописанная ЗИП сводится к следующей: есть библиотека V е В", \У\ — к, берем запрос х = (х\,..., хп)- трехзначный вектор, компоненты которого могут быть равны либо 1, либо 0, либо 2- если м, = 1, то ж, = 1, если ги1 — 0, то х, = 0, иначе х, = 2. Для данного запроса х = (ц,.. , хп) хотим найти все У = (Уь • ■ • ,Уп) 6 V, для которых уг — хи если хг — 1 или хг = 0, и уг любое из {0,1}, если Хг = 2.

Получаем тип задач Эп =< В%, В™, р,сг, Р >, где и трехзначный и двузначный (булев) кубы, соответственно, р : хру о- (хг = уг) V (хг = 2), о - множество подмножеств В", и Р равномерная вероятностная мера на В", то есть для любого х е В^ Р(х) = 3~".

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

Пусть X множество переменных {х\, ..., хп}. Упорядоченное множество 11 = {Хь ..., Хт} будем называть разбиением множества X, если Х,ПХ; = 0 для г ф г, ] = 1,..., т, и Ц=Г Хг = X.

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

х, если (у — 1)&(ж ф 2) х, если (у = 0)&(а; ф 2) , ^ 1, если (у = 2)У (х- 2)

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

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

= {<' & • р = 1,... ,п,<т, € {0,1}},

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

1) из каждой вершины г-го яруса вершин, г = 1,..., ш — 2, выходит точно 2'|Х*' ребер, и если Хг = {хн,____х1р}, то этим ребрам взаимно однозначно сопоставлены конъюнкции вида х**& ■ ■ ■ , где ег, 6 {0,1}, г = 1,...,р\

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

1-Сбалансированным деревом с характеристикой т будем называть сбалансированное дерево, такое, что если И = {X], .., Хт} - разбиение, задающее дерево, то |Х,| =■ 1 для любого г, то есть решающее дерево построено над базисом переменных

Т\ = {Х1,Х2,.-.ХП,Х1,Х2,..-ХП}-

Из каждой вершины тп-го яруса выходит не более 21х™' цепочек ребер, и им приписаны конъюнкции (различные для каждой пары цепочек ребер, исходящих из одной вершины) объединение которых по всем ребрам цепочки выглядит как х^к • • • где <т, 6 {0,1}, г = 1,..., q, и где Хт - {х.,ч,. ., xmJ.

Множество задач / =< B$,V,p > типа S„, где \V\ = к, обозначим через 1{п, к) Множество сбалансированных деревьев с характеристикой h, с к висячими вершинами, над базисом F обозначим Т>р(п, к, h).

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

1\l,F,h)= inf T\D).

D£VF(-n,k,h)

Сложностью задачи 7 Ç X(n, к) в классе сбалансированных (1-сбаланси-рованных) деревьев над базовым множеством F назовем

T[l,F) = miaT\l,F,h).

с <|>iituÂ

Сбалансированное ИД D, решающее задачу I в базисе ^/назовем оптимальным, если T\l, F) — 1\D). В силу конечности множества сбалансированных деревьев, решающих задачу типа < B",Brj:,p >, оптимальное дерево существует

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

Обозначим Ci = logi 2 log« f)'^2 3 и с2 = 2 (^)'°Е2 *.

Теорема 1 Для любой ЗИП I Ç J(п, к) выполняется

36 . _ . ..ь. , 34

Cljfc2-to82з Т(/,^0) < с2к2^3

Следствие 1 При п —> оо, к оо, / G 1(п. к) верно

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

1) к, —» оо при г —» оо,

2) для любой последовательности задач информационного поиска /, £ 1{п, кг) при 1 —^ оо Т(/„ ~ a^fc,2~,cв,3.

Обозначим сз = 11о§| 2 ^ |^ 3 и С4 = 9.

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

Сзкъ- з _ 6 _ з ^ < т(/1 ^ < з _ б _ з 0

Следствие 2 При п -»• оо, к -> оо, / £ Х(п, А;) верно

Теорема 4 Длл любого числа а € [сз, с^] существует подпоследовательность натурального ряда кг, для которой выпоянено 1) кг оо при г —оо,

для любой пос аедовательности задач информационного поиска 1г £ Х(п, А;г) при г —> оо Т(/,,^х) ~

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

Пусть £> — произвольное отношение на х Д" и -< В^, в > соответствующий ему тип задач информационного поиска. Положим

II, если хду = < „

I 0 иначе

Для ЗИП / =< V, й- >е 8АП1 7 = {у\...,ук} обозначим = {/?> •-■>/?}' где /еИ = /¿-(^У1) Для г = 1, ..,/с Обозначим через Г(/) сложность минимального ИГ, решающего ЗИП / £ 5е,„ над базисом переменных.

Утверждение 1 Пусть ЗИП I Е S£>ri, и пусть каждая функция из множество Fe(I) принимает значение, равное 1, не более чем на р набораj Тогда при п > log2(fcp) выполнено

Т(1) < 10

Пусть а ~ (ai,..., ап) Е R". На множестве Tq элементарных конъюнкций введем функцию весов такую, что конъюнкции длины i имеют вес а,. Для обозначения этой функции весов мы также будем использовать значок а.

Систему весов а ~ (a-¡,... ,о„) будем называть допустимой, если существует I Е Ujt=i к)-, такая что

Та(1,Т0)<Т(1,Ъ).

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

-К1-®')-

Теорема 6 Для любой ЗИПI С I(п, к), любой системы весов а = (ai,..., ап) при п оо, к -4 оо выполняется

Clifc2-iog23 „ 36 < Т°{1,Яо) < с4к2~ь^3 - 3 (!)"*- 6. Следствие 3 При п -> оо, к ->■ оо, / € 1{п, к), а Е Rn верно

Теорема 7 Для любого числа а Е [01,04], существуют подпоследовательность натурального ряда к, и система весов а = (ai,... ,ап), для которыг выполнено

1) к, —> оо при i оо,

2) для любой последовательности задач информационного поиска 1г Е 1(п, кг) при г —»■ оо Та(1г, J-о) ~ а ■ fct2_logi3.

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

L(n,k) — m ах min T(D).

iei(n,k) Devr(n,k)

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

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

1. Если к > 2"'1, то L(n, к) = 6 + к (|)n_I - 6;

2 Если к х 2п, то L{n, к) х t;

3. Если log2 log2 п = o(log2 к), то log2 L(n, к) ~ log2 | • log2 к.

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

Пусть V — {у1, ■ ■ ■ ,ук} является подмножеством булева куба В2 Через Sn обозначим множество «-перестановок. По упорядоченному множеству (у4,... ,у1к), то есть по множеству V и перестановке <7о = (¿i, . , ù) G >?ь по заданной перестановке чисел а — (ji,... ,jn) 6 Sn, задающей порядок координат, будем строить информационное дерево D, решающее задачу I =<

Обозначим через C(v,p,m) следующую операцию: из вершины v строим ориентированную от v цепочку ребер длины п — m, а всем ребрам цепочки последовательно (по ориентации) приписываем функции х^', 1=1, , п — то Листу (конечной вершине последнего ребра) приписываем запись ур

Определим индуктивно алгоритм с жестким порядком проверок

Базис индукции. Объявляем корнем дерева £> вершину V и выполняем операцию С(*,г1,0).

Индуктивный переход Пусть для множества записей {уц,..., у1?-1} построено дерево Д р £ {2,..., к} Запись уг" добавляем в О следующим образом.

Шаг 1. ./V — 1, устанавливаем текущей вершиной и — корень дерева £)

у"

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

то конец этого ребра делаем текущей вершиной V устонавливаем N = N + 1 и переходим к шагу 2. Иначе переход им к шагу 3 Шаг 3. Выполняем С(ь,1р, М).

Таким образом, по библиотеке, заданной перестановке координат и при заданном порядке элементов библиотеки получаем дерево £) = А1(У,ао,а).

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

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

Е(у, Ы) - выдает полную цепь с номером N. исходящую из вершины V.

У(у, N) - выдает конечную вершину полной цепи Е(у, М).

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

/(с) £ Т\ — нагрузка цепи с.

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

Х'МНВДППО-

с(иь^г) — цепь с начальной вершиной ь^ и конечной вершиной

Операция С (с, г) удаляет полную цепь с = т/г), добавляет новые вершины у' и у", добавляет цепи с\ = («1, г/), с2 = (и', «г), с! — (у1, и"). Цели С! соответствует нагрузка х, цепи с2 - Ахех(с)\х'(г,г) цепи с'

Г\хеУ{г)\х'(с,1) х- Первое ребро цепи сх получает номер, равный номеру цепи с, остальные ребра цепи с получают номер 1; все ребра цепи с2 получают номер, равный 1; первое ребро цепи с! получает номер 2, все остальные ребра — номер 1.

Операция ЛГЕ(у,{,Х) добавляет в вершину у цепь с номером первого ребра Ы(у) + 1, номерами остальных ребер, равными 1, и суммарной нагрузкой цепи Г\хех х ЛИГТУ У{%}, + 1) приписываем запись у1.

Для задачи I =< V, р >£ 1{п, к) и перестановки элементов библиотеки и = (¿х,..., г к) € 5'ь решающее дерево будем строить при помощи алгоритма первого пересечения А2(У, сг)

Алгоритм первого пересечения (А2(У,а)) Шаг 1 Добавить в множество вершин дерева корень и0. Выполнить ЫЕ(ьо,г1,У(1{)). Установить р — 2 Шаг 2. V = Уа. N — 1, У = У{гр)- Перейти к шагу 1 Шаг 3. Если Х'(Е(у, ЛГ),гр) = 0, то перейти к шагу 4. Иначе

перейти к шагу 5 Шаг 4. Если N < N(v}

установить N = N + 1, перейти к шагу 3

Иначе

выполнить МЕ(у,1р, У), Перейти к шагу 6. Шаг 5 Если Х'(Е(и, Лг), (Р) = Х{Е(и, И)), то

установить у = У {у, ЛГ), N = 1, У = У\Х{Е{у, И)), перейти к шагу 1.

Иначе выполнить С(Е(у, Л''), гр) и перейти к шагу 6 Шаг 6. Если р < к, то

установить р — р + 1 и перейти к шагу 2

Пусть V = {г/1,..., ук} является подмножеством булева куба Я". По упорядоченному множеству (у'1,... ,уч), то есть по множеству V и перестановке <т = (¿1,... ,4) £ будем строить информационное дерево Д решающее задачу / =< У,р> при помощи жадного алгоритма.

Жадный алгоритм (Л3(1/, и))

Шаг 1 Добавить в множество вершин дерева корень г>о, выполнить гь У'(г1)),

установить р — 2. Шаг 2. Установить ь = ьо, У — У(гР)- Перейти к шагу 3. Шаг 3 Установить I — тях^ецд(г,)} ЛГ)> ¿Р)| Перейти к шагу 4

Шаг 4. Если £ = 0, то

перейти к шагу 5.

иначе

перейти к шагу 6. Шаг 5 Выполнить гр, У), перейти к шагу 8

Шаг б Установить N = тт{п : \Х'(Е(ь, п), гр)| = перейти к шагу 7 Шаг 7 Если Х'(£(г/, Я), гр) -= Х{Е{у, ЛГ)), то

утановить у - У(ь, И), У = У\Х(Е(у, Л^)) и перейти к шагу 3

Иначе

выполнить С(Е(у, М),гр) и перейти к шагу 8. Шаг 8 Если р < к, то

установит р = р + 1 и перейти к шагу 2.

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

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

У\ и Уг и параметры (т\ £ Б а и ст2 ? такие что

Т(Л(УЬ(71)) > гшпТ{В{Уиа)) и ттТ{А{Уг,о)) < Т{В(Уъо2)).

Теорема 9 Алгоритмы А1 и А2 попарно несравнимы

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

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

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

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

Положим Т1(У) = МаТ(А1(У, а)), где а £ 5П. Положим Т1(п, к) = Му Т1(У), где V € В$ : |У| = к. Положим Т2(У) = М„Т{А2{У а)), где а £ Бк. Положим Т2(п, к) = Му Т2{У), где V £ В% : \У\ = к. Получены следующие результаты

Теорема 12 При п оо, к оо, к — о(2п), п = о{2к)

оевв

аевл

ттТ(А(У») < гтпТ(В(1»).

Теорема 13 При п оо, к оо, к = о(2"), п = о(2к)

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

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 Блайвас Т.Д. Функция Шеннона сложности интервального поиска на булевом кубе в классе деревьев.//Дискретная математика, в печати

Подписано в печать 21.09.2005 Формат 60x88 1/16. Объем 1.5 п.л. Тираж 75 экз. Заказ № 109 Отпечатано в ООО «Соцветие красок» 119992 г.Москва, Ленинские горы, д.1 Главное здание МГУ, к. 102

#1668 1

РНБ Русский фонд

2006-4 13542

Введение

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

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

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

Класс сбалансированных деревьев

1.1 Оптимальное решение над базисом элементарных конъюнкций

1.1.1 Построение оптимальных деревьев.

1.1.2 Порядок сложности сбалансированных деревьев

1.1.3 Асимптотики в классе сбалансированных схем

1.2 Оптимальное решение над базисом переменных.

1.2.1 Построение оптимальных сбалансированных деревьев

1.2.2 Порядок сложности в классе сбалансированных деревьев

1.2.3 Асимптотики в классе сбалансированных деревьев

1.2.4 Случай произвольного отношения поиска.

1.3 Случай взвешенных базисов.

1.3.1 Критерий допустимости системы весов.

1.3.2 Построение оптимального сбалансированного дерева

1.3.3 Порядок сложности оптимальных деревьев.

Функция Шеннона сложности в классе древовидных схем

2.1 Нижняя оценка.

2.2 Верхняя оценка.

2.3 Оценки функции Шеннона.

Алгоритмы построения решающих деревьев

3.1 Описание алгоритмов.

3.1.1 Алгоритм с жестким порядком проверок (А1)

3.1.2 Алгоритм первого пересечения (А2(У, а)).

3.1.3 Жадный алгоритм (ЛЗ(У,ег)).

3.1.4 Сравнительный анализ алгоритмов.

3.2 Средняя сложность алгоритма с жестким порядком проверок (Л1).

3.2.1 Вспомогательные утверждения.

3.2.2 Доказательство теоремы.

3.3 Средняя сложность алгоритма первого пересечения (А2)

3.3.1 Вспомогательные утверждения.

3.3.2 Доказательство теоремы.

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

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

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

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

Пусть задано некоторое упорядоченное множество X. На множестве Хп определим отношение частичного порядка следующим образом: если а, Ь € Хп, а = (а1,.,ап), Ь = {Ъ\ ,.,£>„), то будем писать а ■< Ь ("а предшествует Ь"), если а< < для любого г = 1,.,п. Если V С Хп, u,w € Хп, и X w, то задача интервального поиска в Хп заключается в перечислении всех тех элементов у из V, для которых верно и -<у -<w.

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

Исследованию задачи интервального поиска в Rn (в другом переводе с английского — регионального поиска) посвящено большое количество работ [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(log2 А:), но требует затрат по памяти порядка А:3 для двумерной задачи. Гасанов в работе [18] для n-мерной задачи предложил алгоритм, который при затратах памяти порядка А;2"-1 требует в среднем константное время, а в худшем случае решает задачу за время 0(log2 к). Чтобы уменьшить требуемую память в работе [36] Бентли и Маурером был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени. В работе Гасанова и Кузнецовой [20] предлагается модификация алгоритма Бентли-Маурера, решающего двумерную задачу интервального поиска. Эта модификация позволяет снизить исходное логарифмическое среднее время поиска до константного при сохранении логарифмического времени поиска в худшем случае. При этом этот алгоритм зависит от параметра, при вариации которого объем памяти, необходимый алгоритму, изменяется от 0(к3) до О (к log к), при этом среднее время поиска (без учета времени на перечисление ответа) изменяется от 0(1) до О (log к). В частности, для любого е > 0 при объеме памяти 0(к1+е) достигается среднее время поиска 0(1). С помощью метода дерева интервалов (или дерева регионов) Бентли и Шеймос [37] получили оценку времени поиска

О (log" А;) при затратах памяти О (A; log"-1 к), где п — размерность задачи интервального поиска. Уиллард [55] и Люкер [49] независимо предложили модификацию дерева интервалов, которая позволила снизить время поиска до O(log21 к) при тех же затратах памяти. Чазелле в [42] для двумерной задачи смог снизить затраты памяти до О (к log2 к/ log2 log2 к), но при этом возросла константа при логарифме в оценке времени. Во всех этих работах оценивается время поиска в худшем случае. И только Болоур описал метод хеширования [41], который он использовал вместо поиска по древовидным структурам в задаче интервального поиска. Применение этого метода позволило получить довольно быстрые в среднем решения задачи интервального поиска при условии, что область запросов находится в заранее определенных границах.

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

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

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

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

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

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

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

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

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

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

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

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

В работе исследуется следующая задача информационного поиска. Имеется некоторое подмножество V п-мерного булева куба В", называемое библиотекой. На булевом кубе берется произвольный интервал (и, го), где и = (щ,. .,и„), ю = . .,ш„) и и Ч и), то есть щ < и)х * = 1,. ,п. Требуется определить все такие элементы у € V, у = (у\,. .,уп), называемые записями, для которых выполнено и Ч у Ч ю.

Приведем интерпретацию данной задачи.

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

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

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

Задачу можно решать, если на каждом шаге алгоритма проверять условие и] < у^ < ] € {1,.,п} для фиксированного набора компонент записи.

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

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

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

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

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

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

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

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

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

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

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

1. Андреев А.Е. О синтезе самокорректирующихся управляющих систем. Доклады АН СССР, 1984, т.277, N3, стр.521-525

2. Андреев А.Е. Универсальный принцип самокорректирования. Математический сборник, 1985, т.127(169), N6, стр.147-172

3. Андреев А.Е. О синтезе топологических функциональных сетей. Препринт 1.259 ИПМех АН СССР и МГУ им. Ломоносова, 1985, 67 стр.

4. Андреев А.Е. Метод бесповторной редукции синтеза самокорректирующихся схем. Доклады АН СССР, 1985, том 283, N2, стр. 265-269

5. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. — М.: Мир, 1979

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

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

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

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

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

11. Вихлянцев И.А. О реализации систем конъюнкций контактными схемами. Дискретная математика, 1989, том 1, вып.4, стр.3-11

12. Вихлянцев И.А. О самокорректировании контактных разделительных схемам. Дискретная математика, 1990, том2, вып.1, стр.80-86

13. Гасанов Э. Э., Кудрявцев В.Б. Теория хранения и поиска информации. Москва, ФИЗМАТЛИТ, 2002

14. Гасанов Э.Э. О сложности информационного поиска, канд. дисс. Москва, 1985

15. Гасанов Э. Э. Некоторые задачи поиска, допускающие мгновенное в среднем решение. Фундаментальная и прикладная математика (1995) 1, JV* 1, 123-146.

16. Гасанов Э. Э. Об одномерной задаче интервального поиска. Дискретная математика (1995) 7, № 2, 40-60.

17. Гасанов Э. Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8, 3, 119-134.

18. Гасанов Э. Э., Кузнецова И. В. Оценки функциональной сложности двумерной задачи интервального поиска. Тезисы докладов XII Международной конференции "Проблемы теоретической кибернетики", Нижний Новгород, (17-22 мая 1999 г.), — 47.

19. Гасанов Э. Э., Кузнецова И. В. О функциональной сложности двумерной задачи интервального поиска. Дискретная математика (2002) 14, № 1.

20. Кнут Д. Искусство программирования для ЭВМ. том 3. Сортировка и поиск. — М.: Мир, 1979

21. Ли Д., Препарата Ф. Вычислительная геометрия. Обзор. // Кибернетический сборник, 1987, том 24, стр.5-96

22. Лупанов О.Б. О синтезе контактных схем. Доклады АН СССР, 1958, том 119, N1, стр.23-26

23. Мартин Дж. Организация баз данных в вычислительных системах. — М.: Мир, 1980

24. Нечипорук Э.И. О топологических принципах самокорректирования. Проблемы кибернетики, 1969, вып.21, стр.5-102

25. Нечипорук Э.И. О топологических принципах самокорректирования. Доклады АН СССР, 1968, том 179, N4, стр.786-789

26. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. — М.: Мир, 1989

27. Редькян Н.П. О реализации систем конъюнкций контактными схемами. Проблемы кибернетики, 1975, вып.ЗО, стр.263-267

28. Решетников В.Н. Алгебраическая теория информационного поиска // Программирование. 1979, N3, сгр.68-74

29. Селтон Г. Автоматическая обработка, хранение и поиск информации. — М.: Советское радио, 1973

30. Химия и жизнь — XXI век. №4, 1998 г, Геном человека, стр. 27-30

31. Яблонский С. В., Лупанов О. Б. Дискретная математика и математические вопросы кибернетики, том 1, Москва, Наука, 1974

32. Bentley J. L. Multidimensional binary search trees used for associative searching. Commun. Ass. Comput. Mach. (Sept. 1975), 18 509-517.

33. Bentley J. L. Decomposable searching problems, Info. Proc. Lett. (1979), 8 244-251.

34. Bentley J. L., Friedman J. H. Data structures for range searching. Comput. Surveys (1979), 11 397-409.

35. Bentley J. L., Maurer H. A. Efficient worst-case data structures for range searching. Acta Inform. (1980), 13 155-168.

36. Bentley J. L., Shamos M. I. A problem in multivariate statistics: Algorithms, data structure and applications. Proc. 15th Allerton Conf. Commun., Contr., Comput. (1977), 193-201.

37. Bentley J. L., Stanat D. F. Analysis of range searching in quad trees. Inform. Processing Lett. (1975), 3 170-173.

38. Bentley J.L., Saxe J.B. Decomposable searching problems. I. Static-to-dynamic transformation. J. Algorithms, 1980, 1, P.301-358

39. Blaivas T. 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

40. Bolour A. Optimal retrieval algorithms for small region queries. SI AM J. Comput. (1981) 10, 721-741.

41. Chazelle В. M. Filtering search: a new approach to query-answering. Proc. 24th IEEE Annu. Symp. Found. Comput. Sci. (Nov. 1983), 122-132.

42. Fredman M. L. A lower bound of the complexity of ortogonal range queries. J. ACM. (1981) 28, 696-705.

43. Gabow H. N., Bentley J. L., Tarjan R. E. Scaling and related techniques for geometry problems. Proc. 16th ACM Annu. Symp. Theory Comput. (Apr. 1984) 135-143.

44. Lauter U. 4-dimensional binary search trees as a means to speed up associative searches in design verification of integrated circuits. Jour, of Design Automation and Fault Tolerant Computing, 2 (3), 241-247 (July 1978).

45. Lee D. T., Wong C. K. Worst case analysis for region and partial region searches in multidimensional binary search trees and balansed quad trees. Acta Informatica (1977) 9 23-29.

46. Lee D. T., Wong C. K. Quintari trees: A file structures for multidimensional database system. ACM Trans. Database Syst. (Sept. 1980) 1, JY* 1, 339-353.

47. Loftsgaarden D. O., Queensberry C. P. A nonparametric density function. Ann. Math. Stat. (1965) 36, 1049-1051.

48. Lueker G. S. A data structure for ortogonal range queries. Processing of the 19th Annual IEEE Symposium on Foundations of Computer Science. (1978), 28-34.

49. Lueker G. S., Willard D. E. A data structure for dynamic range queries. Inform. Processing Lett. (Dec. 1982) 15, № 5, 209-213.

50. Preparata F.P., Shamos M.J. Computational Geometry. Springer- Verlag. New-York, 1985

51. Saxe J. B. On the number of range queries in ¿-space. Discrete Applied Mathematics (1979) 1, 217-225.

52. Saxe J.B., Bentley J.L. Transforming static data structures into dynamic structures. Proc 20th IEEE Annu. Symp. Found. Comput. Sci., oct. 1980, P.148-168

53. Shannon C.E. The synthesis of two-terminal switching circuits. Bell SysLTechn. J., 1949, v.28, N1, P.59-98

54. Willard D. E. Predicate-oriented database search algorithms. Ph. D. dissertation, Harvard Univ., Cambridge, MA, 1978.