|
Перейти к полному списку специальных курсов кафедры
Теория баз данных
Вопросы по курсу, 2008 г.
1.
Информационно-графовая модель данных.
2.
Критерий допустимости информационных графов (ИГ).
3.
Критерий полноты базового множества.
4.
Сложность информационных графов.
5.
Теорема о существовании оптимальных ИГ.
6.
Мощностная нижняя оценка.
7.
Случай оптимальности перебора.
8.
Задача поиска идентичных объектов. Константный в среднем
алгоритм поиска идентичных объектов.
9.
Оценки памяти константного в худшем случае алгоритма
поиска идентичных объектов.
10. Задачи поиска с коротким ответом. Древовидность оптимальных
информационных графов для задач поиска с коротким ответом.
11. Нижняя оценка сложности задач поиска с коротким ответом в случае
равновероятных теней записей.
12. Одномерная задача интервального поиска.
13. Линейный по памяти непереборный алгоритм решения двумерной задачи
интервального поиска.
14. Задача включающего поиска. Нижняя оценка сложности включающего поиска.
15. Асимптотика функции Шеннона сложности включающего поиска.
16. Нижняя оценка сложности включающего поиска в классе древовидных схем.
17. Асимптотика функции Шеннона сложности включающего поиска в классе
древовидных схем.
18. Метод сеток на примере двумерной задачи о метрической близости.
Лекции
Лекция 1
Лекция 2
Лекция 3
Лекция 4
Лекция 5
Лекция 6
Лекция 7
Лекция 8
Лекция 9
Лекция 10
Лекция 11
Лекция 12
Лекция 13
Лекция 14
Лекция 15
Лекция 24
Литература
1.
Гасанов Э.Э., Кудрявцев В.Б., Теория хранения и поиска
информации. Москва, «Физматлит», 2002 г.
2.
Гасанов Э.Э. Теория сложности информационного поиска.
Москва, изд-во механико-математического факультета МГУ, 2005 г.
3.
Кудрявцев В.Б., Гасанов Э.Э., Подколзин А.С. Введение в
теорию интеллектуальных систем. М.: Изд-во ф-та ВМиК МГУ, 2006.
4.
Гасанов Э.Э., Ерохин А.Н. Линейный по памяти непереборный
алгоритм решения двумерной задачи интервального поиска. Дискретная математика
(2004) 16, N 4, 49-64.
5.
Gasanov E.E. On Functional Complexity of
Two-dimensional Manhattan Metrics Closeness Problem. Emerging Database
Research In East Europe. Proceedings of the pre-conference workshop of VLDB
2003, 51-56.
6.
http://company.yandex.ru/class/courses/gasanov.xml
Наверх
| 
