Читать онлайн «Теория сложности информационного поиска»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Э. Э. Гасанов Теория сложности информационного поиска Mocква 2005 год  Э. Э. Гасанов Теория сложности информационного поиска Учебное пособие написано на основе специальных курсов "Тео- рия баз данных и информационного поиска" и "Теория интеллек- туальных систем", читаемых на кафедре математической теории ин- теллектуальных систем механико-математического факультета МГУ им. М. В. Ломоносова. В книге вводится новый вид представления баз данных, называемый информационно-графовой моделью данных, об- общающий известные ранее модели данных. Рассматриваются основ- ные типы задач поиска информации в базах данных и исследуются проблемы сложности решения этих задач применительно к информа- ционно-графовой модели. Приводятся алгоритмы решения рассмат- риваемых задач поиска близкие к оптимальным. Для студентов, аспирантов, специализирующихся в области мате- матической кибернетики, дискретной математики и математической информатики. Рецензент — доктор физико-математических наук, академик, профессор В. Б. Кудрявцев. Механико-математический c факуль- тет МГУ, 2005 г. Оглавление Введение 5 1 Информационно-графовая модель данных 11 1. 1 Понятие информационного графа (ИГ) . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1. 2 Критерий допустимости ИГ . . . . . . . . . . . . . 31 1. 3 Полнота для информационных графов . . . . . . . 35 1. 4 Сложность информационных графов . . . . . . . . . . . . . . . . . . . . . . . . . 38 1. 5 Мощностная нижняя оценка . . . . . . . . . . . . . 46 1. 6 Случай оптимальности перебора . . . . . . . . . . 49 1. 7 Основные задачи . . . . . . . . . . . . . . . . . . . 50 2 Задачи поиска с коротким ответом 52 2. 1 Некоторые свойства задач поиска с коротким от- ветом . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2. 2 Существование древовидного оптимального ИГ для задач поиска с коротким ответом . . . . . . . . . 53 2. 3 Нижняя оценка сложности ИГ для задач поиска c коротким ответом и равномощными тенями записей 60 3 Поиск идентичных объектов 68 3. 1 Бинарный поиск . . . . . . . . . . . . . . . . . . . . 70 3. 2 Константный в среднем алгоритм поиска . . . . . 73 3. 3 Константный в худшем случае алгоритм поиска . 80 3. 4 Оценки памяти константного в худшем случае ал- горитма поиска . . . . . . . . . . . . . . . . . . . . 81 3 4 Включающий поиск 88 4. 1 Задачи поиска на конечных частично-упорядочен- ных множествах данных . . . . . . . . . . . . . . . 88 4. 2 Включающий поиск . . . . . . . . . . . . . . . . . . 91 4. 3 Нижняя оценка сложности включающего поиска . 95 4. 4 Верхняя оценка сложности включающего поиска . 102 4. 5 Асимптотика функции Шеннона сложности включающего поиска . . . . . . . . . . 104 4. 6 Асимптотика функции Шеннона включающего поиска в классе древовидных ИГ . 105 5 Одномерный интервальный поиск 111 5. 1 Случай базового множества характеристических функций . . . . . . . . . . . . . . . . . . . . . . . . 113 5. 2 Случай простого базового множества . . . . . . . . 113 5. 3 Базовое множество логарифмического поиска . . . 121 5. 4 Базовое множество сверхлогарифмического поиска 126 5. 5 Мгновенное решение . . . . . . . . . . . . . . . . . 131 Литература 138 4 Введение В последние десятилетия активно развивается новое науч- ное направление, связанное с оптимальным хранением и поис- ком информации, именуемое теорией информационного поиска.