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

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

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

Руководитель курса: проф. Гасанов Э.Э.
Время и место проведения: суббота 10:45 в ауд. 12-12.
Годовой спецкурс, предназначенный для студентов 2-5 курсов мех-мата МГУ.

 

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

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

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

 

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

  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.

Наверх

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