ИНТЕЛЛЕКТУАЛЬНЫЕ СИСТЕМЫ. ТЕОРИЯ ХРАНЕНИЯ И ПОИСКА ИНФОРМАЦИИ
ИНФОРМАЦИОННО-ГРАФОВАЯ МОДЕЛЬ ДАННЫХ Понятие информационного графа (ИГ) Критерий допустимости ИГ Полнота для информационных графов Сложность информационных графов Мощностная нижняя оценка Случай оптимальности перебора Основные задачи ЗАДАЧИ ПОИСКА С КОРОТКИМ ОТВЕТОМ Некоторые свойства задач поиска с коротким ответом Существование древовидного оптимального ИГ для задач поиска с коротким ответом. Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей. Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом. Леммы о сведении. Поиск идентичных объектов Бинарный поиск. Константный в среднем алгоритм поиска. Константный в худшем случае алгоритм поиска. Оценки памяти константного в худшем случае алгоритма поиска. Задачи о близости Бинарный поиск. Константный в среднем алгоритм поиска. Константный в худшем случае алгоритм поиска. ЗАДАЧИ ПОИСКА НА ЧАСТИЧНО-УПОРЯДОЧЕННЫХ МНОЖЕСТВАХ ДАННЫХ Задачи поиска на конечных частично-упорядоченных множествах данных Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных Включающий поиск. О древовидности оптимальных ИГ включающего поиска. О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей. Нижняя оценка сложности включающего поиска. Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесновторных или древовидных Оценки сложности одного метода решения задачи включающего поиска. Оценки В-сложности включающего поиска. Задачи поиска на линейно-упорядоченных множествах данных Последовательные алгоритмы решения задачи поиска с отношением поиска вида линейного предпорядка. Моделирование поиска в системах с несколькими вычислителями. Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка. Задачи поиска на декартовых произведениях линейно-упорядоченных множеств данных (задача о доминировании) Последовательные алгоритмы решения задачи о доминировании. Оценки В-сложности задачи о доминировании. Математическая модель фоновых алгоритмов поиска. Фоновый алгоритм решения двумерной задачи о доминировании. ЗАДАЧИ ИНТЕРВАЛЬНОГО ПОИСКА Одномерная задача интервального поиска Случай базового множества характеристических функций. Случай простого базового множества. Базовое множество логарифмического поиска. Базовое множество сверхлогарифмического поиска. Мгновенное решение. Многомерная задача интервального поиска Мгновенное решение многомерной задачи интервального поиска. Пример оценки константы специальной ограниченности. Оценки В-сложпости задачи интервального поиска. Оценки сложности двумерной задачи интервального поиска Формулировка результата. Неформальное описание алгоритма. Построение информационного графа. Допустимость информационного графа. Объем информационного графа. Сложность информационного графа. СВОЙСТВО КАНОНИЧЕСКОГО ЭФФЕКТА Понятие канонического эффекта Неустойчивость канонического эффекта по отношению к базовому множеству Неустойчивость канонического эффекта по отношению к объему памяти Устойчивость канонического эффекта по отношению к е-расширению запроса е-расширение задачи поиска идентичных объектов. е-расширение задач о доминировании и интервального поиска.Предметный указатель
