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

Короткий опис

Гасанов, Эльяр Эльдарович.
Оптимальное решение базовых задач хранения и поиска в информационно-графовой модели данных : диссертация ... доктора физико-математических наук : 01.01.09. - Москва, 1999. - 368 с. : ил.
Оглавление диссертациидоктор физико-математических наук Гасанов, Эльяр Эльдарович
Введение
1 Информационный граф (ИГ) как управляющая система, моделирующая алгоритмы хранения и поиска информации
1.1 Задачи хранения и поиска в базах данных.
1.2 Понятие информационного графа.
1.3 Критерий допустимости ИГ.
1.4 Полнота для информационных графов.
1.5 Сложность информационных графов.
1.6 Мощностная нижняя оценка.
1.7 Случай оптимальности перебора
2 Задачи информационного поиска с коротким ответом
2.1 Задачи поиска с коротким ответом.
2.1.1 Существование древовидного оптимального ИГ для задач поиска с коротким ответом.
2.1.2 Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей.
2.1.3 Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом.
2.1.4 Леммы о сведении.
2.2 Поиск идентичных объектов.
2.2.1 Бинарный поиск.
2.2.2 Константный в среднем алгоритм поиска
2.2.3 Константный в худшем случае алгоритм поиска
2.2.4 Оценки памяти константного в худшем случае алгоритма поиска.
2.3 Задачи о близости.
ОГЛАВЛЕНИЕ
2.3.1 Бинарный поиск.
2.3.2 Константный в среднем алгоритм поиска
2.3.3 Константный в худшем случае алгоритм поиск а
3 Задачи поиска на частично-упорядоченных множествах данных
3.1 Задачи поиска на конечных частично-унорядоченных множествах данных.
3.2 Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных
3.2.1 Включающий поиск.
3.2.2 О недревовидности оптимальных ИГ включающего поиска.
3.2.3 О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей
3.2.4 Нижняя оценка сложности включающего поиска
3.2.5 Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ
3.2.6 Оценки сложности одного метода решения задачи включающего поиска.
3.2.7 Оценки B-сложности включающего поиска
3.3 Задачи поиска на линейно-упорядоченных множествах данных.
3.3.1 Последовательные алгоритмы решения задачи поиска с отношением поиска вида линейного предпорядка
3.3.2 Моделирование поиска в системах с несколькими вычислителями.
3.3.3 Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка
3.4 Задачи поиска на декартовых произведениях линейноупорядоченных множеств данных (задача о доминировании)
3.4.1 Последовательные алгоритмы решения задачи о доминировании.
ОГЛАВЛЕНИЕ
3.4.2 Оценки В-сложности задачи о доминировании
3.4.3 Математическая модель фоновых алгоритмов поиска
3.4.4 Фоновый алгоритм решения двумерной задачи о доминировании.
4 Задача поиска на евклидовом параллелепипеде при запросах вида его подпараллелепипедов (интервальный поиск)
4.1 Одномерная задача интервального поиска
4.1.1 Случай базового множества характеристических функций
4.1.2 Случай простого базового множества.
4.1.3 Базовое множество логарифмического поиска
4.1.4 Базовое множество сверхлогарифмического поиска
4.1.5 Мгновенное решение
4.2 Многомерная задача интервального поиска.
4.2.1 Мгновенное решение многомерной задачи интервального поиска
4.2.2 Пример оценки константы специальной ограниченности
4.2.3 Оценки В-сложности задачи интервального поиска
5 Об устойчивости канонического эффекта информационно-графовой модели хранения и поиска данных
5.1 Понятие канонического эффекта.
5.2 Неустойчивость канонического эффекта по отношению к базовому множеству.
5.3 Неустойчивость канонического эффекта по отношению к объему памяти.
5.4 Устойчивость канонического эффекта по отношению к ^-расширению запроса
5.4.1 е-расширение задачи поиска идентичных объектов
ОГЛАВЛЕНИЕ
5.4.2 £-расширение задач о доминировании и интервального поиска