RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





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






Конференция «Современная математика и ее приложения», посвященная подведению итогов реализации гранта РНФ № 14-50-00005
19 ноября 2018 г. 15:10–15:30, Направление «Дискретная математика и математическая логика», г. Москва, конференц-зал МИАН (ул. Губкина, 8)
 


Оценки сложности для баз данных, снабженных логическими теориями

В. В. Подольский
Видеозаписи:
MP4 585.3 Mb
MP4 265.8 Mb

Количество просмотров:
Эта страница:74
Видеофайлы:9

В. В. Подольский
Фотогалерея


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

  2. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  3. Сообщите администратору портала о данной ошибке

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

Статьи по теме:

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