Перейти к полному списку специальных курсов кафедры

Теория баз данных и информационного поиска

Целью спецкурса является описание подхода к исследованию сложностных характеристик алгоритмов поиска с помощью методов теории управляющих систем.

В спецкурсе рассматриваются наиболее популярные задачи поиска, возникающие в базах данных, и приводятся как традиционные, так и оригинальные алгоритмы решения этих задач. Особенностью курса является исследование такой традиционно сложной характеристики поиска, как "среднее" время поиска. Описываются быстрые в "среднем" алгоритмы решения задач поиска.

Это оригинальный спецкурс, большинство результатов которого приводилось ранее только в научных статьях автора.

Примерный список вопросов по спецкурсу:

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

Литература:

1. Ахо А.,  Хопкрофт  Дж.,  Ульман  Дж. Построение   и   анализ вычислительных алгоритмов. Мир,  Москва, 1979.
2. Гасанов Э.Э. Об одной математической модели информационного поиска. Дискретная математика (1991) 3, N 2, 69–76.
3. Гасанов Э.Э. Об одномерной задаче интервального поиска. Дискретная математика (1995) 7, N 2, 40–60.
4. Гасанов Э.Э. Мгновенно решаемые задачи поиска. Дискретная математика (1996) 8, N 3, 119–134.
5. Гасанов Э.Э. Нижняя  оценка  сложности  информационных  сетей для одного отношения частичного порядка. Дискретная математика (1996) 8, N 4, 108–122.
6. Гасанов Э.Э. Функционально-сетевые базы данных и сверхбыстрые алгоритмы поиска. Изд. центр РГГУ, Москва, 1997.
7. Гасанов Э.Э., Мхитарова Т.В. Об одной математической модели фоновых алгоритмов поиска и быстрый фоновый алгоритм двумерной задачи о доминировании. Фундаментальная и прикладная математика (1997) 3, N 3, 759–773.
8. Гасанов Э.Э. Нижняя оценка сложности включающего поиска в классе древовидных схем. Дискретная математика (1998) 10, N 1, 63–72.
9. Гасанов Э.Э. Информационно-графовая модель хранения и поиска данных. Интеллектуальные системы (1998) 3, N 3–4, 163–192.
10. Гасанов Э.Э., Луговская Ю.П. Константный в худшем случае алгоритм поиска идентичных объектов. Дискретная математика (1999) 11, N 4, 139–144.
11. Ершов А.П. О программировании арифметических операторов. ДАН СССР  (1958) 118, 427–430.
12. Кнут Д. Искусство программирования для ЭВМ. Сортировка и поиск. т. 3, Мир, Москва, 1978.
13. Ли Д., Препарата Ф. Вычислительная  геометрия.  Обзор. Кибернетический сб. (1987) 24, 5–96.
14. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. Мир, Москва, 1989.

Наверх