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

• Автор: Кучеренко, Наталья Сергеевна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2010
• Место защиты: Москва
• Количество страниц: 179 с.

Содержание
Введение
Глава 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 далее будет называться также библиотекой. Множество запросов X совпадает с множеством У. Требуется по произвольному запросу из множества X найти в библиотеке V объект, равный запросу, если такого объекта нет — указать в какой промежуток между данными попал запрос. Полагается, что для решения этой задачи можно сравнивать любые два объекта из множеств X и У.
Рассматривается случай, когда множества X и У представляют собой интервал (0,1), и база данных — статическая, то есть библиотека V фиксирова-

Покажем, что при переходе от информационного графа и' к информационному графу сложность не увеличилась. Для этого нам понадобится следующая лемма. Рассмотрим произвольную задачу поиска I и информационный граф Г, Г Є 5/. Пусть и переключательная вершина Г. Вероятностью достижения вершины и назовем вероятность множества запросов, которые при функционировании Г достигают вершины и. Вероятность достижения вершины у обозначим через Р (и).
Лемма 3. Для любой задачи поиска идентичных объектов I сложность ИГПН Г, Г Є можно представить в виде
где Р — множество переключательных вершин ИГПН Г.
Доказательство леммы 3. Сложность информационного графа Т(Г) — это математическое ожидание сложности Г на запросе Т(Г, х)
где Р — множество переключательных вершин, а <ру(х) — предикат, принимающий значение единица, если х проходит в вершину V. и нуль в противном случае. Предикат ру(х) называется функцией фильтра вершипыи. Выражая сложность через функцию фильтра, получаем
ї7(г) = Ерм.
т7( Г) = М Т(Г, х).
Сложность на запросе — это величина
Т(Г,х) = ^(я),