Теория хранения и поиска информации
- Раздел 1. Понятие информационного графа (ИГ)
- Раздел 2. Критерий допустимости ИГ
- Раздел 3. Полнота для информационных графов
- Раздел 4. Сложность информационных графов
- Раздел 5. Мощностная нижняя оценка
- Раздел 6. Случай оптимальности перебора
- Раздел 7. Некоторые свойства задач поиска с коротким ответом
- Тема 1. Существование древовидного оптимального ИГ для задач поиска с коротким ответом
- Тема 2. Нижняя оценка сложности ИГ для задач поиска с коротким ответом и равномощными тенями записей
- Тема 3. Нижняя оценка В-сложности ИГ для задач поиска с коротким ответом
- Тема 4. Леммы о сведении
- Раздел 8. Поиск идентичных объектов
- Тема 1. Бинарный поиск
- Тема 2. Константный в среднем алгоритм поиска
- Тема 3. Константный в худшем случае алгоритм поиска
- Тема 4. Оценки памяти константного в худшем случае алгоритма поиска
- Раздел 9. Задачи о близости
- Тема 1. Бинарный поиск
- Тема 2. Константный в среднем алгоритм поиска
- Тема 3. Константный в худшем случае алгоритм поиска
- Раздел 10. Задачи поиска на декартовых произведениях бинарных частично-упорядоченных множеств данных
- Тема 1. Включающий поиск
- Тема 2. О недревовидности оптимальных ИГ включающего поиска
- Тема 3. О древовидности оптимальных ИГ включающего поиска в классе бесповторных сетей
- Тема 4. Нижняя оценка сложности включающего поиска
- Тема 5. Нижняя оценка сложности включающего поиска для базового множества переменных в классе бесповторных или древовидных ИГ
- Тема 6. Оценки сложности одного метода решения задачи включающего поиска
- Тема 7. Оценки В-сложности включающего поиска
- Раздел 11. Задачи поиска на линейно-упорядоченных множествах данных
- Тема 1. Последовательные алгоритмы решения задачи поиска с отношением поиска вида линейного предпорядка
- Тема 2. Моделирование поиска в системах с несколькими вычислителями
- Тема 3. Параллельное решение задачи поиска с отношением поиска вида линейного предпорядка
- Раздел 12. Задачи поиска на декартовых произведениях линейно-упорядоченных множеств данных (задача о доминировании)
- Тема 1. Последовательные алгоритмы решения задачи о доминировании
- Тема 2. Оценки В-сложности задачи о доминировании
- Тема 3. Математическая модель фоновых алгоритмов поиска
- Тема 4. Фоновый алгоритм решения двумерной задачи о доминировании
- Раздел 13. Одномерная задача интервального поиска
- Тема 1. Случаи базового множества характеристических функции
- Тема 2. Случаи простого базового множества.
- Тема 3. Базовое множество логарифмического поиска
- Тема 4. Базовое множество сверхлогарифмического поиска
- Тема 5. Мгновенное решение
- Раздел 14. Многомерная задача интервального поиска
- Тема 1. Мгновенное решение многомерной задачи интервального поиска
- Тема 2. Пример оценки константы специальной ограниченности
- Тема 3. Оценки В-сложности задачи интервального поиска
- Раздел 15. Оценки сложности двумерной задачи интервального поиска
- Тема 1. Формулировка результата
- Тема 2. Неформальное описание алгоритма
- Тема 3. Построение информационного графа
- Тема 4. Допустимость информационного графа
- Тема 5. Объем информационного графа
- Тема 6. Сложность информационного графа
- Раздел 16. Понятие канонического эффекта
- Раздел 17. Неустойчивость канонического эффекта по отношению к базовому множеству
- Раздел 18. Устойчивость канонического эффекта по отношению к ε-расширению запроса
- Тема 1. ε-расширение задачи поиска идентичных объектов
- Тема 2. ε-расширение задач о доминировании и интервального поиска