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

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

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



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






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


Дискрет. матем., 2018, том 30, выпуск 2, страницы 27–36 (Mi dm1521)  

Оценки среднего размера образа подмножества при композиции случайных отображений

А. М. Зубков, А. А. Серов

Математический институт им. В.А. Стеклова Российской академии наук

Аннотация: Пусть $\mathcal{X}_N$ — множество из $N$ элементов и $F_1,F_2,\ldots$ — последовательность случайных независимых равновероятных отображений $\mathcal{X}_N\to\mathcal{X}_N$. Для подмножества $S_0\subset \mathcal{X}_N$, $|S_0|=m$, рассматривается последовательность его образов $S_t=F_t(\ldots F_2(F_1(S_0))\ldots)$, $t=1,2\ldots$ Описан рекуррентный способ точного вычисления распределения $|S_t|$. Получены двусторонние неравенства для $\mathbf{M}\{|S_t| | |S_0|=m\}$, в которых разность между верхней и нижней оценками имеет порядок $o(m)$, если $m,t,N\to\infty, mt=o(N)$. Результаты представляют интерес для анализа алгоритмов балансировки времени и памяти.

Ключевые слова: композиции случайных отображений, метод балансировки времени и памяти.

Финансовая поддержка Номер гранта
Российский научный фонд 14-50-00005
Исследование выполнено за счет гранта Российского научного фонда (проект № 14-50-00005).


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

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

Англоязычная версия:
Discrete Mathematics and Applications, 2018, 28:5, 331–338

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

Тип публикации: Статья
УДК: 519.212.2
Статья поступила: 28.03.2018

Образец цитирования: А. М. Зубков, А. А. Серов, “Оценки среднего размера образа подмножества при композиции случайных отображений”, Дискрет. матем., 30:2 (2018), 27–36; Discrete Math. Appl., 28:5 (2018), 331–338

Цитирование в формате AMSBIB
\RBibitem{ZubSer18}
\by А.~М.~Зубков, А.~А.~Серов
\paper Оценки среднего размера образа подмножества при композиции случайных отображений
\jour Дискрет. матем.
\yr 2018
\vol 30
\issue 2
\pages 27--36
\mathnet{http://mi.mathnet.ru/dm1521}
\crossref{https://doi.org/10.4213/dm1521}
\elib{http://elibrary.ru/item.asp?id=34940587}
\transl
\jour Discrete Math. Appl.
\yr 2018
\vol 28
\issue 5
\pages 331--338
\crossref{https://doi.org/10.1515/dma-2018-0029}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000448699100006}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-85056217416}


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

    ОТПРАВИТЬ: 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
  • Дискретная математика
    Просмотров:
    Эта страница:101
    Литература:7
    Первая стр.:10

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2018