НЕФТЬ-ГАЗ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

Теперь на нашем сайте можно за 5 минут создать свежий реферат или доклад

Скачать книгу целиком можно на сайте: www.nglib.ru.

<< Теория информации <<

Гасанов Э.Э. Теория хранения и поиска информации

Скачать книгу здесь
Автор: Гасанов Э.Э.
Название: Теория хранения и поиска информации
Год издания: 2002
УДК: 519.71
Число страниц: 288
Содержание книги:
Введение
Глава 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. О недревовидности оптимальных ИГ включающего поиска 97 3.2.3.0 древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей
3.2.4. Нижняя оценка сложности включающего поиска
3.2.5. Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ
3.2.6. Оценки сложности одного метода решения задачи включающего поиска
3.2.7. Оценки В-сложности включающего поиска
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.2. Случай простого базового множества
4.1.3. Базовое множество логарифмического поиска
4.1.4. Базовое множество сверхлогарифмического поиска
4.1.5. Мгновенное решение
4.2. Многомерная задача интервального поиска
4.2.1. Мгновенное решение многомерной задачи интервального поиска
4.2.3. Оценки В-сложности задачи интервального поиска
4.3.1. Формулировка результата
4.3.2. Неформальное описание алгоритма
4.3.3. Построение информационного графа
4.3.4. Допустимость информационного графа
4.3.5. Объем информационного графа
4.3.6. Сложность информационного графа
Глава 5. Свойство канонического эффекта
5.1. Понятие канонического эффекта
5.2. Неустойчивость канонического эффекта по отношению к базовому множеству
5.3. Неустойчивость канонического эффекта по отношению к объему памяти
5.4. Устойчивость канонического эффекта по отношению к е-расширению запроса
Литература
Предметный указатель
Предметный указатель Introductuon 1. Information-graph database model 1.1. Notion of information graph (IG 1.2. Admissibility criterion for IG 1.3. Completeness for IG 1.4. Complexity of IG 1.5. Power lower bound 1.6. Examination optimality case 1.7. Basic problems 2. Search problems with short answer 2.1. Some properties of search problems with short answer 2.1.1. Existence of tree-like optimal IG for search problems with short answer 2.1.2. Lower bound for complexity of IG for search problems with short answer 2.1.3. Lower bound for B-complexity of IG for search problems with short answer 2.1.4. Lemmas on reduction 2.2. Searching for identical objects 2.2.1. Binary searching 2.2.3. Constant, in the worst case, algorithm to search for identical objects 2.3. Problems on closeness 2.3.1. Binary searching 2.3.2. Constant, in average, algorithm 2.3.3. Constant, in worst case, algorithm 3. Search problems over partially ordered data bases 3.1. Search problems over finite partially ordered sets of data 3.2. Search problems on Boolean cube 3.2.1. Inclusive search 3.2.2. On non-optimality of tree-like IG for inclusive search 3.2.3. On optimality of tree-like IG for inclusive search in nonrecurrent case 3.2.4. Lower bound for the complexity of inclusive search 3.2.5. Lower bound for the complexity of inclusive search in class of tree-like IG 3.2.6. Estimates of complexity of method to solve problem of inclusive search 3.2.7. Estimates of B-complexity of inclusive search 3.3. Search problems over linearly ordered sets of data 3.3.1. Serial algorithms to solve search problem with linear quasi-order search relation 3.3.2. Modelling of searching in multiprocessor system 3.3.3. Parallel algorithms to solve search problem with linear quasi-order search relation 3.4. Domination problem 3.4.1. Serial algorithms to solve domination problem 3.4.2. Estimates of B-complexity of domination problem 3.4.3. Mathematical model of background search algorithms 3.4.4. Background algorithm to solve two-dimensional domination problem 4. Range searching problems 4.1. One-dimensional range searching 4.1.1. Case of base set of characteristic functions 4.1.2. Case of simple base set 4.1.3. Base set of logarithmic searching 4.1.4. Base set of superlogarithmic searching 4.1.5. Instantly solution 4.2. Multidimensional range searching 4.2.1. Instantly solution for multidimensional range searching 4.2.2. Exapmle of estimate of spesial boundedness constant 4.2.3. Estimates of B-complexity of range searching 4.3.1. Formulation of result 4.3.2. Informal algorithm description 4.3.3. Construction of IG 4.3.4. Admissibility of IG 4.3.5. Volume of IG 4.3.6. Complexity of IG 5. Canonical effect property 5.1. Notion of canonical effect 5.2. Instability of canonical effect relatively to base set 5.3. Instability of canonical effect relatively to memory volume Bibliography
Subject index
Глоссарий:
7 8 а б в г д е ж з и к л м н о п р с т у ф х ц ч ш э я
Смотреть страницы:
1 3 32 60 88 116 144 172 200 228 256 284 287 288
Полнотекстовый поиск по книге:
Введите слово или фразу для поиска:
Близкие по содержанию книги:
Прикладные задачи теории графов
Математика >> Вычислительная математика >> Теория графов
Применение теории графов в программировании
Математика >> Вычислительная математика >> Теория графов
Теория графов
Математика >> Вычислительная математика >> Теория графов

Просмотреть оригинальные страницы книг в формате djvu можно на сайте: www.nglib.ru.


Главный редактор проекта: Мавлютов Р.Р.
oglib@mail.ru