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

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

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



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






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


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

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

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

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

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

Аннотация: Пусть $\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}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3808075}
\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

    Эта публикация цитируется в следующих статьяx:
    1. В. О. Миронкин, “Коллизии и инцидентность вершин компонентам в графе $k$-кратной итерации равновероятного случайного отображения”, Дискрет. матем., 31:4 (2019), 38–52  mathnet  crossref
    2. В. О. Миронкин, “Распределение длины отрезка апериодичности в графе композиции независимых равновероятных случайных отображений”, Матем. вопр. криптогр., 10:3 (2019), 89–99  mathnet  crossref
  • Дискретная математика
    Просмотров:
    Эта страница:194
    Литература:17
    Первая стр.:22
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020