English version of this page
На главную страницу
Официальный сайт кафедры Математической теории интеллектуальных систем и
лаборатории Проблем теоретической кибернетики
механико-математического факультета МГУ им. М. В. Ломоносова
На первую страницу сервера Новости Кафедра Сотрудники Учеба Наука Исследования Журнал Культура Полнотекстовый поиск по серверу
 ТДФ Теория дискретных функций – лекции и семинары для студентов 1 курса (II поток)
 Ташкентский филиал Ташкентский филиал МГУ им. М.В. Ломоносова
 Семинары расписание специальных семинаров кафедры МаТИС
 Курсы расписание специальных курсов кафедры, программа курсов
 Практикум cпециальный математический практикум кафедры МаТИС, III курс
 Студенты список студентов кафедры по курсам и группам, расписание занятий, выпускники
 Магистратура информация для поступающих в магистратуру
 Аспирантура информация для аспирантов и поступающих в аспирантуру; списки аспирантов

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

Теория баз данных

Вопросы по курсу, 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

Наверх

   © 2001-2015 г. Кафедра Математической теории интеллектуальных систем, лаборатория Проблем теоретической кибернетики Написать вебмастеру   
XWare
 Полнотекстовый поиск
 
Только точная форма слов      Выводить по результатов на странице
Rambler's Top100 Рейтинг@Mail.ru