RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Ближайшие семинары
Календарь семинаров
Список семинаров
Архив по годам
Регистрация семинара

Поиск
RSS
Ближайшие семинары





Для просмотра файлов Вам могут потребоваться








Семинар отдела дискретной математики МИАН
1 июня 2010 г. 16:00, г. Москва, МИАН, комн. 511 (ул. Губкина, 8)
 


Сложность поиска в случайных базах данных

Н. С. Кучеренко

Количество просмотров:
Эта страница:46

Аннотация: В докладе рассматриваются алгоритмы поиска в базах данных, использующие только операции сравнения. Алгоритм поиска формализуется как информационный граф (ИГ), который представляет собой ориентированный граф, ребра и вершины которого нагружены элементами данных и функциями, со специально определяемым функционированием такого графа. Сложность ИГ определяется как среднее количество операций сравнения, выполняемых на запросе. В докладе будут изложены результаты о структуре оптимального по вычислительным возможностям информационного графа и о поведении его сложности на случайных базах данных. Приводятся достаточные условия, обеспечивающие логарифмический порядок роста сложности. Для некоторых естественных баз данных с логарифмическим поведением строятся уточненные оценки. Построена бесконечная возрастающая шкала функций роста сложности, начинающаяся с ограниченных функций и заканчивающаяся двоичным логарифмом.

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017