Документ взят из кэша поисковой машины. Адрес оригинального документа : http://new.math.msu.su/content_root/programs/kaf/special/matis/teorbd.doc Дата изменения: Mon Nov 10 08:55:22 2008 Дата индексирования: Sun Apr 10 03:00:21 2016 Кодировка: koi8-r

ТЕОРИЯ БАЗ ДАННЫХ И ИНФОРМАЦИОННОГО ПОИСКА

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