Наталья сергеевна сложность поиска в случайных базах данных

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

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

АВТОРЕФЕРАТ

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

МОСКВА — 2010

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

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

Официальные оппоненты: доктор физико-математических наук, профессор Зубков Андрей Михайлович кандидат физико-математических наук, доцент Применко Эдуард Андреевич

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

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

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

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

Ученый секретарь диссертационного совета Д.501.001.84 при МГУ, доктор физико-математических наук, профессор А. О. Иванов

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

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

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

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

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

Рассматривается случай, когда множества и представляют собой ин­ тервал (0, 1) и база данных — статическая, то есть библиотека фиксирова­ на. Предполагается, что к статической базе данных происходит многократное обращение с запросами на поиск по ключу, поэтому при ее проектировании Кнут Д. Э. Искусство программирования. Издательский дом “Вильямс”, Москва, 2000, Т. 3.

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

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

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

В пятидесятые годы двадцатого века возникла идея представлять алго­ ритмы для задачи поиска по ключу с помощью деревьев. В 1959 году Э. Н.

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

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

Любую задачу поиска по ключу можно решить с помощью информаци­ онного графа, реализующего бинарный поиск, со сложностью равной лога­ Gilbert E. N, Moore E. F., Variable-length binary encodings. Bell System Tech. J., — 1959. 38, — 933–968.

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

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

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

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

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

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

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

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

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

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

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

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

Апробация работы Результаты диссертации неоднократно докладывались на семинарах ме­ ханико-математического факультета МГУ им. М. В. Ломоносова: на семинаре «Вопросы сложности алгоритмов поиска» под руководством профессора Э. Э.

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

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

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

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

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

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

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

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

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

Задача поиска идентичных объектов на интервале (0, 1) формализуется как четверка ((0, 1),, =, ()), где (0, 1) — множество запросов. Конечный набор точек интервала (0, 1), = (1, 2,..., ), элементы которого упо­ рядочены по возрастанию и не равны между собой, называется библиотекой, а элементы библиотеки — записями. Отношение поиска = – это отношение равенства на множестве (0, 1) (0, 1). Предполагается, что запрос является случайной величиной, принимающей значения из интервала (0, 1). Распреде­ ление запросов задается функцией плотности. Отношение = задает функ­ цию ответов (), определенную на множестве запросов (0, 1), следующим образом { }, если [1..] : =, () = иначе.

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

Обозначим через множество, состоящее из всех подинтервалов и точек ин­ тервала (0, 1). Конечный набор состоит из таких элементов множества, что они представляют собой разбиение интервала (0, 1) следующего вида = ((0, 1 ), {1 }, (1, 2 ), {2 },..., { }, (, 1)), 1 2 · · ·.

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

Введем обозначения 0 = 0, +1 = 1. Отношение задает функцию ответов (), определенную на множестве запросов (0, 1), следующим образом { }, если [1..] : =, () = (, +1 ), если [0..] : +1.

Расширением ЗПИО = ((0, 1),, =, ()), где = (1, 2,..., ), назовем РЗПИО = ((0, 1),,, ()), где = ((0, 1 ), {1 }, (1, 2 ), {2 },..., { }, (, 1)), 1 2 · · ·.

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

Множество ИГПН, которые решают задачу поиска, обозначим через. Рассмотрим информационный граф с переключательной нагрузкой из множества, где — некоторая задача поиска. Сложностью ИГПН на запросе называется число переключательных вершин, которые достигаются запросом при функционировании. Сложностью ИГПН из множества называется математическое ожидание величины (, ), которое можно записать в виде ( ) = M ( (, )) = (, ) (), где () — функция плотности распределения запросов в задаче поиска.

Сложностью задачи поиска называется величина () = inf ( ).

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

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

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

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

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

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

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

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

В разделе 1.4 приводится алгоритм построения оптимального ИГПН, основанного на результатах, полученных в 1959 году Э. Н. Гильбертом и Э. Ф.

Муром3. Под алгоритмом построения понимается условный алгоритм с опера­ циями сложения и нахождения минимального для пар вещественных чисел.

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

Теорема 4. Существует условный алгоритм, который для любой задачи поиска идентичных объектов = ((0, 1),, =, ), = {1, 2,..., }, строит оптимальный ИГПН из множества. При этом сложность по­ строения по порядку не больше 3, где = | |.

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

Теорема 5. Существует условный алгоритм, который для любой задачи поиска идентичных объектов = ((0, 1),, =, ), = {1, 2,..., }, строит информационный граф бинарного поиска из множества. При этом сложность построения по порядку не больше, где = | |. Для построенного ИГПН верны следующие оценки [log2 ( + 1)] ( ) ] log2 ( + 1)[.

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

Теорема 6. Для сложности любой задачи поиска идентичных объектов = ((0, 1),, =, ) верно 1 () ] log2 ( + 1)[, где = | |. При этом для любого N существуют задачи поиска иден­ тичных объектов = ((0, 1),, =, ), | | =, и = ((0, 1),, =, ), | | =, такие, что ( ) = 1, ( ) log2 ( + 1).

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

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

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

Первый класс задач поиска обозначим через ( ) 1 2, N.

= ((0, 1),, =, ), =,,..., + 1 + 1 + Автором получен следующий результат.

Теорема 7. Для любой функции плотности распределения () ( ) log2 ( ).

При этом если функция плотности ограничена константой, 0, то ( ) log2 ( + 1) log2 log2 ( + 1) 1.

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

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

Автором показано, что для любого, N, математическое ожидание сложности оптимального ИГПН для равномерно распределенных запросов и для случайной библиотеки, являющейся вариационным рядом равномерно распределенных случайных величин, незначительно отличается от сложности логарифмического поиска, а именно верны следующие оценки Теорема 8. Пусть M ( ( )) — математическое ожидание ( ), тогда для любого N 1 + log2 ( + 1) ] log2 ( + 1)[ M ( ( )), ln ln.

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

Разделы 2.3 и 2.4 посвящены классам задач поиска, для которых рас­ пределение данных и запросов может быть отлично от равномерного. Слу­ чайная библиотека задается с помощью функции плотности как вектор = ((1), (2),..., () ), где (1), (2),..., () — вариационный ряд, составленный из независимых слу­ чайных величин 1,..., с функцией плотности распределения (). Обозна­ (,) чим через ( ) случайную величину, которая при реализации случай­ ной библиотеки, заданной с помощью функции плотности, равна слож­ ности ЗПИО ((0, 1),, =, ), где — функция плотности распределения запросов.

В разделе 2.3 изучается при каких условия на функции плотности (,) и математическое ожидание величины ( ) имеет порядок логарифма от мощности библиотеки.

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

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

(, ) 0, () 1 () 2 0.

1 Тогда при ( ) (,) · log2 (1 + ) ] log2 ( + 1)[ M ( ( )) +, 1/ =1 = · · где =, =, = (), = 1,...,.

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

Следствие 9.1. Если существует невырожденный интервал (, ), на ко­ тором функции плотности и одновременно ограничены и отделены от нуля, то (,) M ( ( )) log2 ( ), где = | |.

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

Обозначим носитель функции через ( ), ( ) = { (0, 1) :

() = 0}. Назовем функцию плотности функцией с конечно-интерваль­ ным носителем, если ( ) имеет вид ( ) = (, ), {1,...,, 1,..., }, = где, +1, = 1... ( 1),.

Автором доказана следующая теорема Теорема 10. Пусть функции плотности и имеют конечно-интерваль­ ный носитель, ограничены и отделены от нуля на множестве ( ) и () соответственно, и существует интервал, на котором функции от­ делены от нуля одновременно. Пусть также функции и интегрируемы по Риману. Тогда (,) M ( ( )) log2 · () ( ), где = ().

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

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

Раздел 3.2 посвящен классам задач поиска идентичных объектов, для которых математическое ожидание сложности оптимального ИГПН при уве­ личении мощности случайной библиотеки является ограниченной функци­ ей. В работе автором показано существование таких функций плотности (,) и, что математическое ожидание сложноcти оптимального ИГПН ( ) является ограниченной функцией при. При этом верна следующая теорема Теорема 11. Для любого числа N существуют функции плотности и такие, что (, ) M ( ( )) = 1.

Для любого вещественного числа, 1, существуют такие функции плотности и, что, ) ( 0 N : 0 + 2 M ( ( )).

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

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

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

() 0, R : lim 1.

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

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

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

В качестве примера показано, что множество { · (log2... log2 ) | N, R+, R+ }, + где R+ — множество положительных вещественных чисел, является подсемей­ ством для.

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

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

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

() R, 0 1 : lim 1.

+ Все функции из * являются неограниченно возрастающими и имеют поря­ док меньше чем log2 при. В отличие от класса, в классе * есть функции по порядку большие чем любая функция из, например (log2 ), 0 1. Автором показано, что для функций семейства * верна следую­ щая теорема Теорема 13. Для любой функции (log2 ()) из семейства * существуют функции плотности и, такие что для математического ожидания (,) сложности оптимального ИГПН M ( ( )) верно (,) M ( ( )) (log2 ()) ( ).

В качестве примера показано, что множество {(log2 ) |0 1, R}, является подсемейством для *.

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

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

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

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

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

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

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

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

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