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

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

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



Дискрет. матем.:
Год:
Том:
Выпуск:
Страница:
Найти






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


Дискрет. матем., 2011, том 23, выпуск 2, страницы 129–158 (Mi dm1148)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

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

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


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

DOI: https://doi.org/10.4213/dm1148

Полный текст: PDF файл (258 kB)
Список литературы: PDF файл   HTML файл

Англоязычная версия:
Discrete Mathematics and Applications, 2011, 21:3, 345–379

Реферативные базы данных:

Тип публикации: Статья
УДК: 519.2
Статья поступила: 13.10.2010
Переработанный вариант поступил: 07.02.2011

Образец цитирования: Н. С. Кучеренко, “Средняя сложность поиска идентичных объектов для случайных неравномерных баз данных”, Дискрет. матем., 23:2 (2011), 129–158; Discrete Math. Appl., 21:3 (2011), 345–379

Цитирование в формате AMSBIB
\RBibitem{Kuc11}
\by Н.~С.~Кучеренко
\paper Средняя сложность поиска идентичных объектов для случайных неравномерных баз данных
\jour Дискрет. матем.
\yr 2011
\vol 23
\issue 2
\pages 129--158
\mathnet{http://mi.mathnet.ru/dm1148}
\crossref{https://doi.org/10.4213/dm1148}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=2865914}
\elib{http://elibrary.ru/item.asp?id=20730391}
\transl
\jour Discrete Math. Appl.
\yr 2011
\vol 21
\issue 3
\pages 345--379
\crossref{https://doi.org/10.1515/DMA.2011.023}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-79961078141}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1148
  • https://doi.org/10.4213/dm1148
  • http://mi.mathnet.ru/rus/dm/v23/i2/p129

    ОТПРАВИТЬ: 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

    Эта публикация цитируется в следующих статьяx:
    1. Кучеренко Н.С., “Математическое ожидание средней длины кодов Хафмана”, Интеллектуальные системы, 17:1-4 (2013), 241–245  mathscinet  elib
  • Дискретная математика
    Просмотров:
    Эта страница:276
    Полный текст:94
    Литература:43
    Первая стр.:16
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020