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

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Интеллектуальные системы. Теория и приложения:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Интеллектуальные системы. Теория и приложения, 2017, том 21, выпуск 4, страницы 102–114 (Mi ista32)  

О функциональной сложности двумерной задачи о доминировании

Э. Э. Гасанов

Московский государственный университет имени М. В. Ломоносова, механико-математический факультет

Аннотация: В работе исследуется двумерная задача о доминировании, в которой база данных представляет собой множество точек на плоскости, и надо для произвольной точки плоскости, интерпретируемой как запрос на поиск, найти все точки из базы данных, которые по обоим координатам превосходят запрос. Под функциональной сложностью понимается функция зависимости времени поиска от объема памяти, которую можно выделить под структуры данных. В работе показано, как, используя метод Бентли-Маурера, можно получить алгоритмы с разными соотношениями времени поиска и объема памяти.

Ключевые слова: информационно-графовая модель данных, двумерная задача о доминировании, функциональная сложность, метод сеток.

Полный текст: PDF файл (505 kB)
Тип публикации: Статья

Образец цитирования: Э. Э. Гасанов, “О функциональной сложности двумерной задачи о доминировании”, Интеллектуальные системы. Теория и приложения, 21:4 (2017), 102–114

Цитирование в формате AMSBIB
\RBibitem{Gas17}
\by Э.~Э.~Гасанов
\paper О функциональной сложности двумерной задачи о доминировании
\jour Интеллектуальные системы. Теория и приложения
\yr 2017
\vol 21
\issue 4
\pages 102--114
\mathnet{http://mi.mathnet.ru/ista32}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/ista32
  • http://mi.mathnet.ru/rus/ista/v21/i4/p102

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Интеллектуальные системы. Теория и приложения
    Просмотров:
    Эта страница:15
    Полный текст:7
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020