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

М.: Физматлит, 2002. — 288 с. — ISBN: 5-9221-0235-4.Вводится новый вид представления баз данных, называемый информационно-графовой моделью данных, обобщающий известные ранее модели. Рассматриваются основные типы задач поиска информации в базах данных и исследуются проблемы сложности решения этих задач применительно к информационно-графовой модели. Разработан математический аппарат решения этих задач, основанный на методах теории сложности управляющих систем, теории вероятностей, а также на оригинальных методах характеристических носителей графа, оптимальной декомпозиции и снижения размерности.
Для математиков, специалистов в области кибернетики и информатики и инженеров как научная монография и новый технологический аппарат, а также как учебное пособие для студентов и аспирантов, специализирующихся в области математической кибернетики, дискретной математики и математической информатики.Оглавление
Введение
Информационно-графовая модель данных
Понятие информационного графа (ИГ)
Критерий допустимости ИГ
Полнота для информационных графов
Сложность информационных графов
Мощностная нижняя оценка
Случай оптимальности перебора
Основные задачи
Задачи поиска с коротким ответом
Некоторые свойства задач поиска с коротким ответом
Существование древовидного оптимального ИГ для задач поиска с коротким ответом
Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей
Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом
Леммы о сведении
Поиск идентичных объектов
Бинарный поиск
Константный в среднем алгоритм поиска
Константный в худшем случае алгоритм поиска
Оценки памяти константного в худшем случае алгоритма поиска
Задачи о близости
Бинарный поиск
Константный в среднем алгоритм поиска
Константный в худшем случае алгоритм поиска
Задачи поиска на частично-упорядоченных множествах данных
Задачи поиска на конечных частично-упорядоченных множествах данных
Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных
Включающий поиск
О недревовидности оптимальных ИГ включающего поиска
О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей
Нижняя оценка сложности включающего поиска
Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ
Оценки сложности одного метода решения задачи включающего поиска
Оценки В-сложности включающего поиска
Задачи поиска на линейно-упорядоченных множествах данных
Последовательные алгоритмы решения задачи поиска с отношением поиска вида линейного предпорядка
Моделирование поиска в системах с несколькими вычислителями
Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка
Задачи поиска на декартовых произведениях линейно-упорядоченных множеств данных (задача о доминировании)
Последовательные алгоритмы решения задачи о доминировании
Оценки В-сложности задачи о доминировании
Математическая модель фоновых алгоритмов поиска
Фоновый алгоритм решения двумерной задачи о доминировании
Задачи интервального поиска
Одномерная задача интервального поиска
Случай базового множества характеристических функций.
Случай простого базового множества
Базовое множество логарифмического поиска
Базовое множество сверхлогарифмического поиска
Мгновенное решение
Многомерная задача интервального поиска
Мгновенное решение многомерной задачи интервального поиска
Пример оценки константы специальной ограниченности
Оценки В-сложности задачи интервального поиска
Оценки сложности двумерной задачи интервального поиска
Формулировка результата
Неформальное описание алгоритма
Построение информационного графа
Допустимость информационного графа
Объем информационного графа
Сложность информационного графа
Свойство канонического эффекта
Понятие канонического эффекта
Неустойчивость канонического эффекта по отношению к базовому множеству
Неустойчивость канонического эффекта по отношению к объему памяти
Устойчивость канонического эффекта по отношению к е-расширению запроса
е-расширение задачи поиска идентичных объектов
е-расширение задач о доминировании и интервального поиска
Литература
Предметный указатель