Сложность поиска в случайных базах данных

Кучеренко, Наталья Сергеевна

Сложность поиска в случайных базах данных тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Кучеренко, Наталья Сергеевна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2010 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

Диссертация по математике на тему «Сложность поиска в случайных базах данных»

Автореферат диссертации на тему "Сложность поиска в случайных базах данных"

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.В. ЛОМОНОСОВА МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

:и

00461*»*

Кучеренко Наталья Сергеевна

СЛОЖНОСТЬ ПОИСКА В СЛУЧАЙНЫХ БАЗАХ ДАННЫХ 01.01.09 — дискретная математика и математическая кибернетика

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

МОСКВА - 2010

1 1 НОЯ 2010

г,

004612550

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

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

профессор Гасанов Эльяр Эльдарович

Официальные оппоненты: доктор физико-математических наук,

профессор Зубков Андрей Михайлович

кандидат физико-математических наук, доцент Применко Эдуард Андреевич

Ведущая организация: Российский Государственный Гуманитарный

Защита диссертации состоится 26 ноября 2010 г. в 16 ч. 45 мин. на заседании диссертационного совета Д.501.001.84 при Московском государственном университете имени М. В. Ломоносова по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д. 1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в библиотеке Механико-математического факультета МГУ М. В. Ломоносова (Главное здание, 14 этаж).

Автореферат разослан 26 октября 2010 г.

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

Университет (РГГУ)

Д.501.001.84 при МГУ,

доктор физико-математических наук,

профессор

А. О. Иванов

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

Актуальность темы

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

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

Более формально задачу поиска по ключу можно описать следующим образом2. Имеется некоторое множество объектов У, на котором введен линейный порядок. Данные — это конечное подмножество V, V С Y. Множество V далее будет называться также библиотекой. Множество запросов X совпадает с множеством У. Требуется по произвольному запросу из множества X найти в библиотеке V объект равный запросу, если такого объекта нет —указать в какой промежуток между данными попал запрос. Полагается, что для решения этой задачи можно сравнивать любые два объекта из множеств X и Y.

Рассматривается случай, когда множества X и Y представляют собой интервал (0,1) и база данных — статическая, то есть библиотека V фиксирована. Предполагается, что к статической базе данных происходит многократное обращение с запросами на поиск по ключу, поэтому при ее проектировании

1 Кнут Д. Э. Искусство программирования. Издательский дом "Вильяме", Москва, 2000, Т. 3.

2 Гасаиов Э. Э., Кудрявцев В. Б. Теория храпения и поиска информации. Флзматлит, Москва, 2002.

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

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

В пятидесятые годы двадцатого века возникла идея представлять алгоритмы для задачи поиска по ключу с помощью деревьев. В 1959 году Э. Н. Гильберт и Э. Ф. Мур показали, что можно построить оптимальное дерево поиска за 0(п3) шагов (тг —мощность библиотеки), и привели оценки сложности такого дерева поиска3. Оптимальным называлось дерево поиска, имеющее минимальную сложность среди всех деревьев. В 1971 году Д. Э. Кнут показал, что построение оптимального дерева поиска можно улучшить до порядка 0(п2) шагов4. Дальнейшие упрощения методов построения были произведены в 1977 A.M. Гарсия и М. J1. Вочем5. Их метод позволяет построить оптимальное дерево поиска за 0(п • log2 п) шагов.

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

Любую задачу поиска по ключу можно решить с помощью информационного графа, реализующего бинарный поиск, со сложностью равной лога-

3 Gilbort E.N, Moore E.F., Variable-length binary encodings. Bell System Tech. J., — 1959. 38, — 933-988.

4 Knuth D.E., Optimum binary search trees. Acta Informatica, — 1971. 1, — 14-25.

5 Garsia A.M., Wachs M.L., A new algorithm for minimum cost binary trees. SICOMP, — 1977. 4, — 622- 642.

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

Цель работы

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

Основные методы исследования

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

Научная новизна

Результаты работы являются новыми и состоят в следующем.

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

2. Рассмотрено поведение сложности оптимального ИГ для двух «равномерных» библиотек. В первом случае библиотека представляет собой равномерную сетку на интервале (0,1), во втором случае библиотека — случайный равномерно распределенный вектор, и запросы также распределены равномерно. В первом случае установлено, что сложность оптимального ИГ имеет асимптотику двоичного логарифма от мощности библиотеки п. Во втором случае показано, что средняя сложность оптимального ИГ также имеет асимптотику \ctg2 п, п —> оо, и получена нижняя оценка средней сложности оптимального ИГ, которая отличается от 1о§2 п на константу.

3. Исследовано поведение средней сложности оптимального ИГ в случае, когда распределение данных и запросов может быть отлично от равномерного. Распределение данных задается функцией плотности д, а распределение запросов — функцией плотности /. При слабых ограничениях на / и д доказана нижняя оценка средней сложности оптимального ИГ. Получены условия для / и д, при которых средняя сложность оптимального ИГ имеет порядок логарифма от мощности библиотеки. Уточнены эти условия до получения асимптотики такой сложности.

4. Рассмотрены случаи, когда средняя сложность оптимального информационного графа является ограниченной функцией при увеличении мощности библиотеки. Показано, что для любого отрезка вида [Ь, Ь + 2], Ь G М, 6 > 1, можно построить такие функции плотности распределения запросов / и данных д, для которых средняя сложность оптимального ИГ не выходит за пределы отрезка при увеличении мощности библиотеки.

5. Рассмотрены случаи, когда средняя сложность оптимального ИГ является неограниченно возрастающей функцией по порядку меньшей, чем логарифм. Описано семейство S возможных асимптотик и семейство S* возможных порядков функций роста, которые являются неограниченно возрастающими, но по порядку меньшими, чем логарифм от мощности библиотеки.

Теоретическая и практическая ценность

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

Апробация работы

Результаты диссертации неоднократно докладывались на семинарах механико-математического факультета МГУ им. М. В. Ломоносова: на семинаре «Вопросы сложности алгоритмов поиска» под руководством профессора Э.Э. Гасанова (2006-2009 гг.), на семинаре «Теория автоматов» под руководством академика В. В. Кудрявцева (2007-2009 гг.).

Они докладывались также на следующих конференциях: IX международная конференция «Интеллектуальные системы и компьютерные пауки» (Москва, 2006 г.), IX международный семинар «Дискретная математика и се приложения», посвященный 75-летию со дня рождения академика О. Б. Лупа-нова (Москва, 2007 г.), международная конференция студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2007 г., 2008 г., 2009 г.), международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В. А. Садовни-чего (Москва, 2009 г.), X Международный семинар «Дискретная математика и ее приложения» (Москва, 2010 г.), научная конференция «Ломоносовские чтения» (Москва, 2007 г., 2008 г., 2010 г.).

Публикации

Основные результаты диссертации опубликованы в 6 работах автора, список которых приведен в конце автореферата [1-6].

Структура и объем диссертации

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

Краткое содержание работы

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

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

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

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

В разделе 1.1 для задачи поиска по ключу приводится два способа ее формализации — задача поиска идентичных объектов на интервале (0,1) и расширенная задача поиска идентичных объектов на интервале (0,1).

Задача поиска идентичных объектов на интервале (0,1) формализуется как четверка ((0,1), V, р=, /(ж)), где (0,1) — множество запросов. Конечный набор V точек интервала (0,1), V = (У\,У2, •.. ,уп), элементы которого упорядочены по возрастанию и не равны между собой, называется библиотекой, а элементы библиотеки — записями. Отношение поиска р= - это отношение равенства на множестве (0,1) х (0,1). Предполагается, что запрос х является случайной величиной, принимающей значения из интервала (0,1). Распределение запросов задается функцией плотности /. Отношение задает функцию ответов 3{х), определенную на множестве запросов (0,1), следующим образом

0, иначе.

Расширенная задача поиска идентичных объектов (РЗПИО) на интервале (0,1) —это четверка ((0,1), V, ре, /(я)), где (0,1) —множество запросов.

{у;}, если Зг е [1..п] : уг = х,

Обозначим через У множество, состоящее из всех подиптервалов и точек интервала (0,1). Конечный набор V' состоит из таких элементов множества У, что они представляют собой разбиение интервала (0,1) следующего вида

У = ((0,У1)ЛУ1}ЛУ\,У2),{У2}т ■■ ЛУП},(УПА)) , У\ < У2 < ■■■ < Уп-

Набор V' называется библиотекой, а элементы библиотеки —записями. Отношение поиска р€ — это отношение на множестве (0,1) х У. Запрос 1,16 (0,1), находится в отношении ре с элементом у множества У тогда и только тогда, когда х £ у. Запрос х является случайной величиной, принимающей значения из интервала (0,1). Распределение запросов задается функцией плотности /. Введем обозначения уо = О, Уп+1 = 1- Отношение ре задает функцию ответов ./'(а;), определенную на множестве запросов (0,1), следующим образом

{{&}, если Эг 6 [1..п] : уг = х, Щ, У-}+\), если 3] е [0..гг] : у^ < х <

Расширением ЗПИО I = ((0,1), V, f(x)), где V = (уиу2,.. .,уп), назовем РЗПИО V = ((0,1), V', р5} /(ж)), где

V' = ((0, ух), {г/1>, (ш, 2/2), {У2>, • - - ЛУп}ЛУП, 1)), У1 <У2 < ••■ <Уп-

Также в разделе дается определение информационного графа. Приведем содержательное описание этого определения. Информационный граф — это ориентированный граф, ребра и вершины которого нагружены элементами данных и функциями. Алгоритм поиска —это «волновой» процесс на графе, который управляется нагрузочными функциями. Нагрузочные функции разделены на два класса: предикаты и переключатели. Поскольку для операций сравнения выбрано представление в виде переключателей, в работе используется информационный граф, множество нагрузочных функций которого состоит только из класса переключателей. Информационный граф такого вида называется информационным графом с переключательной нагрузкой (ИГПН).

Множество ИГПН, которые решают задачу поиска I, обозначим через 5/. Рассмотрим информационный граф с переключательной нагрузкой из

множества 5/, где 7 —некоторая задача поиска. Сложностью ИГПН V на запросе х называется число переключательных вершин, которые достигаются запросом х при функционировании V. Сложностью ИГПН и из множества 5/ называется математическое ожидание величины Т(11,х), которое можно записать в виде

Т1(и) = М(Т(11,х)) =

Т{и,х)}{х)йх,

где /(х) — функция плотности распределения запросов в задаче поиска I.

Сложностью задачи поиска I называется величина

Т(7) = Ы ЩЩ.

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

В разделе 1.2 приводятся результаты главы и необходимые для их формулировки понятия. Вводится понятие древовидного ИГПН и определяется множество Дг, состоящее из древовидных ИГПН, решающих задачу поиска I и удовлетворяющих жестким требованиям к структуре.

В разделе 1.3 приводится доказательство результата о том, что для любой задачи поиска идентичных объектов I можно построить оптимальный ИГ принадлежащий множеству £)/.

Теорема 1. Для любой задачи поиска идентичных объектов I существует оптимальный информационный граф с переключательной нагрузкой, который содержится во множестве £>/.

Для расширенной задачи поиска идентичных объектов в разделе доказывается аналогичный результат. Однако он не выводится заново, а получается из теоремы 1 с помощью алгоритма преобразования ИГПН из множества £)/, где / — задача поиска идентичных объектов, в ИГПН из множества где РЗПИО /' — расширение I, и теоремы 3 о том, что сложности ЗПИО / и РЗПИО Г равны.

Теорема 2. Для любой задачи поиска идентичных объектов I и для любого информационного графа с переключательной нагрузкой U из множества D¡ верно, что после применения алгоритма преобразования к ИГПН U получается ИГПН U' из множества Dji, где РЗПИО I' —расширение задачи поиска идентичных объектов I. При этом сложность ИГПН U равна сложности получившегося ИГПН U'

T¡{U) — T¡>(U').

Теорема 3. Сложность любой задачи поиска идентичных объектов I и ее расширения I' равны

Т(1) = Т{Г).

В силу теоремы 3 сложность задачи поиска по ключу не зависит от выбора одного из двух способов формализации. Поэтому далее в работе исследуется более «простая» формализация в виде ЗПИО, и при необходимости даются пояснения как эти результаты перенести для РЗПИО.

В разделе 1.4 приводится алгоритм построения оптимального ИГПН, основанного на результатах, полученных в 1959 году Э. Н. Гильбертом и Э. Ф. Муром3. Под алгоритмом построения понимается условный алгоритм с операциями сложения и нахождения минимального для нар вещественных чисел. Сложность условного алгоритма — количество таких операций. Доказывается корректность алгоритма построения и показывается, что его сложность по порядку не больше куба от мощности библиотеки.

Теорема 4. Существует условный алгоритм, который для любой задачи поиска идентичных объектов

I = ((0,1), V, р=, /), К = {гМиу,2,..., yia],

строит оптимальный ИГПН из множества D¡. При этом сложность построения по порядку не больше п3, где п = \V\.

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

графа бинарного поиска и показывается, что для любой задачи поиска идентичных объектов I сложность ИГ бинарного поиска не больше ]log2(n + 1)[ н не меньше [log2(n + 1)], где п — мощность библиотеки задачи поиска. Алгоритм построения такого ИГ требует линейного от мощности библиотеки числа операций сложения, деления и взятия целой части над вещественными числами.

Теорема 5. Существует условный алгоритм, который для любой задачи поиска идентичных объектов

I = ((0,1), V,P=, /), V = {yh,yh,..

строит информационный граф бинарного поиска Ug из множества D[. При этом сложность построения по порядку не больше п, где п = \V\. Для построенного ИГПН 1)в верны следующие оценки

[log2(n + 1)] ^ Ti{Ub) «$] log2(n + 1)[.

В разделе 1.6 доказывается, что сложность любой задачи поиска не меньше единицы и не больше верхней оценки сложности ИГ бинарного поиска ] log2(n+ 1)[. При этом строится пример задачи поиска, для которой нижняя оценка достигается, и строится задача поиска со сложностью не меньше чем log2(n+ 1), где п — мощность библиотеки задачи поиска.

Теорема 6. Для сложности любой задачи поиска идентичных объектов 1= ((0,1), V,p=, /) верно

1 ^T(I) <]log2(n+l)[,

где п = |К|. При этом для любого п S N существуют задачи поиска идентичных объектов Гп = ((0,1), V', р=, /'), \V'\ = п, и = ((0,1), V", Р=, /")> W"\ ~ п> такие, что

т(о = 1, ад ^iog2(n+i).

В силу теоремы 6 сложность оптимального ИГПН может быть как логарифмом от мощности библиотеки, так и константой в зависимости от конкретной задачи поиска идентичных объектов. В следующих главах автором

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

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

В разделе 2.2 рассмотрены два «равномерных» класса задач поиска идентичных объектов. Библиотека первого класса задач представляет собой равномерную сетку на интервале (0,1), библиотека второго — вариационный ряд равномерно распределенных случайных величин.

Первый класс задач поиска обозначим через /,{

/,{ = ((0,1), К /), F = •., , n 6 N.

Автором получен следующий результат. Теорема 7. Для любой функции плотности распределения f(x)

T(#)~log2n (n — оо). При этом если функция плотности ограничена константой с, с > 0, то Т(1;0 > log2(n + 1) - log2 log2(n + 1) - 1 - с.

Библиотека V второго рассматриваемого в работе «равномерного» класса задач поиска представляет собой вектор

V = (У(1),У(2),- • • ,У(„)),

гДе У(i)> У(2)> ■ • •) У(п) — вариационный ряд, составленный из независимых равномерно распределенных на интервале (0,1) случайных величин У\,У2,---, Уп-

Обозначим через Tn(V) случайную величину, которая при реализации V вектора V равна сложности ЗПИО ((0,1), V, р=, х(0,1)), где функция плотности распределения запросов х(0,1) является функцией плотности равномерного распределения на интервале (0,1).

Автором показано, что для любого п, п £ N, математическое ожидание сложности оптимального ИГПН для равномерно распределенных запросов и

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

Теорема 8. Пусть Му(Т„(У)) — математическое ожидание Tn(V), тогда для любого hgN

] log2(n + М v(Tn(V)) > log2(n + 1) -

где in = l 7 -Inn.

Последовательность jn при n —► +oo — сходящаяся. Предел этой последовательности называется постоянной Эйлера 7, 7 = 0,57...

Разделы 2.3 и 2.4 посвящены классам задач поиска, для которых распределение данных и запросов может быть отлично от равномерного. Случайная библиотека У задается с помощью функции плотности g как вектор

V ={У{\),У(2),---,У{п)),

гЛе 2/(1) 1 У(2)> • • • 12/(n) ~ вариационный ряд, составленный из независимых случайных величин ?/1,..., у» с функцией плотности распределения д(х). Обозначим через Tn'g\v) случайную величину, которая при реализации У случайной библиотеки У, заданной с помощью функции плотности д, равна сложности ЗПИО ((0,1), У, р=, /), где / — функция плотности распределения запросов.

В разделе 2.3 изучается при каких условия на функции плотности / и д математическое ожидание величины имеет порядок логарифма

от мощности библиотеки.

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

Теорема 9. Пусть для функций плотности fug существует s, s G N, не пересекающихся интервалов (а,:, bi) С (0,1), г = 1,..., s, таких что

Уг, г = l,...,s, 36 : 12

Va; € (a,;, b{) e{ > f{x) > e\ > 0, fcj ^ 3(1) > hi, > 0. Тогда при n —> 00

] log2(n + M v(T^\V)) > £ u, • log2(l + r,n) - ^ ^ + О i-7/3

1=1 J=1 \

где Uj = vi = п = g(x) dx, i = 1,..., s.

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

Следствие 9.1. Если существует невырожденный интервал (а,Ь), на котором функции плотности / и g одновременно ограничены и отделены от нуля, то

Mv(TU«XV))x\og2n (я-00),

где п= \V\.

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

Обозначим носитель функции / через supp(f), supp(f) = {х G (0,1) : f(x) ф 0}. Назовем функцию плотности / функцией с конечно-интервальным носителем, если supp(f) имеет вид

supp(f) = U-=1(a.;, bi) Ü К, К С {оь ..., а,„ Ъи ..., Ь.,},

где ai < bi, bi < dj+i, Vi = 1... (s - 1), as < b„. Автором доказана следующая теорема

Теорема 10. Пусть функции плотности fug умеют конечно-интервальный носитель, ограничены и отделены от нуля на множестве supp(f) и supp(g) соответственно, и существует интервал, на котором функции отделены от нуля одновременно. Пусть такэюе функции fug интегрируемы по Риману. Тогда

Mv(T^(V))~\og2n

f(x)dx (п —» оо),

где В = supp(g).

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

В разделе 3.1 приводятся основные понятия и результаты главы.

Раздел 3.2 посвящен классам задач поиска идентичных объектов, для которых математическое ожидание сложности оптимального ИГПН при увеличении мощности случайной библиотеки п является ограниченной функцией. В работе автором показано существование таких функций плотности / и <7, что математическое ожидание сложности оптимального ИГПН Tn'9\v) является ограниченной функцией при п —> оо. При этом верна следующая теорема

Теорема 11. Для любого числа п' € N существуют функции плотности f и д' такие, что

Mv{T{J-!<'\V)) = 1. Для любого вещественного числа b, b > 1, существуют такие функции плотности f" и д", что

Зп0 <= N : Vn > по Ь + 2 > М ИГ/Л'^ОО) > Ь.

Раздел 3.3 посвящен классам задач поиска идентичных объектов для которых математическое ожидание сложности оптимального ИГПН является неограниченно возрастающей функцией по порядку меньшей, чем логарифм. Автором исследуются возможные асимптотики и порядки функций роста средней сложности поиска для таких классов задач.

Положительная, возрастающая функция г(х) называется сохраняющей асимптотику, если выполнено условие

Vc е К г(х + с) ~ г(х) (х оо).

Семейство S возможных асимптотик промежуточных функций роста состоит из функций вида r(log2log2(n)), где неограниченно возрастающая, положительная и дифференцируемая функция г(х), определенная на интервале

(хо,+оо),а:о ^ 0, сохраняет асимптотику и имеет в качестве производной монотонную, положительную и непрерывную функцию г'(х), удовлетворяющую условию:

_ г'(х)

За > 0, а S R : Ига < 1.

я->+00 Ха

Все функции из S являются неограниченно возрастающими и имеют порядок меньше чем log2n при п —> оо.

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

Теорема 12. Для любой функции r(log2 log2(n)) из семейства S существуют функции плотности fug такие, что для математического ожидания сложности оптимального ИГПН верно

М v{TU«\V)) ~ r(log2log2(n)) (п -» оо).

В качестве примера показано, что множество

{с • (log2... log2 n)a\i eN,ae R+, с G M+},

^ Ш У

¿+1

где К+ — множество положительных вещественных чисел, является подсемейством для 5.

Следствие 12.1. Для любого натурального i, для любых положительных и вещественных а и с существуют функции плотности fug такие, что

М v(T^\V)) ~ с • (log2... log2 п)а (п - со).

4 v-'

» + 1

Положительная, возрастающая функция г(х) называется сохраняющей порядок, если

Vc6R,c^0, г(с-х)хф) (ж-юо).

Семейство S* возможных порядков промежуточных функций роста состоит из функций вида r(log2(n)), где неограниченно возрастающая, положительная и дифференцируемая функция г(х), определенная на интервале (xq, +оо),

хо ^ 0, сохраняет порядок n имеет в качестве производной монотонную, положительную и непрерывную функцию г'(х), удовлетворяющую условию:

_ г'(х)

За eR,0 < а < 1 : lim -^-f ^ 1.

Х—+СО ха

Все функции из S* являются неограниченно возрастающими и имеют порядок меньше чем log2 п при п —» оо. В отличие от класса S, в классе S* есть функции по порядку большие чем любая функция из S, например (log2n)a, О < а < 1. Автором показано, что для функций семейства S* верна следующая теорема

Теорема 13. Для любой функции r(log2(n)) из семейства S* существуют функции плотности fug, такие что для математического ожидания сложности оптимального ИГПН Mv(T,¥'°\v)) верно

М v(T,[}'9]{V)) >i r(log2(n)) (n -» оо).

В качестве примера показано, что множество

{(log2n)a|0 <q<1,ü£ R},

является подсемейством для 5*.

Следствие 13.1. Для любого вещественного а, 0 < а < 1, существуют функции плотности fug, такие что

М viT^'^iV)) ж (log2 п)а (п -» оо).

Благодарности

Автор выражает благодарность своему научному руководителю профессору Гасанову Эльяру Эльдаровичу за постановку задачи и постоянное внимание к работе и академику Кудрявцеву Валерию Борисовичу за ценные советы и замечания.

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

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

[1] Кучеренко Н.С. Сложность поиска идентичных объектов в случайных базах данных. Интеллектуальные системы (2007) 11, № 1-4, с. 525-550.

[2] Кучеренко Н. С. О промежуточных функциях роста сложности поиска для случайных баз данных. Интеллектуальные системы (2009) 13, №1-4. с. 361-395.

[3] Кучеренко Н. С. О сложности поиска идентичных объектов для случайных баз данных. В кн.: Материалы IX Международной конференции "Интеллектуальные системы и компьютерные науки". Механико-математический факультет МГУ, Москва, 2006, Т. 1, с. 171.

[4] Кучеренко Н. С. Оценки сложности поиска идентичных объектов для случайных баз данных. В кн.: Материалы IX Международного семинара "Дискретная математика и ее приложения", посвященного 15-летию со дня рождения академика О. Б. Лупанова. Механико-математический факультет МГУ, Москва, 2007, с. 329-331.

[5] Кучеренко Н. С. О средней сложности поиска идентичных объектов для случайных баз данных. В кн.: Материалы международной конференции "Современные проблемы математики, механики и их приложений", посвялценная 70-лет,ию рект,ора МГУ академика В. А. Садовнгь-чего. Механико-математический факультет МГУ, Москва, 2009, с. 362.

[6] Кучеренко Н. С. Асимптотика промежуточных функций роста сложности поиска для случайных баз данных. В кн.: Материалы X Международного семинара "Дискретная математика и ее приложения". Механико-математический факультет МГУ, Москва, 2010. с. 373-375.

Заказ № 174-аЛ 0/10 Подписано в печать 25.10.2010 Тираж 100 экз. Усл. пл. 1

ООО "Цифровичок", тел. (495) 649-83-30 www.cfr.ru; е-таИ:'нф(а),с/г.г11

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Кучеренко, Наталья Сергеевна

Введение

Глава 1. Оптимальный информационный граф с переключательной нагрузкой

1.1. Формализация задачи поиска. Понятие информационного графа с переключательной нагрузкой (графа переключателей)

1.2. Основные понятия и результаты главы.

1.3. Структура оптимального графа переключателей

1.4. Алгоритм построения оптимального графа переключателей

1.5. Алгоритм построения графа переключателей бинарного поиска

1.6. Универсальные оценки сложности оптимального графа переключателей

Глава 2. Классы задач поиска с логарифмической средней сложностью оптимального графа переключателей.

2.1. Основные понятия и результаты главы.

2.2. Классы задач поиска для равномерно распределенных данных

2.3. Нижняя оценка средней сложности оптимального графа переключателей

2.4. Классы задач поиска с известной асимптотикой средней сложности оптимального графа переключателей.

Глава 3. Классы задач поиска с не логарифмической средней сложностью оптимального графа переключателей.

3.1. Основные понятия и результаты главы.

3.2. Классы задач поиска с ограниченной средней сложностью оптимального графа переключателей.

3.3. Классы задач поиска с неограниченной средней сложностью оптимального графа переключателей.

Введение диссертация по математике, на тему "Сложность поиска в случайных базах данных"

Актуальность темы

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

Более формально задачу поиска по ключу можно описать следующим образом [9]. Имеется некоторое множество объектов У, на котором введен линейный порядок. Данные — это конечное подмножество V, V С У. Множество V далее будет называться также библиотекой. Множество запросов X совпадает с множеством У. Требуется по произвольному запросу из множества X найти в библиотеке V объект, равный запросу, если такого объекта нет — указать в какой промежуток между данными попал запрос. Полагается, что для решения этой задачи можно сравнивать любые два объекта из множеств X и У.

Рассматривается случай, когда множества X и У представляют собой интервал (0,1), и база данных — статическая, то есть библиотека V фиксирована. Предполагается, что к статической базе данных происходит многократное обращение с запросами на поиск по ключу, поэтому при ее проектировании внимание акцентируется на организации данных и алгоритме поиска, минимизирующих среднее время поиска.

В данной работе задача поиска по ключу исследуется с позиции информационно-графовой модели данных [9]. В этой модели структура данных задается управляющей системой — информационным графом (ИГ), который представляет собой ориентированный граф, ребра и вершины которого нагружены элементами данных и функциями. Алгоритм поиска —это "волновой" процесс на графе, который управляется нагрузочными функциями. Под сложностью информационного графа понимается среднее время поиска. Информационный граф, на котором достигается минимум сложности, называется оптимальным.

В пятидесятые годы двадцатого века возникла идея представлять алгоритмы для задачи поиска по ключу с помощью деревьев. В 1959 году Э. Н. Гильберт и Э. Ф. Мур показали, что можно построить оптимальное дерево поиска за 0(п3) шагов (п — мощность библиотеки), и привели оценки сложности такого дерева поиска [22]. Оптимальным называлось дерево поиска, имеющее минимальную сложность среди всех деревьев. В 1971 году Д. Э. Кнут показал, что построение оптимального дерева поиска можно улучшить до порядка 0(п2) шагов [21]. Дальнейшие упрощения методов построения были произведены в 1977 А. М. Гарсия и М. Л. Вочем [23]. Их метод позволяет построить оптимальное дерево поиска за 0(п • п) шагов.

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

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

Цель работы

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

Научная новизна

Результаты работы являются новыми и состоят в следующем.

2. Рассмотрено поведение сложности оптимального ИГ для двух «равномерных» библиотек. В первом случае библиотека представляет собой равномерную сетку на интервале (0,1), во втором случае библиотека — случайный равномерно распределенный вектор, и запросы также распределены равномерно. В первом случае установлено, что сложность оптимального ИГ имеет асимптотику двоичного логарифма от мощности библиотеки п. Во втором случае показано, что средняя сложность оптимального ИГ также имеет асимптотику log2 п, п —> оо, и получена нижняя оценка средней сложности оптимального ИГ, которая отличается от log2 п на константу.

4. Рассмотрены случаи, когда средняя сложность оптимального информационного графа является ограниченной функцией при увеличении мощности библиотеки. Показано, что для любого отрезка вида [Ь, 6 + 2], Ь е К, Ь > 1, можно построить такие функции плотности распределения запросов / и данных д, для которых средняя сложность оптимального ИГ не выходит за пределы отрезка при увеличении мощности библиотеки.

5. Рассмотрены случаи, когда средняя сложность оптимального ИГ является неограниченно возрастающей функцией по порядку меньшей логарифма от мощности библиотеки. Описано семейство 5 возможных асимптотик и семейство 5* возможных порядков функций роста, которые являются неограниченно возрастающими функциями по порядку меньше логарифма.

Методы исследования

Теоретическая и практическая ценность

Апробация работы

Гасанова (2006-2009 гг.), на семинаре «Теория автоматов» под руководством академика В. Б. Кудрявцева (2007-2009 гг.).

Они докладывались также на следующих конференциях: IX международная конференция «Интеллектуальные системы и компьютерные науки» (Москва, 2006 г.), IX международный семинар «Дискретная математика и ее приложения», посвященный 75-летию со дня рождения академика О. Б. Лупа-нова (Москва, 2007 г.), международная конференция студентов, аспирантов и молодых ученых «Ломоносов» (Москва, 2007 г., 2008 г., 2009 г.), международная конференция «Современные проблемы математики, механики и их приложений», посвященная 70-летию ректора МГУ академика В. А. Садовни-чего (Москва, 2009 г.), X Международный семинар «Дискретная математика и ее приложения» (Москва, 2010 г.), научная конференция «Ломоносовские чтения» (Москва, 2007 г., 2008 г., 2010 г.).

Структура и объем работы