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

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

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



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






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


Дискрет. матем., 2014, том 26, выпуск 4, страницы 43–50 (Mi dm1303)  

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

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

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

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

Аннотация: Пусть $\mathcal{N}$ — множество из $N$ элементов и $F_1,F_2,\ldots$ — последовательность случайных независимых равновероятных отображений $\mathcal{N}\to\mathcal{N}$. Для подмножества $S_0\subset \mathcal{N}, |S_0|=n$, рассматриваются последовательность его образов $S_k=F_k(\ldots F_2(F_1(S_0))\ldots), k=1,2\ldots$, и последовательность их объединений $\Psi_k=S_1\cup\ldots\cup S_k, k=1,2\ldots$ Описан способ точного вычисления распределений $|S_k|$ и $|\Psi_k|$ при умеренных значениях $N$. Получены двусторонние неравенства для $\mathbf{M}|S_k|$ и $\mathbf{M}|\Psi_k|$, в которых верхние оценки асимптотически эквивалентны нижним, если $N,n,k\to\infty, nk=o(N)$. Результаты представляют интерес для анализа алгоритмов балансировки времени и памяти.

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

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

Англоязычная версия:
Discrete Mathematics and Applications, 2015, 25:3, 179–185

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

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

Образец цитирования: А. М. Зубков, А. А. Серов, “Совокупность образов подмножества конечного множества при итерациях случайных отображений”, Дискрет. матем., 26:4 (2014), 43–50; Discrete Math. Appl., 25:3 (2015), 179–185

Цитирование в формате AMSBIB
\RBibitem{ZubSer14}
\by А.~М.~Зубков, А.~А.~Серов
\paper Совокупность образов подмножества конечного множества при итерациях случайных отображений
\jour Дискрет. матем.
\yr 2014
\vol 26
\issue 4
\pages 43--50
\mathnet{http://mi.mathnet.ru/dm1303}
\crossref{https://doi.org/10.4213/dm1303}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=3467224}
\elib{http://elibrary.ru/item.asp?id=22834160}
\transl
\jour Discrete Math. Appl.
\yr 2015
\vol 25
\issue 3
\pages 179--185
\crossref{https://doi.org/10.1515/dma-2015-0017}
\isi{http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&DestLinkType=FullRecord&DestApp=ALL_WOS&KeyUT=000366854000006}
\elib{http://elibrary.ru/item.asp?id=24049599}
\scopus{http://www.scopus.com/record/display.url?origin=inward&eid=2-s2.0-84931050021}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/dm1303
  • https://doi.org/10.4213/dm1303
  • http://mi.mathnet.ru/rus/dm/v26/i4/p43

    ОТПРАВИТЬ: 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. А. А. Серов, “Образы конечного множества при итерациях двух случайных зависимых отображений”, Дискрет. матем., 27:4 (2015), 133–140  mathnet  crossref  mathscinet  zmath  elib; A. A. Serov, “Images of a finite set under iterations of two random dependent mappings”, Discrete Math. Appl., 26:3 (2016), 175–181  crossref  isi  elib
    2. А. М. Зубков, А. А. Серов, “Предельная теорема для мощности образа подмножества при композиции случайных отображений”, Дискрет. матем., 29:1 (2017), 17–26  mathnet  crossref  elib; A. M. Zubkov, A. A. Serov, “Limit theorem for the size of an image of subset under compositions of random mappings”, Discrete Math. Appl., 28:2 (2018), 131–138  crossref  isi
    3. А. М. Зубков, В. О. Миронкин, “Распределение длины отрезка апериодичности в графе $k$-кратной итерации случайного равновероятного отображения”, Матем. вопр. криптогр., 8:4 (2017), 63–74  mathnet  crossref  mathscinet  elib
    4. Kogan D., Manohar N., Boneh D., “T/Key: Second-Factor Authentication From Secure Hash Chains”, Ccs'17: Proceedings of the 2017 Acm Sigsac Conference on Computer and Communications Security, Assoc Computing Machinery, 2017, 983–999  crossref  isi  scopus
    5. А. М. Зубков, А. А. Серов, “Оценки среднего размера образа подмножества при композиции случайных отображений”, Дискрет. матем., 30:2 (2018), 27–36  mathnet  crossref  elib; A. M. Zubkov, A. A. Serov, “Estimates of the mean size of the subset image under composition of random mappings”, Discrete Math. Appl., 28:5 (2018), 331–338  crossref  isi
    6. В. О. Миронкин, В. Г. Михайлов, “О множестве образов $k$-кратной итерации равновероятного случайного отображения”, Матем. вопр. криптогр., 9:3 (2018), 99–108  mathnet  crossref  elib
  • Дискретная математика
    Просмотров:
    Эта страница:225
    Полный текст:29
    Литература:41
    Первая стр.:61

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